On the power of 2-way probabilistic finite state automata

Abstract

The recognition power of two-way probabilistic finite-state automata (2pfas) is studied. It is shown that any 2pfa recognizing a nonregular language must use exponential expected time infinitely often. The power of interactive proof systems (IPSs) where the verifier is a 2pfa is also investigated. It is shown that (1) IPSs in which the verifier uses private randomization are strictly more powerful than IPSs in which the random choices of the verifier are made public to the prover. (2) IPSs in which the verifier uses public randomization are strictly more powerful than 2pfas alone, that is, without a prover; (3) every language accepted by some deterministic Turing machine in exponential time can be accepted by some IPS. Other results concern IPSs with 2pfa verifiers that run in polynomial expected time.