Properties of multihead two-way probabilistic finite automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata with log-space constructible transition probabilities and describe a technique to simulate these automata by standard log-space probabilistic Turing machines. Next we represent log-space probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and show their (deterministic log-space) reducibility to the second levels of these hierarchies. We relate the number of heads of a multihead probabilistic finite automaton to the bandwidth of its configuration transition matrix for an input string; partially based on this relation we find an apparently easier log-space complete problem for PL (the class of languages recognized by log-space unbounded-error probabilistic Turing machines), and explore possibilities for a space-efficient deterministic simulation of probabilistic automata