10
$\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.

Improve this question
$\endgroup$
4
  • $\begingroup$ what does alternation mean ? also, it's "Kleene". $\endgroup$
    – Suresh Venkat
    Sep 9, 2011 at 16:15
  • 1
    $\begingroup$ @Suresh Venkat: Union, logical OR, |, /, ∪. $\endgroup$
    – Charles
    Sep 9, 2011 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, 2011 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, 2011 at 5:55

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice. Is anything known about the additional power from complementation? $\endgroup$
    – Charles
    Sep 9, 2011 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, 2011 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.