{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T06:41:37Z","timestamp":1789627297793,"version":"build-2803163510"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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 Arthur is limited to polynomial time and constant space.<\/jats:p>\n                  <jats:p>Dwork and Stockmeyer [SIAM J. Comput., 19 (1990), pp. 1011--1023] asked whether these 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 1-way input head. We also show that if L is a nonregular language, then either L or $\\bar{L}$ is not accepted by any npfa with a 2-way input head.<\/jats:p>\n                  <jats:p>Toward this end, we define a new measure of the complexity of a language L, called its 1-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 $\\le n$, where entry [x,y]=1 if and only if the string $xy \\in 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 result regarding the general 2-way input tape follows by contrasting two bounds: 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-tiling complexity of a nonregular language or its complement exceeds a function in $2^{\\Omega (\\sqrt{\\log n})}$ infinitely often.<\/jats:p>\n                  <jats:p>The last lower bound follows by proving that the characteristic matrix of every nonregular language has rank n for infinitely many n. This is our main technical result, and its proof extends techniques of Frobenius and Iohvidov developed for Hankel matrices [Sitzungsber. der K\u00f6nigl. Preuss. Akad. der Wiss., 1894, pp. 407--431], [Hankel and Toeplitz Matrices and Forms: Algebraic Theory, Birkhauser, Boston, 1982].<\/jats:p>","DOI":"10.1137\/s0097539794265578","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"739-762","source":"Crossref","is-referenced-by-count":15,"title":["On the Power of Finite Automata with both Nondeterministic and Probabilistic States"],"prefix":"10.1137","volume":"27","author":[{"given":"Anne","family":"Condon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lisa","family":"Hellerstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Pottle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. V. Aho, J. D. Ullman, and M. Yannakakis,\n                      On notions of information transfer in VLSI circuits\n                      , in Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 133\u2013139."},{"key":"R2","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy,\n                      Proof verification and hardness of approximation problems\n                      , in Proc. 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 14\u201323."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"R4","volume-title":"Computational models of games","author":"Condon Anne","year":"1989"},{"key":"R5","first-page":"739","volume":"27","author":"Condon Anne","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90038-4"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0219069"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146599"},{"key":"R9","unstructured":"Lance Fortnow, Carsten Lund, Interactive proof systems and alternating time\u2010space complexity, Lecture Notes in Comput. Sci., Vol. 480, Springer, Berlin, 1991, 263\u201327492c:68057"},{"key":"R10","unstructured":"R\u016bsin\u02db\u0161 Freivalds, Probabilistic two\u2010way machines, Lecture Notes in Comput. Sci., Vol. 118, Springer, Berlin, 1981, 33\u20134583e:03059"},{"key":"R11","unstructured":"G. Frobenius,\n                      \u00dcber das Tr\u00e4gheitsgesetz der quadratischen Formen\n                      , Sitzungsber. der K\u00f6nigl. Preuss. Akad. der Wiss., 1894, pp. 407\u2013431."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90045-0"},{"key":"R13","unstructured":"B. Halstenberg and R. Reischuk,\n                      On different modes of communication\n                      , in Proc. 20th Annual ACM Symposium on the Theory of Computing, 1988, pp. 162\u2013172."},{"key":"R14","unstructured":"John Hopcroft, Jeffrey Ullman, Wprowadzenie do teorii automat\u00f3w, j\u0119zyk\u00f3w i oblicze\u0144, Wydawnictwo Naukowe PWN, Warsaw, 1994, 480\u20130, Translated from the 1979 English original by Beata Konikowska99a:68001"},{"key":"R15","unstructured":"I. S. Iohvidov,\n                      Hankel and Toeplitz Matrices and Forms: Algebraic Theory\n                      , I. Gohberg, ed., G. Philip and A. Thijsse, translators, Birkh\u00e4user, Boston, 1982."},{"key":"R16","unstructured":"J\u0101nis Kan\u02dbeps, R\u016bsin\u02db\u0161 Freivalds, Minimal nontrivial space complexity of probabilistic one\u2010way Turing machines, Lecture Notes in Comput. Sci., Vol. 452, Springer, Berlin, 1990, 355\u20133611084853"},{"key":"R17","unstructured":"J\u0101nis Kan\u02dbeps, R\u016bsin\u02db\u0161 Freivalds, Running time to recognize nonregular languages by 2\u2010way probabilistic automata, Lecture Notes in Comput. Sci., Vol. 510, Springer, Berlin, 1991, 174\u20131851129905"},{"key":"R18","unstructured":"J\u0101nis Kan\u02dbeps, Regularity of one\u2010letter languages acceptable by 2\u2010way finite probabilistic automata, Lecture Notes in Comput. Sci., Vol. 529, Springer, Berlin, 1991, 287\u20132961136091"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321410"},{"key":"R20","unstructured":"F. T. Leighton and R. L. Rivest\n                      ,\n                      The Markov chain tree theorem\n                      , Report MIT\/LCS\/TM\u2010249, Laboratory for Computer Science, MIT, Cambridge, MA, 1983;"},{"key":"R20","unstructured":"also in IEEE Trans. Inform. Theory, I T\u201037 (1986), pp. 733\u2013742."},{"key":"R21","unstructured":"K. Melhorn and E. M. Schmidt,\n                      Las Vegas is better than determinism in VLSI and distributed computing\n                      , in Proc. 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 330\u2013337."},{"key":"R22","first-page":"406","volume":"80","author":"Orlin J.","year":"1977","journal-title":"Proc. Koniklijke Nederlandse Akademie van Wetenschappen, Amsterdam Series A","ISSN":"https:\/\/id.crossref.org\/issn\/0023-3358","issn-type":"print"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90045-5"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"R26","unstructured":"A. Salomaa and M. Soittola,\n                      Automata\u2010Theoretic Aspects of Formal Power Series\n                      , Texts and Monographs in Computer Science, Springer\u2010Verlag, New York, 1978."},{"key":"R27","unstructured":"E. M. Schmidt,\n                      Succinctness of description of context free, regular and unambiguous languages\n                      , Ph.D. thesis, Cornell University, Ithaca, NY, 1978."},{"key":"R28","unstructured":"J. Shallit,\n                      Automaticity: properties of a measure of descriptional complexity\n                      , in Proc. 11th Annual Symposium on Theoretical Aspects of Computer Science, February 1994."},{"key":"R29","unstructured":"A. C. Yao,\n                      Some complexity questions related to distributed computing\n                      , in Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 209\u2013213."},{"key":"R30","unstructured":"A. C. Yao,\n                      Lower bounds by probabilistic arguments\n                      , in Proc. 24th IEEE Symposium on Foundations of Computer Science, 1983, pp. 420\u2013428."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794265578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:38Z","timestamp":1787336018000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794265578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794265578"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794265578","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}