<p>If you are allowed to use complementation to express $\Sigma^*$ as $\emptyset^{C}$, the resulting language class includes the pattern languages (see, e.g., <a href="http://research.cs.queensu.ca/home/ksalomaa/julk/patkirj.ps" rel="nofollow">this survey</a> by Kai Salomaa).</p>

<p>As shown by <a href="http://dx.doi.org/10.1016/0022-0000(80)90041-0" rel="nofollow">Angluin</a>, the membership problem for pattern languages is NP-complete. (This holds even if you consider pattern languages that are generated by patterns that do not contain terminal symbols.)</p>

<p>So, membership for this class is as hard as for the full class of regular expressions with backreferences.</p>

CC BY-SA 3.0
2014-12-14T22:53:07.633Z
Great answer! In addition, I think you do not need the complementation to express $\Sigma^*$ if you use instead a union-free expression such as $(a^*b^*)^*$ (binary alphabet), $(a^*b^*c^*)^*$ (ternary alphabet), and so on.
Hermann Gruber
CC BY-SA 3.0
2011-09-13T14:09:14.163Z
2011-09-13T14:09:14.163Z
Dominik D. Freydenberger
<p>As a follow-up to my question <a href="https://cstheory.stackexchange.com/q/8153/962">Regular expressions without alternation</a>, I was wondering what was known about the power of regular expressions in which union is not allowed but backreferences are.</p>

<p>I'm familiar with a number of papers discussing regular expressions with the addition of backreferences, but none that I've seen address the union-free version. This class would be incomparable with the class of regular languages, but are they as hard to recognize as full regular expressions with backreferences?  (I've seen several terms used for this; none seem to be standard.)  In the case without backreferences, removing union seems to reduce expressibility without making membership tests much/any faster.</p>

<p>As before union means the same as alternation, logical OR, | (in standard regexes), / (ABNF), ∪, etc.</p>

CC BY-SA 3.0
2011-09-13T09:49:17.603Z
Do you still allow complementation? For example, could one use $\emptyset^{C}$ to express $\Sigma^*$?
Dominik D. Freydenberger
CC BY-SA 3.0
2011-09-13T13:01:57.643Z
@Dominik: I'd take either answer.
Charles
<fl.formal-languages><regular-expressions>
Regular expressions without union but with backreferences
Charles
# Regular expressions without union but with backreferences

(Asked by: username_0 on 2011-09-12)

As a follow-up to my question [Regular expressions without alternation](https://cstheory.stackexchange.com/q/8153/962), I was wondering what was known about the power of regular expressions in which union is not allowed but backreferences are.

I'm familiar with a number of papers discussing regular expressions with the addition of backreferences, but none that I've seen address the union-free version. This class would be incomparable with the class of regular languages, but are they as hard to recognize as full regular expressions with backreferences? (I've seen several terms used for this; none seem to be standard.) In the case without backreferences, removing union seems to reduce expressibility without making membership tests much/any faster.

As before union means the same as alternation, logical OR, | (in standard regexes), / (ABNF), ∪, etc.

**Tags:** fl.formal-languages, regular-expressions

> **Comments:**
> **username_1**: Do you still allow complementation? For example, could one use $\emptyset^{C}$ to express $\Sigma^*$?  
> **username_0**: @Dominik: I'd take either answer.  

---

## 1 answers

### Answer by username_1 on 2011-09-13. Score: 7

If you are allowed to use complementation to express $\Sigma^\*$ as $\emptyset^{C}$, the resulting language class includes the pattern languages (see, e.g., [this survey](http://research.cs.queensu.ca/home/ksalomaa/julk/patkirj.ps) by Kai Salomaa).

As shown by [Angluin](http://dx.doi.org/10.1016/0022-0000(80)90041-0), the membership problem for pattern languages is NP-complete. (This holds even if you consider pattern languages that are generated by patterns that do not contain terminal symbols.)

So, membership for this class is as hard as for the full class of regular expressions with backreferences.

> **Comments:**
> **username_2**: Great answer! In addition, I think you do not need the complementation to express $\Sigma^*$ if you use instead a union-free expression such as $(a^*b^*)^*$ (binary alphabet), $(a^*b^*c^*)^*$ (ternary alphabet), and so on.  

---

