An alternating hierarchy for finite automata

We study the polynomial state complexity classes 2 Sigma(k) and 2 Pi(k), that is, the hierarchy of problems that can be solved with a polynomial number of states by two-way alternating finite automata (2AFAS) making at most k-1 alternations between existential and universal states, starting in an existential or universal state, respectively. This hierarchy is infinite: for k = 2, 3, 4, ... , both 2 Sigma(k-1) and 2 Pi(k-1) are proper subsets of 2 Sigma(k) and of 2 Pi(k), since the conversion of a one-way Sigma(k)- or Pi(k)-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires 2(n/4-O(k)) states. The same exponential blow-up is required for converting a Sigma(k)-bounded 2AFA into a Pi(k)-bounded 2AFA and vice versa, that is, 2 Sigma(k) and 2 Pi(k) are incomparable. In the case of Sigma(k)-bounded 2AFAS, the exponential gap applies also for intersection, while in the case of Pi(k)-bounded 2AFAS for union. The same results are established for one-way alternating finite automata. This solves several open problems raised in [C. Kapoutsis, Size complexity of two-way finite automata, in: Proc. Develop. Lang. Theory, in: Lect. Notes Comput. Sci., vol. 5583, Springer-Verlag, 2009. pp. 47-66.] (C) 2012 Elsevier B.V. All rights reserved.