Square on Deterministic, Alternating, and Boolean Finite Automata

We investigate the state complexity of the square operation on languages represented by deterministic, alternating, and Boolean automata. For each k such that 1 <= k <= 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.