Square on Deterministic, Alternating, and Boolean Finite Automata - Descriptional Complexity of Formal Systems (DCFS 2017) Access content directly
Conference Papers Year : 2017

Square on Deterministic, Alternating, and Boolean Finite Automata

Ivana Krajňáková
  • Function : Author
  • PersonId : 1024585
Galina Jirásková
  • Function : Author
  • PersonId : 1011781

Abstract

We investigate the state complexity of the square operation on languages represented by deterministic, alternating, and Boolean automata. For each k such that $1 \le k \le n-2$, we describe a binary language accepted by an n-state DFA with k final states meeting the upper bound $n2^n - k2^{n-1}$ on the state complexity of its square. We show that in the case of $k=n-1$, the corresponding upper bound cannot be met. Using the DFA witness for square with $2^n$ states where half of them are final, we get the tight upper bounds on the complexity of the square operation on alternating and Boolean automata.
Fichier principal
Vignette du fichier
440206_1_En_17_Chapter.pdf (113.25 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01657005 , version 1 (06-12-2017)

Licence

Attribution

Identifiers

Cite

Ivana Krajňáková, Galina Jirásková. Square on Deterministic, Alternating, and Boolean Finite Automata. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.214-225, ⟨10.1007/978-3-319-60252-3_17⟩. ⟨hal-01657005⟩
48 View
134 Download

Altmetric

Share

Gmail Facebook X LinkedIn More