{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:03:03Z","timestamp":1787385783816,"version":"build-2736575974"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Given a description of a probabilistic automaton (one-head probabilistic finite-state automaton or probabilistic Turing machine) and an input string x of length n, we ask how much space does a deterministic Turing machine need in order to decide the acceptance of the input string by that automaton?<\/jats:p>\n                  <jats:p>The question is interesting even in the case of one-head one-way probabilistic finite-state automata (1pfa's). We call (rational) stochastic languages} ($\\SS_{rat}^{ &gt; }$) the class of languages recognized by 1pfa's whose transition probabilities and cutpoints (i.e., recognition thresholds) are rational numbers. The class $\\SS_{rat}^{ &gt; }$ contains context-sensitive languages that are not context-free, but on the other hand there are context-free languages not included in $\\SS_{rat}^{ &gt; }$.<\/jats:p>\n                  <jats:p>Our main results are as follows: \\begin{itemize} \\item{ The (proper) inclusion of $\\SS_{rat}^{ &gt; }$ in $\\zlo$, which is optimal (i.e., $\\SS_{rat}^{ &gt; } \\not \\subset$ \\Dspace$(o(\\log n))$). The previous upper bounds were \\Dspace$(n)$ (obtained by P. D. Dieu in 1972) and\\linebreak[4]\\Dspace$(\\log n \\log \\log n)$ (obtained by H. Jung in 1984).}<\/jats:p>\n                  <jats:p>\\item{ Probabilistic Turing machines with space bound f(n) in O(log n) can be deterministically simulated in space $O(\\min (c^{f(n)}\\log n, \\log n (f(n) + \\log \\log n)))$, where c is a constant depending on the simulated probabilistic Turing machine. The best previously known simulation uses O(log n (f(n) + log log n)) space (obtained by H. Jung in 1984).} \\end{itemize}<\/jats:p>\n                  <jats:p>\n                    To obtain these results we develop and use two space-efficient (but also parallel-time-efficient) techniques, which are of independent interest: \\begin{itemize} \\item {a technique to compare deterministically, using only O(log n) space, large numbers given in terms of their values modulo a sequence of primes, p\n                    <jats:sub>1<\/jats:sub>\n                    &lt; p\n                    <jats:sub>2<\/jats:sub>\n                    &lt; \\cdots &lt; p\n                    <jats:sub>n<\/jats:sub>\n                    in O(n\n                    <jats:sup>a<\/jats:sup>\n                    ) (where a is some arbitrary constant);} \\item {a technique to compare deterministically a threshold with entries of the inverse of a given banded matrix.} \\end{itemize}\n                  <\/jats:p>","DOI":"10.1137\/s0097539793253851","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"448-465","source":"Crossref","is-referenced-by-count":17,"title":["Space-Efficient Deterministic Simulation of Probabilistic Automata"],"prefix":"10.1137","volume":"27","author":[{"given":"Ioan I.","family":"Macarie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"R3","unstructured":"R. Bukharaev,\n                      On the representability of events in probabilistic automata\n                      , Prob. Methods and Cybernetics, V, Kazan, 1967, pp. 7\u201320 (in Russian)."},{"key":"R4","unstructured":"R. Bukharaev,\n                      Fundamentals of the Theory of Probabilistic automata\n                      , Moscow, Nauka, 1985 (in Russian)."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791224893"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170146"},{"key":"R9","first-page":"575","volume":"8","author":"Dieu P. D.","year":"1972","journal-title":"Electronische Informationsverarbeitung und Kybernetik EIK"},{"key":"R10","unstructured":"P. Dietz, personal communication, April 1993."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0220048"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00021-2"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0219069"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0218066"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1008"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"R\u016bsin\u02db\u0161 Freivalds, Probabilistic two\u2010way machines, Lecture Notes in Comput. Sci., Vol. 118, Springer, Berlin, 1981, 33\u20134583e:03059","DOI":"10.1007\/3-540-10856-4_72"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Freivalds,\n                      Complexity of probabilistic versus of Computer Science, 1981, Lecture Notes in Computer Science, 118, pp. 33\u201345. deterministic automata\n                      , Baltic Computer Science, Selected Papers, Lecture Notes on Computer Science 502, 1991, pp. 565\u2013613.","DOI":"10.1007\/3-540-10856-4_72"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0206049"},{"key":"R19","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , The Johns Hopkins University Press, Baltimore, MD, 1983."},{"key":"R20","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":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"H. Jung, Relationships between probabilistic and deterministictape complexity, Lecture Notes in Comput. Sci., Vol. 118, Springer, Berlin, 1981, 339\u201334683j:03066","DOI":"10.1007\/3-540-10856-4_101"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Hermann Jung, On probabilistic tape complexity and fast circuits for matrix inversion problems, Lecture Notes in Comput. Sci., Vol. 172, Springer, Berlin, 1984, 281\u2013291784256","DOI":"10.1007\/3-540-13345-3_25"},{"key":"R24","first-page":"63","volume":"1","author":"Kaneps J.","year":"1989","journal-title":"Diskretnaya Matematika"},{"key":"R25","first-page":"35","volume":"5","author":"Kuklin Yu. I.","year":"1973","journal-title":"Avtomatika i vycislitelnaja tekhnika"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057250"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"P. M. Lewis II, R. Stearn, and J. Hartmanis,\n                      Memory bounds for recognition of context\u2010free and context\u2010sensitive languages\n                      , IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"R28","unstructured":"I. Macarie,\n                      Closure properties of stochastic languages\n                      , TR441, Jan 1993, Dept. of Comp. Science, University of Rochester."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00218-N"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90075-5"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      Pseudorandom generators for space\u2010bounded computation\n                      , Proc. 22nd Annual ACM Symposium on the Theory of Computing, 1990, pp. 204\u2013212.","DOI":"10.1145\/100216.100242"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"N. Nisan, RL\u2286SC, Proc. 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 619\u2013623.","DOI":"10.1145\/129712.129772"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"N. Nisan and D. Zuckerman,\n                      More deterministic simulation in logspace\n                      , Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 235\u2013244.","DOI":"10.1145\/167088.167162"},{"key":"R34","unstructured":"A. Paz,\n                      Introduction to Probabilistic Automata\n                      , Computer Science and Applied Mathematics, Academic Press, New York and London, 1971."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/0215017"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"B. Ravikumar, Some observations on 2\u2010way probabilistic finite automata, Lecture Notes in Comput. Sci., Vol. 652, Springer, Berlin, 1992, 392\u201340394g:68085","DOI":"10.1007\/3-540-56287-7_121"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90066-7"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"A. Salomaa and M. Soittola,\n                      Automata\u2010theoretic aspects of formal power series\n                      , Berlin, Springer, 1978.","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"R. E. Stearns, J. Hartmanis, and P. M. Lewis II,\n                      Hierarchies of memory limited computations\n                      , 1965 IEEE Conf. Record on Switching Circuit Theory and Logical Design, 1965, pp. 179\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"J. Simon,\n                      On the difference between one and many\n                      , 4th Internat. Coll. on Automata, Languages and Programming, 1977, Lecture Notes in Computer Science 52, pp. 480\u2013491.","DOI":"10.1007\/3-540-08342-1_37"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"J. Simon,\n                      Space\u2010bounded probabilistic Turing machine complexity classes are closed under complement\n                      , 13th Annual ACM Symposium on Theory of Computing, 1981, pp. 158\u2013167.","DOI":"10.1145\/800076.802469"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90053-5"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"A. Salomaa and M. Soittola,\n                      Automata\u2010theoretic aspects of formal power series\n                      , Berlin, Springer, 1978.","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19660120108"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321741"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"M. Saks and S. Zhou, RSPACE(S)\u2286DSPACE(S3\/2), Proc. 36th Symposium on Foundations of Computer Science, 1995, pp. 344\u2013353.","DOI":"10.1109\/SFCS.1995.492490"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90360-4"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"P. Turakainen,\n                      On languages representable in rational probabilistic automata\n                      , Ann. Acad. Sci. Fenn. Ser. A, I 439, 1969.","DOI":"10.5186\/aasfm.1969.439"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1969-0242596-1"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90391-3"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90119-G"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793253851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:11Z","timestamp":1787335931000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793253851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793253851"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793253851","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}