<p>EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis.</p>
<p><a href="https://cstheory.stackexchange.com/a/29166/2367">https://cstheory.stackexchange.com/a/29166/2367</a></p>
<p>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 &quot;no&quot;. <a href="https://rjlipton.wpcomstaging.com/2009/08/17/on-the-intersection-of-finite-automata/" rel="nofollow noreferrer">https://rjlipton.wpcomstaging.com/2009/08/17/on-the-intersection-of-finite-automata/</a></p>
<p>George Karakostas, Richard J. Lipton, Anastasios Viglas:
On the Complexity of Intersecting Finite State Automata. CCC 2000: 229-234</p>

CC BY-SA 4.0
2023-05-25T15:00:54.137Z
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
CC BY-SA 4.0
2023-05-26T09:27:55.043Z
@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
CC BY-SA 4.0
2023-05-26T09:32:48.227Z
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
CC BY-SA 4.0
2023-05-30T08:53:01.997Z
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
CC BY-SA 4.0
2023-05-30T08:55:01.147Z
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
CC BY-SA 4.0
2023-05-30T13:50:25.513Z
I just noticed that this question was answered 8 years ago by @MichaelWehar. Michael, I should have tagged you on this question :-)
Hermann Gruber
CC BY-SA 4.0
2023-05-30T15:34:24.633Z
@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
CC BY-SA 4.0
2023-05-30T21:48:14.320Z
@EmilJeřábek thanks for the hint!
Hermann Gruber
CC BY-SA 4.0
2023-05-30T23:07:13.503Z
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
CC BY-SA 4.0
2023-05-31T09:37:03.130Z
@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
CC BY-SA 4.0
2023-05-31T19:29:30.467Z
I guess that could work!  I can mention your comment that inclusion is equivalent to intersection non-emptiness for two DFA's.
Michael Wehar
CC BY-SA 4.0
2023-05-31T19:30:38.240Z
So that it's more clear that this question is related / nearly duplicated.
Michael Wehar
CC BY-SA 4.0
2023-05-31T19:31:13.700Z
Cool!  Thank you again!  :)
Michael Wehar
CC BY-SA 4.0
2023-06-01T12:53:45.383Z
Turns out I cannot delete an accepted answer.
Hermann Gruber
CC BY-SA 4.0
2023-06-01T15:02:03.820Z
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
CC BY-SA 4.0
2023-06-01T15:06:49.460Z
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
CC BY-SA 4.0
2023-06-02T07:24:11.293Z
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
CC BY-SA 4.0
2023-05-25T05:50:49.937Z
2023-05-30T13:56:08.330Z
2023-05-30T13:56:08.330Z
Hermann Gruber
<p>Given two DFAs <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span>, we want to decide whether <span class="math-container">$\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$</span>. Of course, one can compute whether <span class="math-container">$\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$</span>. However, the product automaton of <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span> can be quadratic in size.</p>
<p>This motivates my question: is there an algorithm that avoids this blow-up and matches the <span class="math-container">$\mathcal{O}(n\log~n)$</span> complexity of Hopcroft's minimization algorithm that decides language equivalence?</p>

<fl.formal-languages><complexity><dfa>
Is DFA language inclusion decidable in quasi-linear time?
Janmar
# Is DFA language inclusion decidable in quasi-linear time?

(Asked by: username_0 on 2023-05-23)

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?

**Tags:** fl.formal-languages, complexity, dfa

---

## 1 answers

### Answer by username_1 on 2023-05-25. Score: 9 | Accepted 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

> **Comments:**
> **username_0**: 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.  
> **username_1**: @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.  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_0**: 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.  
> **username_1**: I just noticed that this question was answered 8 years ago by @MichaelWehar. Michael, I should have tagged you on this question :-)  
> **username_2**: @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.  
> **username_1**: @EmilJeřábek thanks for the hint!  
> **username_3**: 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  
> **username_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.  
> **username_3**: I guess that could work!  I can mention your comment that inclusion is equivalent to intersection non-emptiness for two DFA's.  
> **username_3**: So that it's more clear that this question is related / nearly duplicated.  
> **username_3**: Cool!  Thank you again!  :)  
> **username_1**: Turns out I cannot delete an accepted answer.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: 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.  

---

