An Alternating Hierarchy for Finite Automata.
Viliam Geffert · NCMA · 2011
We study the polynomial state complexity classes 2@Sk and 2@Pk, 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@Sk-1 and 2@Pk-1 are proper subsets of 2@Sk and of 2@Pk, since the conversion of a one-way @Sk- or @Pk-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 @Sk-bounded 2Afa into a @Pk-bounded 2Afa and vice versa, that is, 2@Sk and 2@Pk are incomparable. In the case of @Sk-bounded 2Afas, the exponential gap applies also for intersection, while in the case of @Pk-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.]