ON THE POWER OF FINITE AUTOMATA WITH BOTH NONDETERMINISTIC AND PROBABILISTIC STATES

We study finite automata with both nondeterministic and random states (npfa's). We restrict our attention to those npfa's that accept their languages with a small probability of error and run in polynomial expe cted time. Equivalently, we study Arthur{Merlin games where Arthur is limited to polynomial time and constant space. Dwork and Stockmeyer [S IAM J. Comput., 19 (1990), pp. 1011-1023] asked whether these npfa's a ccept only the regular languages (this was known if the automaton has only randomness or only nondeterminism). We show that the answer is ye s in the case of npfa's with a 1-way input head. We also show that if L is a nonregular language, then either L or (L) over bar is not accep ted by any npfa with a 2-way input head. Toward this end, we define a new measure of the complexity of a language L, called its 1-tiling com plexity. For each n, this is the number of tiles needed to cover the 1 's in the ''characteristic matrix'' of L, namely, the binary matrix wi th a row and column for each string of length less than or equal to n, where entry [x,y] = 1 if and only if the string xy epsilon L. We show that a language has constant 1-tiling complexity if and only if it is regular, from which the result on 1-way input follows. Our main resul t regarding the general 2-way input tape follows by contrasting two bo unds: an upper bound of polylog(n) on the 1-tiling complexity of every language computed by our model and a lower bound stating that the 1-t iling complexity of a nonregular language or its complement exceeds a function in 2 (Omega(root log n)) infinitely often. The last lower bou nd follows by proving that the characteristic matrix of every nonregul ar language has rank n for infinitely many n. This is our main technic al result, and its proof extends techniques of Frobenius and Iohvidov developed for Hankel matrices [Sitzungsber. der Konigl. Preuss. Akad. der Wiss., 1894, pp. 407-431], [Hankel and Toeplitz Matrices and Forms : Algebraic Theory, Birkhauser, Boston, 1982].