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.
https://hal.inria.fr/hal-02387293 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Friday, November 29, 2019 - 4:35:50 PM Last modification on : Friday, November 29, 2019 - 5:01:51 PM
Benedek Nagy. Union-Freeness, Deterministic Union-Freeness and Union-Complexity. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.46-56, ⟨10.1007/978-3-030-23247-4_3⟩. ⟨hal-02387293⟩