State Complexity of Unambiguous Operations on Deterministic Finite Automata - Descriptional Complexity of Formal Systems
Conference Papers Year : 2018

State Complexity of Unambiguous Operations on Deterministic Finite Automata

Galina Jirásková
  • Function : Author
  • PersonId : 1011781
Alexander Okhotin
  • Function : Author
  • PersonId : 1024589

Abstract

The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is $$mn-1$$; for the unambiguous concatenation, it is known to be $$m2^{n-1} - 2^{n-2}$$ (Daley et al. “Orthogonal concatenation: Language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be $$\frac{3}{8}2^n+1$$. In the case of a unary alphabet, disjoint union requires up to $$\frac{1}{2}mn$$ states, unambiguous concatenation has state complexity $$m+n-2$$, and unambiguous star requires $$n-2$$ states in the worst case.
Fichier principal
Vignette du fichier
470153_1_En_16_Chapter.pdf (395.38 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01905641 , version 1 (26-10-2018)

Licence

Identifiers

Cite

Galina Jirásková, Alexander Okhotin. State Complexity of Unambiguous Operations on Deterministic Finite Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.188-199, ⟨10.1007/978-3-319-94631-3_16⟩. ⟨hal-01905641⟩
83 View
106 Download

Altmetric

Share

More