It is well-known that star-free regular expressions, which are defined by the grammar

$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$

where $a$ belongs to a finite alphabet $\Sigma$ and $\varepsilon$ is the empty string, have their language-emptiness problem which is non-elementary (more precisely, tower-complete), being negation the "difficult case".

However, what can we say about the same problem for this kind of regular expressions?

$r::= a \mid r \cdot \Sigma^+ \mid \Sigma^+\cdot r \mid r \cup r \mid \neg r \mid\varepsilon \mid \emptyset$

Here, we still have negation, and still no Kleene star, as $\Sigma^+$ can be "rewritten" as $\neg(\emptyset \cup \varepsilon)$, but concatenation is weakened: in fact, $r \cdot \Sigma^+$ and $\Sigma^+\cdot r$ represent right-/left-extensions of $r$ with any (non-empty) string.

Does anybody know the complexity of this problem? Is it elementary? Do you know similar problems/connected literature? Thanks.

  • 1
    $\begingroup$ Just a note: both left- and right-extensions must be present! Not just one of them! $\endgroup$ – Alberto M. May 6 '18 at 16:57
  • 1
    $\begingroup$ Using alternating automata over finite words, it is easy to prove PSPACE membership of emptiness, if only one of right or left-extensions is present $\endgroup$ – Alberto M. May 7 '18 at 17:24
  • 1
    $\begingroup$ EXPSPACE-hardness of the problem can be proved, by a reduction from domino-tiling with rows of exponential length (we encode rows by concatenating them, and add binary column counters to enforce vertical adjacency contraints). $\endgroup$ – Alberto M. May 10 '18 at 10:35
  • 1
    $\begingroup$ I have tried to prove non-elementarity (tower-hardness) by encoding the nested Turing machine computations à là Meyer&Stockmeyer, but it works only at the first level (EXPSPACE-hardness). It fails to encode "movable" rulers. $\endgroup$ – Alberto M. May 11 '18 at 12:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.