6533b7d8fe1ef96bd126a1ff

RESEARCH PRODUCT

Weak and strong recognition by 2-way randomized automata

Rusins FreivaldsAndris AmbainisMarek Karpinski

subject

Deterministic pushdown automatonCombinatoricsDeterministic automatonProbabilistic automatonPushdown automatonQuantum finite automataBüchi automatonTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Computational ComplexityComputer Science::Formal Languages and Automata TheoryMathematics

description

Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular.

yearjournalcountryeditionlanguage
1997-01-01
https://doi.org/10.1007/3-540-63248-4_15