Space-Efficient Deterministic Simulation of Probabilistic Automata

摘要

Given a description of a probabilistic automaton (one-head probabilistic finiteautomaton or probabilistic Turing machine) and an input string x of length n, we ask how much space does a deterministic Turing machine need in order to decide the acceptance of an input string by that automaton. The question is interesting even in the case of one-head one-way probabilistic finite automata. We call (rational) stochastic languages (S(sup greater than)(sub rat)) the class of languages recognized by these devices with rational transition probabilities and rational cutpoint. The class S(sup greater than)(sub rat) contains context-sensitive languages that are not context free, but on the other hand there are context-free languages not included in S(sup greater than)(sub rat). Our main results are as follows: (1) The (proper) inclusion of S(sup greater than)(sub rat) in Dspace(log n), which is optimal. The previous upper bounds were Dspace(n), and, in a special case, Dspace(log n loglog n). (2) The inclusion of the languages recognized by S(n) belonging to o(logloglog n) space-bounded probabilistic Turing machines in Dspace(2(exp S(n))log n). The previous upper bound was Dspace(log n(S(n)+log log n)). (Note that this improvement is meaningful, based on Freivalds' result that probabilistic Turing machines do not have a space complexity gap below loglog n like their deterministic and nondeterministic counterparts) . We present a technique to compare numbers given in terms of their values modulo a sequence of primes, 3 less than or equal to (LE) p(sub 1) LE p(sub 2) LE ... LE p(sub n) = O(n(exp a)) (where a is some constant) in O(log n) deterministic space. The previous result was O(log n loglog n).