Regular expressions without union but with backreferences 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.
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.