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 mn1

; for the unambiguous concatenation, it is known to be m2n12n2
(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 382n+1
. In the case of a unary alphabet, disjoint union requires up to 12mn
states, unambiguous concatenation has state complexity m+n2
, and unambiguous star requires n2
states in the worst case.

Fichier principal
Vignette du fichier
470153_1_En_16_Chapter.pdf (395) 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⟩
98 View
115 Download

Altmetric

Share

  • More