{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:54Z","timestamp":1725663354507},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_133","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:36:43Z","timestamp":1330209403000},"page":"174-185","source":"Crossref","is-referenced-by-count":12,"title":["Running time to recognize nonregular languages by 2-way probabilistic automata"],"prefix":"10.1007","author":[{"given":"J\u0101nis","family":"Ka\u0146eps","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"13_CR1","unstructured":"A.And\u017e\u0101ns. On advantages of probabilistic automata over deterministic ones in maze walks and recognition of 2-dimensional domains.-In: Probabilistic Automata and their Applications. Kazan University Press, 1986, p.64\u201368 (Russian)."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"M.Blum and C.Hewitt. Automata on a 2-dimensional tape.-Proc. 8th Annual Symp. on Switching and Automata Theory, 1967, p.155\u2013160.","DOI":"10.1109\/FOCS.1967.6"},{"key":"13_CR3","unstructured":"C.Dwork and L.Stockmeyer. Interactive proof systems with finite state verifiers.-Report RJ 6262, IBM Research Division, San Jose, CA, 1988."},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"C.Dwork and L.Stockmeyer. On the power of 2-way probabilistic finite state automata.-Proc. 30th FOCS, 1989, p.480\u2013485.","DOI":"10.1109\/SFCS.1989.63522"},{"issue":"6","key":"13_CR5","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"C. Dwork and L. Stockmeyer. A time complexity gap for two-way probabilistic finite state automata.-SIAM Journal of Computing, December 1990, v.19,No.6,p.1011\u20131023.","journal-title":"SIAM Journal of Computing"},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds. Probabilistic two-way machines.-Lecture notes in Computer Science, Springer, 1981, v.118, p.33\u201345.","journal-title":"Lecture notes in Computer Science"},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/3-540-12689-9_101","volume":"158","author":"R. Freivalds","year":"1983","unstructured":"R. Freivalds.Space and reversal complexity of probabilistic one-way Turing machines.-Lecture Notes in Computer Science, Springer, 1983, v.158, p.159\u2013170.","journal-title":"Lecture Notes in Computer Science"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0022-0000(86)90045-0","volume":"33","author":"A.G. Greenberg","year":"1986","unstructured":"A.G. Greenberg and A. Weiss. A lower bound for probabilistic algorithms for finite state machines.-Journal of Computer and System Sciences, 1986, v.33, p.88\u2013105.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/BFb0030312","volume":"176","author":"J. Hromkovi\u010d","year":"1984","unstructured":"J. Hromkovi\u010d. Hierarchy of reversal and zerotesting bounded multicounter machines.-Lecture Notes in Computer Science, Springer, 1984, v.176, p.312\u2013321.","journal-title":"Lecture Notes in Computer Science"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O.H. Ibarra","year":"1978","unstructured":"O.H. Ibarra. Reversal-bounded multicounter machines and their decision problems.-Journal of the ACM, 1978, v.25, p.116\u2013133.","journal-title":"Journal of the ACM"},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N.D. Jones","year":"1975","unstructured":"N.D. Jones. Space bounded reducibility among combinatorial problems.-Journal of Computer and System Sciences, 1975, v.11, p.68\u201385.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"H.Jung. On probabilistic time and space.-Lecture Notes in Computer Science, Springer, 1985, v.194.","DOI":"10.1007\/BFb0015756"},{"issue":"4","key":"13_CR13","first-page":"63","volume":"1","author":"J. Ka\u0146eps","year":"1989","unstructured":"J. Ka\u0146eps. Stochasticity of the languages recognizable by 2-way finite probabilistic automata.-Diskretnaya Matematika, 1989, v.1, n.4, p.63\u201377 (Russian).","journal-title":"Diskretnaya Matematika"},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BFb0029629","volume":"452","author":"J. Ka\u0146eps","year":"1990","unstructured":"J. Ka\u0146eps and R. Freivalds. Minimal nontrivial space complexity of probabilistic one-way Turing machines.-Lecture Notes in Computer Science, Springer, 1990, v.452, p.355\u2013361.","journal-title":"Lecture Notes in Computer Science"},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R.E. Ladner","year":"1984","unstructured":"R.E. Ladner, R.J. Lipton, and L.J. Stockmeyer. Alternating pushdown and stack automata.-SIAM Journal of Computing, 1984, v.13, p.135\u2013155.","journal-title":"SIAM Journal of Computing"},{"key":"13_CR16","volume-title":"The Markov Chain Tree Theorem","author":"F.T. Leighton","year":"1983","unstructured":"F.T. Leighton and R.L. Rivest. The Markov Chain Tree Theorem.-MIT Laboratory for Computer Science TM-249, MIT, Cambridge, Mass., 1983."},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/3-540-09510-1_34","volume":"72","author":"B. Monien","year":"1979","unstructured":"B. Monien and I.H. Sudborough. On eliminating nondeterminism from Turing machines which use less than logarithm worktape space.-Lecture Notes in Computer Science, Springer, 1979, v.72, p.431\u2013435.","journal-title":"Lecture Notes in Computer Science"},{"issue":"3","key":"13_CR18","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"M.O. Rabin. Probabilistic automata.-Information and Control, 1963, v.6, No.3, p.230\u2013245.","journal-title":"Information and Control"},{"key":"13_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-theoretic Aspects of Formal Power Series","author":"A. Salomaa","year":"1978","unstructured":"A. Salomaa and M. Soittola. Automata-theoretic Aspects of Formal Power Series.-Berlin: Springer, 1978."},{"key":"13_CR20","volume-title":"Computational Complexity","author":"K. Wagner","year":"1986","unstructured":"K. Wagner and G. Wechsung. Computational Complexity.-Mathematische Monographien, Band 19, VEB Deutscher Verlag der Wissenschaften, Berlin, 1986."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_133.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:10Z","timestamp":1605646390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_133","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}