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

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

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

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

CC BY-SA 3.0
2011-09-09T16:36:10.340Z
Nice.  Is anything known about the additional power from complementation?
Charles
CC BY-SA 3.0
2011-09-13T15:39:55.590Z
Short nitpicky correction: The paper by Afonin and Golomazov appeared at LATA 2009, not DLT 2009.
Dominik D. Freydenberger
CC BY-SA 3.0
2011-09-09T16:26:13.080Z
2011-09-14T18:06:23.970Z
2011-09-14T18:06:23.970Z
Hermann Gruber
<p>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.)</p>

<p>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.</p>

<p>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.</p>

<p>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?)</p>

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

<p>This question was inspired by <a href="https://math.stackexchange.com/q/62769/1778">Regular Expression question</a> on math.se.</p>

CC BY-SA 3.0
2011-09-09T16:15:54.507Z
what does alternation mean ? also, it's "Kleene".
Suresh Venkat
CC BY-SA 3.0
2011-09-09T16:26:00.700Z
@Suresh Venkat: Union, logical OR, |, /, ∪.
Charles
CC BY-SA 3.0
2011-09-10T06:20:08.827Z
Note that in the original context, the class doesn't have complement but does have backreferences.
Peter Taylor
CC BY-SA 3.0
2011-09-11T05:55:29.717Z
@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
<fl.formal-languages><regular-expressions>
Regular expressions without alternation
Charles
# Regular expressions without alternation

(Asked by: username_0 on 2011-09-09)

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](https://math.stackexchange.com/q/62769/1778) on math.se.

**Tags:** fl.formal-languages, regular-expressions
> **Comments:**
> **username_1**: what does alternation mean ? also, it's "Kleene".  
> **username_0**: @Suresh Venkat: Union, logical OR, |, /, ∪.  
> **username_2**: Note that in the original context, the class doesn't have complement but does have backreferences.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2011-09-09. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: Nice.  Is anything known about the additional power from complementation?  
> **username_4**: Short nitpicky correction: The paper by Afonin and Golomazov appeared at LATA 2009, not DLT 2009.  

---

