7
$\begingroup$

Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. However, the product automaton of $A_1$ and $A_2$ can be quadratic in size.

This motivates my question: is there an algorithm that avoids this blow-up and matches the $\mathcal{O}(n\log~n)$ complexity of Hopcroft's minimization algorithm that decides language equivalence?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
9
$\begingroup$

EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis.

https://cstheory.stackexchange.com/a/29166/2367

ORIGINAL ANSWER: The following blog post points to a paper that discusses this question. The answer is, a better than quadratic algorithm would yield improved running times for several notoriously hard computational problems. So, there is evidence that the answer to your question is "no". https://rjlipton.wpcomstaging.com/2009/08/17/on-the-intersection-of-finite-automata/

George Karakostas, Richard J. Lipton, Anastasios Viglas: On the Complexity of Intersecting Finite State Automata. CCC 2000: 229-234

Improve this answer
$\endgroup$
17
  • 1
    $\begingroup$ Thanks for the reference, I am still studying the exact claims. But I don't see yet how a subquadratic algorithm for language inclusion proofs their assumption $\mathcal{F}$ for the existence of a $O(n^{\epsilon k})$ algorithm for $k$-PEP. $\endgroup$
    – Janmar
    Commented May 25, 2023 at 15:00
  • 1
    $\begingroup$ I got that connection, however the decision problem studied by the references are more generic because it considers the intersection of DFAs $A_1, \dots, A_k$ for some variable $k$. It provides a lowerbound that an algorithm solving this does not have runtime with an exponent sub-linear in terms of $k$. However this bound does not seems to indicate a quadratic lowerbound for $k=2$. $\endgroup$
    – Janmar
    Commented May 30, 2023 at 8:53
  • 1
    $\begingroup$ In summary, I believe the blogpost answers my question, but with a "open" instead of a negative answer. In particular in the last paragraph they specifically mention the open problem for the intersection of 2 automata. $\endgroup$
    – Janmar
    Commented May 30, 2023 at 8:55
  • 1
    $\begingroup$ I just noticed that this question was answered 8 years ago by @MichaelWehar. Michael, I should have tagged you on this question :-) $\endgroup$
    – Hermann Gruber
    Commented May 30, 2023 at 13:50
  • 2
    $\begingroup$ I guess that could work! I can mention your comment that inclusion is equivalent to intersection non-emptiness for two DFA's. $\endgroup$
    – Michael Wehar
    Commented May 31, 2023 at 19:29

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