Skip to Main content Skip to Navigation
Conference papers

Square on Deterministic, Alternating, and Boolean Finite Automata

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01657005
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:44:02 AM
Last modification on : Wednesday, December 6, 2017 - 2:14:19 PM

File

440206_1_En_17_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

83

Files downloads

76