27
$\begingroup$

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.

Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M_1,M_2$, but I was wondering if anything more efficient is known.

Is there a $o(n^2)$ algorithm for deciding whether $L_1\cap L_2\neq \emptyset$? What is the fastest known algorithm?

$\endgroup$
9
  • 5
    $\begingroup$ If anyone has good ideas please let me know, but currently it's an open problem. If you could solve this problem in say linear time, then basically any problem solvable by a non-deterministic machine using only n bits of memory could be solved deterministically in $2^{\frac{n}{2}}$ time. $\endgroup$ Jan 14, 2015 at 17:05
  • 6
    $\begingroup$ I think it's still open for any sub-quadratic. Some more info: rjlipton.wordpress.com/2009/08/17/… $\endgroup$ Jan 14, 2015 at 17:13
  • 4
    $\begingroup$ So for example (based on Michael's comment), the strong exponential time hypothesis implies that the exponent should be 2. I think this could also proved to follow from the exponential time hypothesis... $\endgroup$ Jan 15, 2015 at 5:25
  • 4
    $\begingroup$ RB: Assume you can test for emptiness of two DFAs of size $n$ in time $n^{1+\varepsilon}$ with $\varepsilon < 1$. Now, if you have $k$ DFAs of size $n$, you can build the product of the first $k/2$ DFAs and of the remaining $k/2$ DFAs. Then, test for emptiness in time $(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$ which is better than $n^k$. vzn: This award-winning paper was written by @MichaelWehar who commented in this thread. Michael, perhaps you could submit an answer, if you have time! $\endgroup$ Jan 15, 2015 at 19:18
  • 4
    $\begingroup$ @RyanWilliams Hi Ryan, what leads you to think that the weaker exponential time hypothesis implies that we can't solve intersection non-emptiness for two DFA's more quickly? Someone else suggested this to me once too. :) $\endgroup$ Jan 17, 2015 at 3:31

1 Answer 1

26
$\begingroup$

Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.


We will prove a stronger theorem and then the simple answer will follow.

Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time, then any problem that's non-deterministically solvable using only n bits of memory is deterministically solvable in $poly(n)\cdot2^{(\delta n/2)}$ time.

Justification: Suppose that we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time. Let a non-deterministic Turing machine M with a read only input tape and a read/write binary work tape be given. Let an input string x of length n be given. Suppose that M doesn't access more than n bits of memory on the binary work tape.

A computation of M on input x can be represented by a finite list of configurations. Each configuration consists of a state, a position on the input tape, a position on the work tape, and up to n bits of memory that represent the work tape.

Now, consider that the work tape was split in half. In other words, we have a left section of $\frac{n}{2}$ cells and a right section of $\frac{n}{2}$ cells. Each configuration can be broken up into a left piece and a right piece. The left piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the left section. The right piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the right section.

Now, we build a DFA $D_1$ whose states are left pieces and a DFA $D_2$ whose states are right pieces. The alphabet characters are instructions that say which state to go to, how the tape heads should move, and how the work tape's active cell should be manipulated.

The idea is that $D_1$ and $D_2$ read in a list of instructions corresponding to a computation of M on input x and together verify that it is valid and accepting. Both $D_1$ and $D_2$ will always agree on where the tape heads are because that information is included in their input characters. Therefore, we can have $D_1$ verify that the instruction is appropriate when the work tape position is in the left piece and $D_2$ verify when in the right piece.

In total, there are at most $poly(n) \cdot 2^{n/2}$ states for each DFA and at most $poly(n)$ distinct alphabet characters.

By the initial assumption, it follows that we can solve intersection non-emptiness for the two DFA's in $poly(n) \cdot 2^{(\delta n /2)}$ time.

You might find this helpful: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/


CNF-SAT is solvable using $k+O(\log(n))$ bits of memory where k is the number of variables. The preceding construction can be used to show that if we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time, then we can solve CNF-SAT in $poly(n) \cdot 2^{(\delta k/2)}$ time. Therefore, the simple answer holds.

Comments, corrections, suggestions, and questions are welcomed. :)

$\endgroup$
10
  • 2
    $\begingroup$ all great but the original question above was for NFAs; does it all still follow? also, some key detail is left out. seems worth a paper. or is it all in your published one? if so plz cite it/ tie in to numbered theorems there etc. also it would be helpful to state this all more in terms of std complexity classes L,P,NP,PSpace,ExpTime etc if possible. also wondering if anything can be said about the direction "strong" 2-way DFA intersection emptiness lower bound ($\Omega(n^2)$?) → SETH...? what needs to be shown for that? $\endgroup$
    – vzn
    Nov 5, 2015 at 5:57
  • 2
    $\begingroup$ Hi VZN, the intersection problem for NFA's appears slightly harder than the intersection problem for DFA's. However, this is not the case because there is a parameterized reduction from intersection non-emptiness for $k$ NFA's to intersection non-emptiness for $k$ DFA's. This is mentioned in my first paper. $\endgroup$ Nov 5, 2015 at 16:34
  • 1
    $\begingroup$ Maybe you can describe in more detail what you mean when you mention 2-way DFA. The non-emptiness problem for $(2k-2)$-turn two-way DFA's is just as hard as the intersection non-emptiness problem for $k$ one-way DFA's. Link: cs.stackexchange.com/questions/13456/… $\endgroup$ Nov 5, 2015 at 16:58
  • 1
    $\begingroup$ In terms of standard complexity classes, you could state this as something like: $NSpace(2 \cdot \log(n)) \subseteq DTime(n)$ implies SETH is false. When I write $NSpace(2 \cdot \log(n))$, I mean $2\cdot \log(n)$ space for non-deterministic Turing machines with a two-way read only input tape and a two-way read/write binary work tape. $\endgroup$ Nov 5, 2015 at 17:01
  • 1
    $\begingroup$ @MichaelWehar 1. If we can solve intersection of $k$ DFA's in $O(nk)$ time what is the consequence? 2. If we can solve intersection of $k$ DFA's in $O(n^{f(k)})$ time what is the consequence where $f=o(k)$ (might be logarithmic or $\sqrt k$ etc.)? $\endgroup$
    – Turbo
    Mar 12, 2021 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.