DFA intersection in subquadratic space?

Question

The intersection of two (minimal) DFAs with n states can be computed using O(n²) time and space. This is optimal in general, since the resulting (minimal) DFA may have n² states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n^2-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.

Answer 1

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)$.

Answer 2

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.

Answer 3

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.

Answer 4

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.