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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.