As a follow-up to my question Regular expressions without alternation, 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.

  • $\begingroup$ Do you still allow complementation? For example, could one use $\emptyset^{C}$ to express $\Sigma^*$? $\endgroup$ – Dominik D. Freydenberger Sep 13 '11 at 9:49
  • $\begingroup$ @Dominik: I'd take either answer. $\endgroup$ – Charles Sep 13 '11 at 13:01

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 by Kai Salomaa).

As shown by Angluin, 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Hermann Gruber Dec 14 '14 at 22:53

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.