An alternating hierarchy for finite automata

DOI10.1016/J.TCS.2012.04.044MaRDI QIDQ442279zbMATH OpenOpenAlexFDO

Publication date 10 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.04.044

alternating automata complexity classes descriptional complexity regular languages two-way atutomata

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Review text

Many variants of finite automata have been proposed in the literature (one-way/two-way, deterministic/nondeterministic/alternating). While all these variants characterize the class of regular languages, they reveal important differences from the point of view of the succinctness of the descriptions. For example, it is well known that each one-way nondeterministic automaton (1NFA) with \(n\) states can be simulated by an equivalent one-way deterministic automaton (1DFA) with \(2^n\) states and that this cost cannot be reduced. In other words, this means that there are regular languages for which the description by 1DFAs is exponentially larger than the description by 1NFAs.NEWLINENEWLINEA relevant question in this area was posed in 1978 by \textit{W. J. Sakoda} and \textit{M. Sipser} [``Nondeterminism and the size of two way finite automata, in: Proceedings of the 10th annual ACM symposium on theory of computing (STOC1978). New York, NY: ACM. 275--286 (1978)]: they conjectured that the state cost of the conversion of two-way nondeterministic automata (2NFAs) into equivalent two-way deterministic automata (2DFAs) is exponential. In spite all attempts, this problem is still open. In the same paper, the authors reformulated the same problem in terms of complexity classes, by introducing the classes 2D and 2N of families of regular languages accepted by polynomial size 2DFAs and 2NFAs, respectively. They show a perfect analogy of the question 2D vs 2N with the question P vs NP. Following the same approach, in 2009, \textit{C. A. Kapoutsis} [Lect. Notes Comput. Sci. 5583, 47--66 (2009; Zbl 1247.68146)] proposed the investigation of other complexity classes definable by families of finite automata (see also [\textit{C. A. Kapoutsis}, Lect. Notes Comput. Sci. 7386, 20--42 (2012; Zbl 1304.68108)]). In particular, by emphasizing the analogy with the polynomial-time hierarchy, he proposed the investigation of classes defined by alternating automata, with a fixed numbers alternations, which is the subject of this paper. Let \(2\Sigma_k\) and \(2\Pi_k\) be the classes of families of languages accepted by two-way alternating finite automata (2AFAs), making at most \(k-1\) alternations between existential and universal states, and starting with an existential or a universal state, respectively. In this paper it is proved that this hierarchy is infinite: in fact, for \(k\geq 2\), both \(2\Sigma_{k-1}\) and \(2\Pi_{k-1}\) are properly contained in \(2\Sigma_k\) and \(2\Pi_k\). Furthermore, for \(k\geq 2\), \(2\Sigma_k\) and \(2\Pi_k\) are incomparable. We remind the reader that similar questions for the polynomial-time hierarchy are open.NEWLINENEWLINEWhat about the low level \(k=1\)? \(2\Sigma_1\) and \(2\Pi_1\) are defined by 2AFAs making only existential or universal choices, respectively. The relationships between these classes are left open on the paper. Furthermore, 2AFAs making only existential choices are 2NFAs. Hence, the investigation of the case \(k=1\) is immediately connected to the open question of Sakoda and Sipser.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: An alternating hierarchy for finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442279)