On some variations of two-way probabilistic finite automata models

摘要

Rabin [M. Rabin, Probabilistic finite automata, Information and Control (1963) 230–245] initiated the study of probabilistic finite automata (pfa). Rabin’s work showed a crucial role of the gap in the error bound (for accepting and non-accepting computations) in the power of the model. Further work resulted in the identification of qualitatively different error models (one-sided error, bounded and unbounded errors, no error etc.) Karpinski and Verbeek [M. Karpinski, R. Verbeek, There is no polynomial deterministic simulation of probabilistic space with two-way random-tape generator, Information and Control 67 (1985) 158–162] and Nisan [N. Nisan, On read-once vs. multiple access to randomness in logspace, in: Proc. of Fifth IEEE Structure in Complexity Theory, Barcelona, Spain, 1990, pp. 179–184] studied a model of probabilistic automaton in which the tape containing random bits can be read by a two-way head. They presented results comparing models with one-way vs. two-way access to randomness. Dwork and Stockmeyer [C. Dwork, L. Stockmeyer, Interactive proof systems with finite state verifiers, IBM Report RJ 6262, 1988] and Condon et al. [A. Condon, et al., On the power of finite automata with both nondeterministic and probabilistic states, SIAM Journal on Computing (1998) 739–762] studied a model of 2-pfa with nondeterministic states (2-npfa). In this paper, we present some results about the above mentioned variations of probabilistic finite automata, as well as a model of 2-pfa augmented with a pebble studied in [B. Ravikumar, Some observations on two-way probabilistic finite automata, in: Proc. of the Foundations of Software Technology and Theoretical Computer Science, 1992, pp. 392–403]. Our observations indicate that these models exhibit subtle variations in their computational power. We also mention many open problems about these models. Complete characterizations of their power will likely provide deeper insights about the role of randomness in space-bounded computations.