<p>It is well-known that <em>star-free regular expressions</em>, which are defined by the grammar</p>

<p>$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$</p>

<p>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".</p>

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

<p>$r::= a \mid r \cdot \Sigma^+ \mid \Sigma^+\cdot r \mid r \cup r \mid \neg r \mid\varepsilon \mid \emptyset$</p>

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

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

CC BY-SA 4.0
2018-05-06T16:57:38.767Z
Just a note: **both** left- and right-extensions must be present! Not just one of them!
Alberto M.
CC BY-SA 4.0
2018-05-07T17:24:31.857Z
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
Alberto M.
CC BY-SA 4.0
2018-05-10T10:35:12.633Z
**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).
Alberto M.
CC BY-SA 4.0
2018-05-11T12:53:31.903Z
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.
Alberto M.
<cc.complexity-theory><reference-request><regular-expressions>
Regular expressions of prefixes/suffixes
Alberto M.
# Regular expressions of prefixes/suffixes

(Asked by: username_0 on 2018-05-06)

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.

**Tags:** cc.complexity-theory, reference-request, regular-expressions
> **Comments:**
> **username_0**: Just a note: **both** left- and right-extensions must be present! Not just one of them!  
> **username_0**: 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  
> **username_0**: **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).  
> **username_0**: 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.  

---

## 0 answers

