7

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?

Janmar
  • 135
  • 6

1 Answers1

9

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

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
  • 1
    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. – Janmar May 25 '23 at 15:00
  • @Janmar this is certainly a good idea. Beware that I just somehow remembered the blog post, and didn't check the details. If you find out, please leave a comment, and also: feel free to update my answer. – Hermann Gruber May 26 '23 at 09:27
  • Just in case you might have overlooked it: I tacitly assumed that you are aware that for DFAs, you can reduce language inclusion to intersection emptiness. Just complement automaton A2 and check if the intersection with A1 is empty. – Hermann Gruber May 26 '23 at 09:32
  • 1
    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$. – Janmar May 30 '23 at 08:53
  • 1
    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. – Janmar May 30 '23 at 08:55
  • 1
    I just noticed that this question was answered 8 years ago by @MichaelWehar. Michael, I should have tagged you on this question :-) – Hermann Gruber May 30 '23 at 13:50
  • 1
    @HermannGruber Beware that comment notification only works for users that have already interacted with the post in some way; you cannot ping random users out of the blue. See https://meta.stackexchange.com/a/43020 for details. If you want to alert Michael Wehar, you can post a comment on some of his questions or answers. – Emil Jeřábek May 30 '23 at 15:34
  • @EmilJeřábek thanks for the hint! – Hermann Gruber May 30 '23 at 21:48
  • 1
    This is great! I will write up a more thorough answer, hopefully I'll get a chance tomorrow. Here is our 2020 paper where we proved some stronger conditional lower bounds for the intersection non-emptiness problem: https://link.springer.com/chapter/10.1007/978-3-030-48516-0_6 – Michael Wehar May 30 '23 at 23:07
  • 1
    @MichaelWehar maybe consider updating your original answer on exactly the same question. Then we can close this question here as a duplicate, and I will delete my answer. – Hermann Gruber May 31 '23 at 09:37
  • 2
    I guess that could work! I can mention your comment that inclusion is equivalent to intersection non-emptiness for two DFA's. – Michael Wehar May 31 '23 at 19:29
  • 1
    So that it's more clear that this question is related / nearly duplicated. – Michael Wehar May 31 '23 at 19:30
  • 1
    Cool! Thank you again! :) – Michael Wehar May 31 '23 at 19:31
  • Turns out I cannot delete an accepted answer. – Hermann Gruber Jun 01 '23 at 12:53
  • Small point, for the lowerbound the reduction should probably be vice-versa, e.g. we can solve intersection non-emptiness by checking the subset of A_1 with the negation of A_2. – Janmar Jun 01 '23 at 15:02
  • 1
    Also, I think for this scenario a direct argument is possible without traversing through the simulation of turing machines, by constructing two automata of size $poly(k)*2^{k/2}$ for which the interesection is non-empty iff the sat formula is satisfiable. But maybe I haven't thought it through completely. – Janmar Jun 01 '23 at 15:06
  • 1
    Yes, direct reductions are possible! I provided a few direct reductions from SAT to restricted versions of the intersection non-emptiness problem in section 7.2.3 of my thesis. – Michael Wehar Jun 02 '23 at 07:24