https://hal.inria.fr/hal-01657005Krajňáková, IvanaIvanaKrajňákováSAS - Slovak Academy of SciencesJirásková, GalinaGalinaJiráskováSAS - Slovak Academy of SciencesSquare on Deterministic, Alternating, and Boolean Finite AutomataHAL CCSD2017[INFO] Computer Science [cs]Ifip, HalGiovanni PighizziniCezar Câmpeanu2017-12-06 11:44:022017-12-06 14:14:192017-12-06 13:46:20enConference papershttps://hal.inria.fr/hal-01657005/document10.1007/978-3-319-60252-3_17application/pdf1We 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.