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 deterministic finite automaton 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 binary deterministic witness for square with 2(n) states where half of them are final, we get the tight upper bounds 2(n) + n + 1 and 2(n) + n on the complexity of the square operation on alternating and Boolean automata, respectively.