State Complexity of Unambiguous Operations on Deterministic Finite Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

State Complexity of Unambiguous Operations on Deterministic Finite Automata

Galina Jirásková
  • Fonction : Auteur
  • PersonId : 1011781
Alexander Okhotin
  • Fonction : Auteur
  • PersonId : 1024589

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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⟩
56 Consultations
72 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More