9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what does alternation mean ? also, it's "Kleene". $\endgroup$ – Suresh Venkat Sep 9 '11 at 16:15
  • 1
    $\begingroup$ @Suresh Venkat: Union, logical OR, |, /, ∪. $\endgroup$ – Charles Sep 9 '11 at 16:26
  • $\begingroup$ Note that in the original context, the class doesn't have complement but does have backreferences. $\endgroup$ – Peter Taylor Sep 10 '11 at 6:20
  • $\begingroup$ @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. $\endgroup$ – Charles Sep 11 '11 at 5:55
12
$\begingroup$

The class of regular languages that can be described by regular expressions without union (and without complementation) are known as union-free regular (also: star-dot regular) languages. This class of languages apparently has received some attention recently:

Benedek Nagy: "Union-free regular languages and 1-cycle-free-path-automata", Publicationes Mathematicae 68(1-2), 2006.

Sergey Afonin and Denis Golomazov: "Minimal Union-Free Decompositions of Regular Languages", Language and Automata Theory and Applications, Springer 2009.

Galina Jirásková and Tomás Masopust: "Complexity in Union-Free Regular Languages", Developments in Language Theory, Springer 2010.

$\endgroup$
  • 1
    $\begingroup$ Nice. Is anything known about the additional power from complementation? $\endgroup$ – Charles Sep 9 '11 at 16:36
  • 1
    $\begingroup$ Short nitpicky correction: The paper by Afonin and Golomazov appeared at LATA 2009, not DLT 2009. $\endgroup$ – Dominik D. Freydenberger Sep 13 '11 at 15:39

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.