Alternation in two-way finite automata

• Type: Article in International Scientific Journal
• Date: 2021

Authors

Konstantinidis, S (Author) Other; Nelma Moreira (Author) FCUP; Rogério Reis (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 870

Pages: 103-120

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 2 Citations

Other information

Authenticus ID: P-00T-9R6

DOI: 10.1016/j.tcs.2020.12.029

Abstract (EN): The study of alternation in two-way finite automata (2FAs) has been quite non-systematic. Since the 1970 & rsquo;s, various authors with a variety of motivations have studied 2FAs 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 (2BFAs); monotone 2BFAs; basic 2BFAs; and (monotone basic, or) alternating 2BFAs (2AFAs). 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 modeled by a circuit of Boolean gates; the formula view, where computation is modeled 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 & ldquo;runs & rdquo;; and the (most classic) tree view, where computation is modeled by a tree of configurations. After carefully defining each 2BFA 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 2BFAs are equivalent: although general 2BFAs are as powerful as monotone 2BFAs, and basic 2BFAs are as powerful as 2AFAs (up to polynomial differences in the number of states), general 2BFAs may need exponentially fewer states than 2AFAs. (c) 2020 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18