Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387293
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:35:50 PM
Last modification on : Friday, November 29, 2019 - 5:01:51 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

70