%0 Conference Proceedings
%T Union-Freeness, Deterministic Union-Freeness and Union-Complexity
%+ Eastern Mediterranean University (EMU)
%A Nagy, Benedek
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 46-56
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_3
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387293/document
%2 https://inria.hal.science/hal-02387293/file/480958_1_En_3_Chapter.pdf
%L hal-02387293
%U https://inria.hal.science/hal-02387293
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612