Extended regular expressions of star degree at most two (Q921911): Difference between revisions

The paper introduces the star operator of degree two, a generalization of Kleene star in regular expressions. One investigates the family of languages obtained by a finite number of operations of union, concatenation, Kleene star and star operator of degree two, starting from finite languages. This family is incomparable with those of linear languages and of deterministic context-free languages, and it is equal to the family of completely linearly nested context-free languages. Closure and decision properties of this family are examined, too.