6533b7cffe1ef96bd1258357

RESEARCH PRODUCT

One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata

Kaspars Balodis

subject

Discrete mathematicsNested wordDeterministic finite automatonContinuous spatial automatonAutomata theoryQuantum finite automataNondeterministic finite automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata TheoryMobile automatonMathematics

description

We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.

yearjournalcountryeditionlanguage
2013-01-01
https://doi.org/10.1007/978-3-642-40164-0_7