An alternating hierarchy for finite automata

We study the polynomial state complexity classes 2Σk and 2Π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Σk−1 and 2Πk−1 are proper subsets of 2Σk and of 2Πk, since the conversion of a one-way Σk- or Πk-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires 2n/4−O(k) states. The same exponential blow-up is required for converting a Σk-bounded 2Afa into a Πk-bounded 2Afa and vice versa, that is, 2Σk and 2Πk are incomparable. In the case of Σk-bounded 2Afas, the exponential gap applies also for intersection, while in the case of Π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.]