Alternating hierarchy and state complexity of two-way automata

prof. RNDr. Viliam Geffert, DrSc.
Institute of Computer Science,

PF UPJŠ, Košice, Slovakia

## Abstract

We shall consider the classes of language families that can be recognized by two-way alternating finite automata (2AFAs) with a polynomial number of states making fewer than *k* alternations between existential and universal states, starting in an existential or universal state, respectively. Such language classes are denoted by 2Σ_{k} and 2Π_{k} in the literature, where *k=1,2,3,…*. We show that this hierarchy is infinite: for each k≥2, both 2Σ_{k-1} and 2Π_{k-1} are proper subsets of 2Σ_{k} and of 2Π_{k}. The conversion of a one-way 2Σ_{k} or Π_{k}-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires, in the worst case, at least 2^{n/4-k/4-3/2}-1 states. The same exponential blow-up is required for converting a Σ_{k}-alternating 2AFA into a Π_{k}-alternating 2AFA or vice versa, that is, the state complexity classes 2Σ_{k} and 2Π_{k} are incomparable. In the case of Σ_{k}-alternating 2AFAs, the exponential gap applies also for intersection, while for Π_{k}-alternating 2AFAs for union. The same hierarchy results are established for one-way alternating finite automata.