Union-Freeness, Deterministic Union-Freeness and Union-Complexity

Abstract

Union-free expressions are regular expressions without using the union operation. Consequently, union-free languages are described by regular expressions using only concatenation and Kleene star. The language class is also characterised by a special class of finite automata: 1CFPAs have exactly one cycle-free accepting path from each of their states. Obviously such an automaton has exactly one accepting state. The deterministic counterpart of such class of automata defines the deterministic union-free languages. A regular expression is in union (disjunctive) normal form if it is a finite union of union-free expressions. By manipulating regular expressions, each of them has equivalent expression in union normal form. By the minimum number of union-free expressions needed to describe a regular language, its union-complexity is defined. For any natural number n there are languages such that their union complexity is n. However, there is not known any simple algorithm to determine the union-complexity of any language. Regarding the deterministic union-free languages, there are regular languages such that they cannot be written as a union of finitely many deterministic union-free languages.