On union-complexity of regular languages
Benedek Nagy · 2010
Regular expressions can be represented by expression tree and by flow diagram (syntax graph). Based on equivalences a possible normal form can be obtained. It has interesting properties in both graphical representations. The union-complexity of languages is defined. The union-complexity is 1 for the union-free languages. These languages can be given by regular expressions without the operation union. Some properties of them are described. There is an analogy with the star-free languages and the star-height problem of regular languages. We show that each regular language has finite union-complexity based on its description by a finite union of union-free languages (union normal-form). For some special language classes, for instance for finite languages the union complexity is easily computed. For union-complexity of any regular languages lower and upper bounds are presented. This measure gives an infinite hierarchy of regular languages. The union-height can be defined and proved to be at most 1 allowing n-ary unions.