11
$\begingroup$

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.)

$\endgroup$
  • 4
    $\begingroup$ It remains PSPACE-complete, as language universality (i.e. E1=Sigma*) is PSPACE-complete. $\endgroup$ – Denis Feb 22 '18 at 15:57
  • 3
    $\begingroup$ Btw allowing squaring makes the problem EXPSPACE-complete, the results you mentioned are without squaring. $\endgroup$ – Denis Feb 22 '18 at 15:59
  • 1
    $\begingroup$ 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? $\endgroup$ – Michael Wehar Feb 22 '18 at 23:05
  • 2
    $\begingroup$ OK, thanks! @Denis, please turn it into an answer (with a reference), and I'll accept it! $\endgroup$ – Florent Foucaud Feb 23 '18 at 10:04
  • 3
    $\begingroup$ @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) $\endgroup$ – Florent Foucaud Feb 23 '18 at 12:05
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, thank you very much for sharing the references!! This is neat!! :) $\endgroup$ – Michael Wehar Feb 24 '18 at 1:21
  • 2
    $\begingroup$ 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 $\endgroup$ – Florent Foucaud Feb 25 '18 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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