Invited Talk (Computer Science)

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 2n/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.