THE COMPUTATIONAL ADVANTAGE OF PROBABILISTIC AUTOMATA OVER DETERMINISTIC AUTOMATA IN HYPERBOLIC PLANE

摘要

In this paper, we address the question whether a probabilistic finite-state automaton (pfa) could recognize a language not recognizable by a deterministic finite-state automaton in polynomial time. We show that there is such a language in a hyperbolic plane and prove that a 5-way error-bounded pfa can recognize it in polynomial time of the number of nodes on the plane.