An alternating hierarchy for finite automata

Abstract: We study the polynomial state complexity classes 2 and 2, 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 alternations between existential and universal states, starting in an existential or universal state, respectively. This hierarchy is infinite: for , both 2 and 2 are proper subsets of 2 and of 2, since the conversion of a one-way - or -alternating automaton with states into a two-way automaton with a smaller number of alternations requires states. The same exponential blow-up is required for converting a -bounded 2Afa into a -bounded 2Afa and vice versa, that is, 2 and 2 are incomparable. In the case of -bounded 2Afas, the exponential gap applies also for intersection, while in the case of -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.] [Copyright &y& Elsevier]