Result: On some variations of two-way probabilistic finite automata models
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Further Information
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.