# Parameterized complexity of inclusion of regular languages

I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed alphabet $\Sigma$, with the operations union, Kleene-star and concatenation.)

Input: Two regular expressions $E_1$ and $E_2$
Question: Is it true that $L(E_1)\subseteq L(E_2)$?

REGULAR LANGUAGE INCLUSION is known to be PSPACE-complete [1].

The classic way to solve it (in PSPACE) is to construct the NFAs $A_1$ and $A_2$ associated to $E_1$ and $E_2$, to build a DFA $D_2$ from $A_2$, complement it into a DFA $D_2^C$, and finally, build the intersection automaton $A_P$ from $A_1$ and $D_2^C$ corresponding to the intersection of $L(E_1)$ and $L(E_2)^C$. Now $L(E_1)\subseteq L(E_2)$ if and only if there no an accepting path in $A_P$.

If I am not mistaken, the whole process can be done in polynomial time when $E_2$ is a fixed language, since the only exponential blow-up comes from transforming $A_2$ into $D_2$. Even better, the problem is FPT when parameterized by $|E_2|$, the length of $E_2$.

This motivates my question:

Question: When $E_1$ is a fixed expression, what is the complexity of REGULAR LANGUAGE INCLUSION? Does it remain PSPACE-complete?

[1] L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: preliminary report. Proceedings of the fifth annual ACM Symposium on Theory of Computing, STOC '73, pp. 1-9.

Remark: Being a non-expert in the field, I find [1] (and related papers of that time) quite unreadable, and couldn't find another proof of the PSPACE-completeness - any pointer to a modern proof, such as in a book, is very welcome! Also, the authors seem to allow squaring in their regular expressions, which is nowadays rather non-standard, I believe.)

• It remains PSPACE-complete, as language universality (i.e. E1=Sigma*) is PSPACE-complete. Feb 22, 2018 at 15:57
• Btw allowing squaring makes the problem EXPSPACE-complete, the results you mentioned are without squaring. Feb 22, 2018 at 15:59
• For $E_1 = \emptyset$, it is solvable in constant time. For $E_1 = w$ for a fixed string $w$, it is solvable in polynomial time. For $E_1 = \Sigma^{*}$ it is PSPACE-complete. Does there exist an $E_1$ such that the problem is $NP$-complete? Feb 22, 2018 at 23:05
• OK, thanks! @Denis, please turn it into an answer (with a reference), and I'll accept it! Feb 23, 2018 at 10:04
• @MichaelWehar: Some coNP-complete cases are proved here, (doi.org/10.1137/080743457) but they are not for fixed languages (but for very restricted classes of languages) Feb 23, 2018 at 12:05

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$.

It is indeed hard to find a modern readable PSPACE-hardness proof for regular expression universality, as it is now considered folklore. Here is a quick proof scheme that allows you to rebuild the proof:

Consider a Turing Machine $M$ on alphabet $\Sigma$ using polynomial space $p(n)$, and let $w\in\Sigma^*$ be an input word for $M$. We will build a regular expression $e$ that accepts all words if and only if $M$ has no accepting run on $w$.

Consider the language $L_M$ consisting of words of the form $\$C_0\$C_1\$\dots\$C_f\$$, where each C_i is a configuration of M of length exactly p(n), C_0 is the initial configuration with w on the tape, C_f is accepting, and each C_i\to C_{i+1} is a valid transition of M. A word in L_M describes an accepting run of M. We build e on alphabet \Sigma'=\Sigma\cup\{\\} such that e accepts exactly words that are not in L_M, by looking for a violation of the definition of L_M. The expression e will be a big disjunction e_1+e_2+\dots+e_k, where each e_i looks for a different kind of violation. For instance$$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$looks for a violation of the fact that each C_i has size exactly p(n). The most tricky part is guessing a violation between C_i and C_{i+1}: the expression can compare a local pattern in C_i and its image in C_{i+1}, using t(\Sigma')^{p(n)}t', where t and t' are expressions for local patterns. With this we can guess a violation of the transition function of M on a local pattern, or a violation of the identity outside of this pattern. In the end, we obtain that$$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if$M$accepts }w$$therefore we reduced (polynomially) an arbitrary PSPACE problem to universality of a regular expression. I left out some details, but this should allow you to build a complete proof. Of course, as pointed out by Michael Wehar in the comments, for others$E_1$the problem can become simpler. Classifying the complexity of this problem has been studied extensively in this paper [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in this answer (there does exist NP-complete cases). As for your remark on squaring: allowing squaring in regular expressions make the inclusion and universality problem EXPSPACE-complete [2]. Remark that this can be seen in the proof scheme above, since$(\Sigma')^{p(n)}$can now be expressed with a logarithmic-size expression in$p(n)$using its binary decomposition, so we can go up to an exponential$p(n)\$ while keeping the size of the expression polynomial.

[1] On the equivalence, containment, and covering problems for the regular and context-free languages Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Journal of Computer and System Sciences. Volume 12, Issue 2, April 1976, Pages 222-268

[2] The equivalence problem for regular expressions with squaring requires exponential space. Meyer, A.R. and L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

• Wow, thank you very much for sharing the references!! This is neat!! :) Feb 24, 2018 at 1:21
• A colleague of mine pointed me to the following survey that deals with this type of regular language and automata problems, and contains further useful references: sciencedirect.com/science/article/pii/S0890540110001999 Feb 25, 2018 at 11:26