{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:05Z","timestamp":1725663725886},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_135","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:21:58Z","timestamp":1330262518000},"page":"109-122","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Space-efficient deterministic simulation of probabilistic automata"],"prefix":"10.1007","author":[{"given":"Ioan I.","family":"Macarie","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"Borodin, A. On relating time and space to size and depth. SIAM J. Comput. 6, 1977, pp. 733\u2013744.","journal-title":"SIAM J. Comput."},{"key":"9_CR2","unstructured":"Bukharaev R. On the representability of events in probabilistic automata. Prob. methods and Cybernetics, V, Kazan, 1967, pp. 7\u201320 (in Russian)."},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1137\/0220048","volume":"20","author":"G.I. Davida","year":"1991","unstructured":"Davida, G.I., and Litow, B. Fast parallel arithmetic via modular representation. SIAM J. Comput. 20, 1991, pp. 756\u2013765.","journal-title":"SIAM J. Comput."},{"key":"9_CR4","unstructured":"Dietz, P. Personal communication. April 1993."},{"key":"9_CR5","unstructured":"Dietz, P., Macarie, I., and Seiferas, J. Bits and Relative Order from Residues, Space Efficiently. TR 464, July 1993, Dept. of Computer Science, Univ. of Rochester."},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1002\/malq.19710170146","volume":"17","author":"P.D. Dieu","year":"1971","unstructured":"Dieu, P.D. On a Class of Stochastic Languages. Zietschr. f. math. Logik und Grundlagen d. Math. 17, 1971, pp. 421\u2013425.","journal-title":"Zietschr. f. math. Logik und Grundlagen d. Math."},{"key":"9_CR7","first-page":"575","volume":"10","author":"P.D. Dieu","year":"1972","unstructured":"Dieu, P.D. On a Necessary Condition for Stochastic Languages. Electronische Informationsverarbeitung und Kybernetik EIK 8, 10, 1972, pp. 575\u2013588.","journal-title":"Electronische Informationsverarbeitung und Kybernetik EIK 8"},{"issue":"No.6","key":"9_CR8","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"Dwork, C. and Stockmeyer, L. A time complexity gap for two-way Probabilistic Finite-state Automata. Siam J. Comput. Vol. 19, No. 6, pp 1011\u20131023, December 1990.","journal-title":"Siam J. Comput."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Freivalds, R. Probabilistic two-way machines. Proceedings, Int. Sympos. Math. Found. of Comput. Sci., Lecture Notes in Computer Science Vol. 118, Springer, 1981, pp. 33\u201345.","DOI":"10.1007\/3-540-10856-4_72"},{"issue":"No4","key":"9_CR10","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, No 4, 1977, pp. 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"9_CR11","volume-title":"Matrix Computations","author":"G. Golub","year":"1983","unstructured":"Golub, G., and Van Loan, C. Matrix Computations. The Johns Hopkins University Press, Baltimore, Maryland, 1983."},{"key":"9_CR12","first-page":"281","volume":"172","author":"H. Jung","year":"1984","unstructured":"Jung, H. On probabilistic tape complexity and fast circuits for matrix inversion problems. Proc. ICALP 1984, LNCS 172, pp. 281\u2013291.","journal-title":"Proc. ICALP"},{"issue":"No4","key":"9_CR13","first-page":"63","volume":"1","author":"J. Kaneps","year":"1989","unstructured":"Kaneps, J. Stochasticity of the languages recognizable by 2-way finite probabilistic automata. Diskretnaya Matematika, Vol. 1, No 4, 1989, pp. 63\u201377 (Russian).","journal-title":"Diskretnaya Matematika"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Lewis II, P.M., Stearn, R., and Hartmanis, J. Memory bounds for recognition of context-free and context-sensitive languages. IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"9_CR15","unstructured":"Macarie, I. Closure properties of stochastic languages. TR441, Jan 1993, Dept. of Comp. Science, Univ. of Rochester"},{"key":"9_CR16","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(82)90075-5","volume":"21","author":"B. Monien","year":"1982","unstructured":"Monien, B. and Sudborough I. H. On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Theoretical Computer Science 21, 1982, pp. 237\u2013253.","journal-title":"Theoretical Computer Science"},{"key":"9_CR17","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O. Probabilistic automata. Information and control, 6, 1963, pp. 230\u2013244.","journal-title":"Information and control"},{"issue":"No1","key":"9_CR18","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/0215017","volume":"15","author":"J. Reif","year":"1986","unstructured":"Reif, J. Logarithmic depth circuits for algebraic functions. SIAM J. Cornput., 15, No 1, 1986, pp. 231\u2013242.","journal-title":"SIAM J. Cornput."},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Ravikumar, B. Some Observations on 2-way Probabilistic Finite Automata. TR92-208, May 1992, Dept. of Comp. Science and Statistics, Univ. of Rhode Island.","DOI":"10.1007\/3-540-56287-7_121"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Ruzzo, W., Simon, J.,and Tompa, M. Space-bounded hierarchies and probabilistic computation. 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 215\u2013223.","DOI":"10.1145\/800070.802194"},{"key":"9_CR21","first-page":"480","volume":"52","author":"J. Simon","year":"1977","unstructured":"Simon, J. On the difference between one and many. 4th Coll. on Automata,Languages and Programming, 1977, LNCS 52, pp. 480\u2013491.","journal-title":"LNCS"},{"key":"9_CR22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"Sipser, M. Halting space-bounded Computation. Theoretical Computer Science 10, 1980, pp. 335\u2013338.","journal-title":"Theoretical Computer Science"},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/malq.19660120108","volume":"12","author":"P. Starke","year":"1966","unstructured":"Starke, P. Stochastische Ereignisse und Wortmengen. Zietschr. f. math. Logik und Grundlagen d. Math. 12, 1966, pp. 61\u201368.","journal-title":"Zietschr. f. math. Logik und Grundlagen d. Math."},{"issue":"No1","key":"9_CR24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/321738.321741","volume":"20","author":"H. Stone","year":"1973","unstructured":"Stone, H. An efficient parallel algorithm for the solution of a tridiagonal linear system of equations. JACM 20, No 1, 1973, pp. 27\u201338.","journal-title":"JACM"},{"key":"9_CR25","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/S0019-9958(68)90360-4","volume":"12","author":"P. Turakainen","year":"1968","unstructured":"Turakainen, P. On Stochastic Languages. Information and Control 12, 1968, pp. 304\u2013313.","journal-title":"Information and Control"},{"key":"9_CR26","first-page":"439","volume":"I","author":"P. Turakainen","year":"1969","unstructured":"Turakainen, P. On languages representable in rational probabilistic automata. Ann. Acad. Sci. Fenn. Ser. A I 439, 1969.","journal-title":"Ann. Acad. Sci. Fenn. Ser. A"},{"key":"9_CR27","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1090\/S0002-9939-1969-0242596-1","volume":"21","author":"P. Turakainen","year":"1969","unstructured":"Turakainen, P. Generalized automata and stochastic languages. Proc. Amer. Math. Soc. 21, 1969, pp. 303\u2013309.","journal-title":"Proc. Amer. Math. Soc."},{"key":"9_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0020-0190(92)90119-G","volume":"43","author":"J. Wang","year":"1992","unstructured":"Wang, J. A note on two-way probabilistic automata. IPL 43, 1992, pp. 321\u2013326.","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:13:57Z","timestamp":1578525237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_135"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_135","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}