<p>Dick Lipton and colleagues recently worked on this problem, and Lipton blogged about it here:</p>

<p><a href="http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/">http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/</a></p>

<p>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.<br>
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.</p>

CC BY-SA 2.5
2010-08-20T07:58:46.807Z
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
CC BY-SA 2.5
2010-08-17T23:34:09.417Z
and what about lower bounds?
Marcos Villagra
CC BY-SA 2.5
2010-08-17T21:19:52.080Z
2010-08-17T21:19:52.080Z
Andy Drucker
<p>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:</p>

<blockquote>
  <p>Dexter Kozen: Lower Bounds for Natural Proof Systems FOCS 1977: 254-266</p>
</blockquote>

<p>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. </p>

CC BY-SA 3.0
2014-11-09T00:23:01.820Z
Cool!  Although it might be slightly off topic, yes, you can show a space complexity lower bound for solving the fixed k intersection non-emptiness problem.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:49:34.057Z
@user124864 Given $k$ DFA's with $n$ states each, the product automaton will have $n^k$ states. Now, there are two tricks you can do to reduce its size. The first is that you just consider the reachable component of the product graph. Second, you could minimize the product DFA. At the end of the day, figuring out what language is recognized by this product automaton is hard.
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:49:52.260Z
@user124864 Even just trying to determine if the product DFA recognizes a non-empty language is hard. This is the intersection non-emptiness problem. By hard, I mean that it is $XNL$ complete in a strong sense.
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:51:51.423Z
@user124864 If you can solve it in less than $n^k$ time, then we get faster algorithms for PSPACE complete problems. It is not solvable in $o(1) \cdot k \cdot \log(n)$ non-deterministic binary space. It's not known if we can solve it in less than $k^2 \log^2(n)$ deterministic binary space. It's not known if we can solve it in simultaneous deterministic polynomial time and $f(k) \cdot \log^2(n)$ binary space for any function $f$ (doing so would improve Savitch's theorem).
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:55:09.187Z
@user124864 Note: we have both of the following.  (1) Beating $n^k$ time deterministically implies faster deterministic algorithms for PSPACE complete problems and (2) beating $n^k$ time non-deterministically implies faster non-deterministic algorithms for PSPACE complete problems.
Michael Wehar
CC BY-SA 2.5
2010-08-20T08:01:17.860Z
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
CC BY-SA 2.5
2010-08-22T19:18:01.143Z
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
CC BY-SA 2.5
2010-10-02T16:46:18.053Z
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
CC BY-SA 2.5
2010-08-19T03:21:48.003Z
2010-08-19T03:21:48.003Z
Ryan Williams
<p>Given two automata <span class="math-container">$A$</span>, <span class="math-container">$B$</span> accepting finite languages (acyclic automata), the state complexity of <span class="math-container">$L(A) \cap L(B)$</span> is in <span class="math-container">$\Theta(|A| \cdot |B|)$</span> <a href="https://doi.org/10.1007/978-3-540-73208-2_22" rel="nofollow noreferrer">(1)</a>. This result also holds for unary DFAs (not necessarily acyclic) <a href="https://www.worldscientific.com/doi/abs/10.1142/S012905410200100X" rel="nofollow noreferrer">(2)</a>. 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 <span class="math-container">$O(n^2)$</span> space. All you need is a constant number of counters of logarithmic size. When you compute the transition function for the new state <span class="math-container">$(q,r)$</span> you only have to scan the input without looking to any previously generated data.</p>
<p>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 <a href="https://www.worldscientific.com/doi/abs/10.1142/S012905410200100X" rel="nofollow noreferrer">(2)</a>, 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 <span class="math-container">$n$</span> be the number of states in the resulting automaton, then for all <span class="math-container">$1 \leq i \leq n$</span>, state <span class="math-container">$i$</span> is a final state iff <span class="math-container">$a^i$</span> is accepted by both <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. This test can be carried with few space.</p>

CC BY-SA 2.5
2010-08-25T11:30:23.123Z
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
CC BY-SA 4.0
2010-08-24T21:33:50.300Z
2022-09-29T14:00:50.740Z
2022-09-29T14:00:50.740Z
Michael Blondin
<p>The answer is <strong>yes</strong> 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.</p>

<p>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.</p>

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

<p>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$.</p>

<p><strong>Lemma 1</strong>: Deciding whether $q \equiv r$ is in NL.</p>

<p>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.</p>

<p><strong>Lemma 2</strong>: Deciding whether $q$ is (in)accessible is in NL.</p>

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

<p><strong>Definition 2</strong>: 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)$.</p>

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

<p>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.</p>

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

<p><strong>Theorem</strong>: Minimizing $A$ can be done in $O(\log^2 n)$ space.</p>

<p>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</p>

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

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

CC BY-SA 3.0
2013-01-10T16:57:21.730Z
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
CC BY-SA 3.0
2013-01-14T18:53:25.117Z
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
CC BY-SA 2.5
2010-10-02T17:17:30.353Z
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
CC BY-SA 3.0
2010-10-02T05:41:42.280Z
2013-01-14T18:55:58.910Z
2013-01-14T18:55:58.910Z
Michael Blondin
<p>The intersection of two (minimal) DFAs with n states can be computed using O(n<sup>2</sup>) time and space. This is optimal in general, since the resulting (minimal) DFA may have n<sup>2</sup> states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n<sup>2-eps</sup>, for some constant eps>0? I would be interested in such a result even for the special case where the input DFAs are acyclic.</p>

CC BY-SA 2.5
2010-08-17T14:50:58.153Z
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
CC BY-SA 2.5
2010-08-17T18:00:25.013Z
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
CC BY-SA 2.5
2010-08-18T01:59:52.977Z
retagging: cs.cc is an arxiv designation, so the given tags don't need the cs.cc prefix.
Suresh Venkat
<automata-theory><dfa>
DFA intersection in subquadratic space?
Rasmus Pagh
# DFA intersection in subquadratic space?

(Asked by: username_0 on 2010-08-17)

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.

**Tags:** automata-theory, dfa

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: retagging: cs.cc is an arxiv designation, so the given tags don't need the cs.cc prefix.  

---

## 4 answers

### Answer by username_7 on 2010-10-02. Score: 17 | Accepted answer

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

> **Comments:**
> **username_8**: 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.  
> **username_5**: 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.  
> **username_7**: 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!  

---

### Answer by username_3 on 2010-08-17. Score: 14

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.

> **Comments:**
> **username_4**: and what about lower bounds?  
> **username_0**: 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.  

---

### Answer by username_5 on 2010-08-19. Score: 13

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.

> **Comments:**
> **username_0**: 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?  
> **username_5**: 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.  
> **username_7**: 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.  
> **username_6**: Cool!  Although it might be slightly off topic, yes, you can show a space complexity lower bound for solving the fixed k intersection non-emptiness problem.  :)  
> **username_6**: @user124864 Given $k$ DFA's with $n$ states each, the product automaton will have $n^k$ states. Now, there are two tricks you can do to reduce its size. The first is that you just consider the reachable component of the product graph. Second, you could minimize the product DFA. At the end of the day, figuring out what language is recognized by this product automaton is hard.  
> **username_6**: @user124864 Even just trying to determine if the product DFA recognizes a non-empty language is hard. This is the intersection non-emptiness problem. By hard, I mean that it is $XNL$ complete in a strong sense.  
> **username_6**: @user124864 If you can solve it in less than $n^k$ time, then we get faster algorithms for PSPACE complete problems. It is not solvable in $o(1) \cdot k \cdot \log(n)$ non-deterministic binary space. It's not known if we can solve it in less than $k^2 \log^2(n)$ deterministic binary space. It's not known if we can solve it in simultaneous deterministic polynomial time and $f(k) \cdot \log^2(n)$ binary space for any function $f$ (doing so would improve Savitch's theorem).  
> **username_6**: @user124864 Note: we have both of the following.  (1) Beating $n^k$ time deterministically implies faster deterministic algorithms for PSPACE complete problems and (2) beating $n^k$ time non-deterministically implies faster non-deterministic algorithms for PSPACE complete problems.  

---

### Answer by username_7 on 2010-08-24. Score: 7

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)](https://doi.org/10.1007/978-3-540-73208-2_22). This result also holds for unary DFAs (not necessarily acyclic) [(2)](https://www.worldscientific.com/doi/abs/10.1142/S012905410200100X). 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)](https://www.worldscientific.com/doi/abs/10.1142/S012905410200100X), 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.

> **Comments:**
> **username_0**: 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.  

---

