# Regular expressions without alternation

I was wondering about what sets of languages are generated by restrictions of regular expressions. Supposing that all the restrictions have a constant symbol for each element of $\Sigma$ and concatenation. Then eight classes can be formed by the presence or absence of complement/negation, alteration/union, and the Kleene star. (Yes, 'normal' regular expressions don't have a $^C$ operator, but it's convenient here.)

Expressions allowing alternation and the Kleene star, with or without complement (what's a little double-exponential blowup amongst friends?), generate the regular languages. Expressions allowing alternation and complement but not the Kleene star generate the star-free languages. Expressions allowing alternation but not complement or the Kleene star generate the finite languages.

But can any interesting classes of languages be generated without alternation? Without any of the three operators all that can be generated is a single word. The complement operator doesn't help much here.

With just the Kleene star the class is somewhat interesting... it's not clear if they can be recognized any faster than regular languages. (Is anything nontrivial known about these?)

With both the Kleene star and complement... do you get anything interesting? Does this class have a name?

This question was inspired by Regular Expression question on math.se.

• what does alternation mean ? also, it's "Kleene". – Suresh Venkat Sep 9 '11 at 16:15
• @Suresh Venkat: Union, logical OR, |, /, ∪. – Charles Sep 9 '11 at 16:26
• Note that in the original context, the class doesn't have complement but does have backreferences. – Peter Taylor Sep 10 '11 at 6:20
• @Peter Taylor: Correct. I intend to ask a follow-up question on backreferences, but I thought it would be too much to fit into this question. – Charles Sep 11 '11 at 5:55