Alternation in two-way finite automata

The study of alternation in two-way finite automata ( 2 fa s) has been quite non-systematic. Since the 1970's, various authors with a variety of motivations have studied 2 fa s with various types of alternation and a variety of names, creating a fairly long list of sporadic contributions with little internal consistency. This article attempts to organize the subject into a single unifying framework. We start with a detailed account of all contributions to date, that reveals the large variety of approaches and the lack of consistency between them. We then identify and name four types of automata that these contributions have really studied over the years: general two-way Boolean finite automata ( 2 b fa s); monotone 2 b fa s; basic 2 b fa s; and (monotone basic, or) alternating 2 b fa s ( 2 a fa s). Next, we identify four different ways by which authors have described how such automata compute, each offering a distinct view onto their operation: the circuit view, where computation is modelled by a circuit of Boolean gates; the formula view, where computation is modelled by a Boolean formula over configuration-variables; the run view, where decisions are determined by the existence of appropriate trees of configuration-goal pairs, called “runs”; and the (most classic) tree view, where computation is modelled by a tree of configurations. After carefully defining each 2 b fa type and each view, we prove the following. First, that within each type, every two of the four views are equivalent to each other, in the strong sense that each of them closely mimics the other at every step of the computation. Second, that not all types of 2 b fa s are equivalent: although general 2 b fa s are as powerful as monotone 2 b fa s, and basic 2 b fa s are as powerful as 2 a fa s (up to polynomial differences in the number of states), general 2 b fa s may need exponentially fewer states than 2 a fa s.