# Is DFA language inclusion decidable in quasi-linear time? [duplicate]

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?

## 1 Answer

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

• 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. Commented May 25, 2023 at 15:00
• 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$. Commented May 30, 2023 at 8:53
• 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. Commented May 30, 2023 at 8:55
• I just noticed that this question was answered 8 years ago by @MichaelWehar. Michael, I should have tagged you on this question :-) Commented May 30, 2023 at 13:50
• I guess that could work! I can mention your comment that inclusion is equivalent to intersection non-emptiness for two DFA's. Commented May 31, 2023 at 19:29