# 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
Domain :
Complete list of metadata

https://hal.inria.fr/hal-01657005
Contributor : Hal Ifip Connect in order to contact the contributor
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)

### 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⟩

Record views