Union-Complexities of Kleene Plus Operation

Abstract

Union-free expressions are used in union normal form to decompose any regular language to a finite union of union-free languages. Based on the automata characterisation of the union-free languages, by restricting the 1CFPAs not to have transitions by the empty word, or to be deterministic, the n-union-free and the deterministic union-free languages are defined. Union-complexity as a measure of descriptional complexity of regular languages was introduced recently. By the minimum number of union-free/n-union-free/deterministic union-free languages needed to get a regular language as their union, its union-complexity/nunion-complexity/d-union-complexity is defined. It is already known that union-complexity and n-union-complexity are finite for every regular language, however there are regular languages with infinite d-unioncomplexity. Operational union-complexity, that is, to predict the unioncomplexity of a language obtained by a language operation from languages with known union-complexity is an important and interesting question belonging to the field of descriptional complexity of formal systems. In the present paper, the Kleene plus, the positive Kleene closure operator is studied. As the Kleene star and plus operations have very different effects on the union-free languages, it is an interesting problem to investigate how the union-complexities may change under this operation. In particular, we show that the union-complexity of a regular language is not growing when this operation is being applied on it. On the other hand, the n-union-complexity of the Kleene plus of an n-unionfree language remains 1, but the n-union-complexity of the Kleene plus of other regular languages may grow. Further, the deterministic unioncomplexity may jump to an infinite value even if the original language had a relatively small deterministic union-complexity, e.g., 4.