TY - GEN

T1 - On the power of finite automata with both nondeterministic and probabilistic states (Preliminary version)

AU - Condon, Anne

AU - Hellerstein, Lisa

AU - Pottle, Samuel

AU - Wigderson, Avi

N1 - Funding Information:
*Department of Computer Sciences, University 1210 West Dayton St., Madison, WI 53706. condon~cs .uisc. edu. Supported in part by NSF grant CCR-9257241. t Department of Electrical Engineering and Computer Science, Northwestern University, 2145 Sheridan Rd., Evanston IL 60208-3118. hstein@eecs. mm. edu. Supported in part by NSF grant 0830-350-F674. f DeP=tment Computer Sciences, University 1210 West Dayton St., Madison, WI 53706. pottle@cs Supported by NSF grant CCR-9257241. $Computer science Department, Hebrew University, Jerusalem, 91904, Israel. avi~cs. huji. ac. il. Supported in part by BSF grant 92-00106/1 and a grant from the Wolfson Research Awards. -

PY - 1994/5/23

Y1 - 1994/5/23

N2 - 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 expected time. Equivalently, we study Arthur-Merlin games where the players are limited to polynomial time and constant space. Dwork and Stockmeyer asked whether the above class of npfa's accept only the regular languages (this was known if the automaton has only randomness or only nondeterminism). We show that the answer is yes in the case of npfa's with a l-way input head. We also show that if L is a nonregular language, then either L or is not accepted 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 l-Tiling complexity. 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 with a row and column for each string of length n, where entry [z, y] = 1 if and only if the string zy ϵ L. We show that a language has constant l-Tiling complexity if and only if it is regular, from which the result on l-way input follows. Our main result regarding the general 2-way input tape follows by contrasting two bounds: An upper bound of polylog(n) on the l-Tiling complexity of every language computed by our model, and a lower bound stating that the l-Tiling complexity of a nonregular language or its complement exceeds a function in 2Ω√(logn) infinitely often. The last lower bound follows by proving that the characteristic matrix of ever-y nonregular language has rank n for infinitely many n. This is our main technical result, and its proof uses techniques of Frobenius and Iohvidov developed for Hankel matrices.

AB - 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 expected time. Equivalently, we study Arthur-Merlin games where the players are limited to polynomial time and constant space. Dwork and Stockmeyer asked whether the above class of npfa's accept only the regular languages (this was known if the automaton has only randomness or only nondeterminism). We show that the answer is yes in the case of npfa's with a l-way input head. We also show that if L is a nonregular language, then either L or is not accepted 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 l-Tiling complexity. 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 with a row and column for each string of length n, where entry [z, y] = 1 if and only if the string zy ϵ L. We show that a language has constant l-Tiling complexity if and only if it is regular, from which the result on l-way input follows. Our main result regarding the general 2-way input tape follows by contrasting two bounds: An upper bound of polylog(n) on the l-Tiling complexity of every language computed by our model, and a lower bound stating that the l-Tiling complexity of a nonregular language or its complement exceeds a function in 2Ω√(logn) infinitely often. The last lower bound follows by proving that the characteristic matrix of ever-y nonregular language has rank n for infinitely many n. This is our main technical result, and its proof uses techniques of Frobenius and Iohvidov developed for Hankel matrices.

UR - http://www.scopus.com/inward/record.url?scp=0027929414&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027929414&partnerID=8YFLogxK

U2 - 10.1145/195058.195431

DO - 10.1145/195058.195431

M3 - Conference contribution

AN - SCOPUS:0027929414

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 676

EP - 685

BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994

PB - Association for Computing Machinery

T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994

Y2 - 23 May 1994 through 25 May 1994

ER -