Union-Freeness, Deterministic Union-Freeness and Union-Complexity - Descriptional Complexity of Formal Systems
Conference Papers Year : 2019

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

Benedek Nagy
  • Function : Author
  • PersonId : 1059501

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.
Fichier principal
Vignette du fichier
480958_1_En_3_Chapter.pdf (280.54 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02387293 , version 1 (29-11-2019)

Licence

Identifiers

Cite

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⟩
51 View
83 Download

Altmetric

Share

More