Probabilism versus Alternation for Automata

Autor:	Georg Schnitger
Rok vydání:	2018
Předmět:	Discrete mathematics Polynomial Computation Bounded function Contrast (statistics) Alternation (formal language theory) Probabilism Constant (mathematics) Automaton Mathematics
Zdroj:	Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications ISBN: 9783319125671 Adventures Between Lower Bounds and Higher Altitudes
DOI:	10.1007/978-3-319-98355-4_8
Popis:	We compare the number of states required for one-way probabilistic finite automata with a positive gap (1P\(_2\)FAs) and the number of states required for one-way alternating automata (1AFAs). We show that a 1P\(_2\)FA P can be simulated by 1AFA with an at most polynomial increase in the number s(P) of states of P, provided only inputs of length at most poly(s(P)) are considered. On the other hand we gather evidence that the number of states grows super-polynomially if the number of alternations is bounded by a fixed constant. Thus the behavior of one-way automata seems to be in marked contrast with the behavior of polynomial-time computations.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::bdc7dc28ea0b53d385d91817eee7d3b9 https://doi.org/10.1007/978-3-319-98355-4_8 Zobrazit plný text záznamu