# DFA intersection in subquadratic space?

The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n2-eps, for some constant eps>0? I would be interested in such a result even for the special case where the input DFAs are acyclic.

-
Um...if two n-state DFAs are acyclic, then each merely accepts a finite set of words of length at most n, in which case their intersection is just the intersection of the two labelled transition graphs, which will have n states and can be computed in linear time and space. Or am I missing something? –  Joshua Grochow Aug 17 '10 at 14:50
Yes, acyclic DFAs accept only a finite set of words. But there are examples of acyclic DFAs whose intersection has size n^2. E.g., think about one DFA that accepts strings of the form AABC (where ABC are strings of length k), and one that accepts strings of the form ABCC. –  Rasmus Pagh Aug 17 '10 at 18:00
retagging: cs.cc is an arxiv designation, so the given tags don't need the cs.cc prefix. –  Suresh Venkat Aug 18 '10 at 1:59

The answer is yes without any requirement on the size of the automaton. It can be computed in $O(\log^2 n)$ space even for $k$ DFAs where $k$ is a constant.

Let $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$ ($i \in [k])$ be $k$ DFAs. We show that, given $\langle A_1, \ldots, A_k \rangle$, computing the minimal DFA recognizing $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ can be done in $O(\log^2 n)$ space. We first prove some technical results.

Definition 1: Let $q, r$ be two states then $q \equiv r$ iff $\forall w \in \Sigma^*$, $q . w \in F \Leftrightarrow r . w \in F$

We now consider the automaton $A$ given by the classical cartesian product construction. Let $q = (q_1, \ldots, q_k)$ and $r = (r_1, \ldots, r_k)$ be states of $A$.

Lemma 1: Deciding whether $q \equiv r$ is in NL.

Proof (sketch): We show that testing inequivalence is in NL and use NL = coNL. Guess a word $w \in \Sigma^*$ (one letter at the time) such that $q . w$ is a final state and $r . w$ isn't. This can be achieved by computing $q_i . w, r_i . w$ in log-space for $i \in [k]$ and using the fact that $q$ is final iff $q_i \in F_i \, \forall i \in [k]$. It can be shown that $q \not\equiv r$ implies the existence of a $w$ of poly-size.

Lemma 2: Deciding whether $q$ is (in)accessible is in NL.

Proof (sketch): Guess (poly-size) paths from $z_i$ to $q_i$ ($i \in [k]$).

Definition 2: Consider the states of $A$ in lexicographical order. Define $s(1)$ as being the first accessible state and $s(i)$ the first accessible state following $s(i-1)$ which isn't equivalent to any previous state. We define $c(q)$ as the unique $i$ such that $q \equiv s(i)$.

Lemma 3: $s(i)$ can be computed in $O(\log^2 n)$ space.

Proof (sketch): Definition 2 yields an algorithm. We use $k$ counters to iterate over the states. Let $j \leftarrow 0$ and $q$ be the current state. At each state, we use lemma 2 to verify if $q$ is accessible. If it is, we loop on every previous states and we verify if any of them is equivalent to $q$. If there isn't any, we increment $j$ and output $q$ if $j = i$. Otherwise, we store $q$ as being $s(j)$ and we continue. Since we only store a constant number of counters and our tests can be carried out in $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$, this completes the proof.

Corollary 1: $c(q)$ can be computed in $O(\log^2 n)$ space.

Theorem: Minimizing $A$ can be done in $O(\log^2 n)$ space.

Proof (sketch): Let $1 \leq m \leq |Q_0| \cdots |Q_1|$ be the largest $i$ such that $s(i)$ is defined (ie. the number of classes of $\equiv$). We give an algorithm outputting an automaton $A' = (Q', \Sigma, \delta', z', F')$ where

• $Q' = \lbrace s(i) : i \in [m] \rbrace$;
• $F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$;
• $z' = s(c(q))$ where $q = (z_0, \ldots, z_k)$.

We now show how to compute $\delta'$. For every $i \in [m], a \in \Sigma$, compute $q \leftarrow s(i) . a$ and output the transition $\left(s(i), a, s(c(q))\right)$. By lemma 3 and corollary 1, this algorithm runs in $O(\log^2 n)$ space. It can be checked that $A'$ is minimal and $\text{L}(A') = \text{L}(A)$.

-
Nice algorithm! Here is a slightly different way to look at this algorithm. Its core is that the state minimization of any given DFA can be done in polynomial time and $O(\log^2 n)$ space. After that, it is easy to construct some DFA representing the intersection in the logarithmic space (hence in polynomial time and $O(\log^2 n)$ space), and we can compose two functions computable in polynomial time and $O(\log^2 n)$ space (in a similar way to composing two logarithmic-space reductions), yielding the whole algorithm in polynomial time and $O(\log^2 n)$ space. –  Tsuyoshi Ito Oct 2 '10 at 17:17
I just saw this answer... I don't see why the algorithm runs in polytime and $O(\log^2 n)$ space simultaneously. Yes, $NL \subseteq P \cap DSPACE[\log^2 n]$, but it is not known if $NL \subseteq TISP[n^{O(1)}, \log^2 n]$ -- that is, we can get an algorithm running in polytime, and we can get another algorithm running in $O(\log^2 n)$ space, but I do not know how to solve $NL$ problems in polytime and $O(\log^2 n)$ space with a single algorithm. –  Ryan Williams Jan 10 '13 at 16:57
You are right, I don't know how either. I posted this a long time ago, so I'm not sure why I wrote it this way, but perhaps I meant "polynomial time or O(log² n)". I will edit it because it is misleading. Thank you! –  Michael Blondin Jan 14 '13 at 18:53

Dick Lipton and colleagues recently worked on this problem, and Lipton blogged about it here:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

It appears that doing better than O(n^2) is open even for the very-special case of determining if the DFA intersection defines the empty language.
The paper gives complexity consequences that would result from a much-improved algorithm handling not just 2 DFAs in the intersection, but larger numbers as well.

-
and what about lower bounds? –  Marcos Villagra Aug 17 '10 at 23:34
Just to clarify the questions: I'm happy to spend O(n^2) time (or maybe even n^O(1) time) to improve the space bound. –  Rasmus Pagh Aug 20 '10 at 7:58

If you're given k DFAs (k is part of the input) and wish to know if their intersection is empty, this problem is PSPACE-complete in general:

Dexter Kozen: Lower Bounds for Natural Proof Systems FOCS 1977: 254-266

Perhaps if you carefully study this proof (and similar constructions by Lipton and his co-authors), you might find some sort of space lower bound even for fixed k.

-
Thanks for this pointer. I'm guessing that this could possibly lead to an n^Omega(1) space lower bound on the additional space needed, apart from the input. But could it possibly lead to a super-linear space lower bound? –  Rasmus Pagh Aug 20 '10 at 8:01
Hmmm... intuition says that the k DFAs together can encode all possible configurations of a machine using space O(k*log n). I am not sure what time/space lower bounds you can infer from this, but it seems that if you could faithfully represent the intersection of the k DFA in n^{o(k)} space then something unlikely should happen, for example, possibly subexponential size circuits for QBF. –  Ryan Williams Aug 22 '10 at 19:18
He doesn't want to test for the emptiness, he only wants to build the minimal automaton for the intersection which appears to be feasible in O(log^2 n) space according to my last post. –  Michael Blondin Oct 2 '10 at 16:46

Given two automata $A$, $B$ accepting finite languages (acyclic automata), the state complexity of $L(A) \cap L(B)$ is in $\Theta(|A| \cdot |B|)$ (1). This result also holds for unary DFAs (not necessarily acyclic) (2). However, you seem to be talking about the space required to compute the intersection of two automata. I don't see how the classic construction using the Cartesian product uses $O(n^2)$ space. All you need is a constant number of counters of logarithmic size. When you compute the transition function for the new state $(q,r)$ you only have to scan the input without looking to any previously generated data.

Perhaps you want to output the minimal automaton? If this is the case, then I have no clue whether it can be achieved. The state complexity of the intersection for finite languages doesn't seem encouraging. However, unary DFAs have the same state complexity and I think it can be achieved with such automata. By using results from (2), you can get the exact size of the automaton recognizing the intersection. This size is described by the length of the tail and the cycle, thus the transition function can be easily computed with very few space since the structure is entirely described by those two sizes. Then, all you have to do is to generate the set of final states. Let $n$ be the number of states in the resulting automaton, then for all $1 \leq i \leq n$, state $i$ is a final state iff $a^i$ is accepted by both $A$ and $B$. This test can be carried with few space.

-
Yes, I am interested in the minimal automaton, or at least an automaton of similar size. Thanks for the pointers to unary DFAs. However, this does not seem to help much for the general case. –  Rasmus Pagh Aug 25 '10 at 11:30