Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Theoretical Computer...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Theoretical Computer Science
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Theoretical Computer Science
Article . 2012
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Theoretical Computer Science
Article . 2012 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2012
Data sources: zbMATH Open
DBLP
Article . 2012
Data sources: DBLP
versions View all 6 versions
addClaim

An alternating hierarchy for finite automata

Authors: Viliam Geffert;

An alternating hierarchy for finite automata

Abstract

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. A 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. What 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.

Keywords

two-way atutomata, Descriptional complexity, Formal languages and automata, Regular languages, Alternating finite automata, regular languages, complexity classes, Theoretical Computer Science, Complexity classes (hierarchies, relations among complexity classes, etc.), alternating automata, descriptional complexity, Computer Science(all)

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    18
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
18
Top 10%
Top 10%
Top 10%
hybrid