{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:22:12Z","timestamp":1736486532138,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354284"},{"type":"electronic","value":"9783540354307"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11779148_40","type":"book-chapter","created":{"date-parts":[[2006,6,21]],"date-time":"2006-06-21T05:55:49Z","timestamp":1150869349000},"page":"443-454","source":"Crossref","is-referenced-by-count":0,"title":["On Some Variations of Two-Way Probabilistic Finite Automata Models"],"prefix":"10.1007","author":[{"given":"Bala","family":"Ravikumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","unstructured":"Alt, H., Mehlhorn, K.: Lower bounds for the space complexity for context-free recognition. In: Proc. of ICALP, pp. 338\u2013351 (1976)"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Borodin, A., Cook, S., Pippenger, N.: Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 113\u2013136 (1983)","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Condon, A., Lipton, R.: On interactive proofs with space-bounded verifiers. In: Proc. of 30th IEEE Annual Symp. on Found. of Comp. Science, pp. 462\u2013467 (1989)","DOI":"10.1109\/SFCS.1989.63519"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Condon, A., et al.: On the power of finite automata with both nondeterministic and probabilistic states. SIAM Journal on Computing, 739\u2013762 (1998)","DOI":"10.1137\/S0097539794265578"},{"key":"40_CR5","unstructured":"Dwork, C., Stockmeyer, L.: Interactive proof systems with finite state verifiers. IBM Report RJ 6262 (1988)"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Dwork, C., Stockmeyer, L.: On the Power of 2-way Probabilistic Finite State Automata. In: Proc. of 30th IEEE Annual Symp. on Found. of Comp. Science, pp. 480\u2013485 (1989)","DOI":"10.1109\/SFCS.1989.63522"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Dwork, C., Stockmeyer, L.: A time complexity gap for two-way probabilistic finite automata. SIAM Journal on Computing, 1011\u20131023 (1990)","DOI":"10.1137\/0219069"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Dwork, C., Stockmeyer, L.: Finite state verifiers I: The power of interaction. Journal of the ACM, 800\u2013828 (1992)","DOI":"10.1145\/146585.146599"},{"key":"40_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume-title":"Mathematical Foundations of Computer Science 1981","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R.: Probabilistic Two-way Machines. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol.\u00a0118, pp. 33\u201345. Springer, Heidelberg (1981)"},{"key":"40_CR10","unstructured":"Freivalds, R.: Why Probabilistic Algorithms Can be More Effective in Certain Cases? (invited Talk). Math. Foundations of Computer Science, pp. 1\u201314 (1986)"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. In: Proc. of 17th Annual ACM Symp. on Theory of Computing, pp. 291\u2013304 (1985)","DOI":"10.1145\/22145.22178"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private coins vs. public coins in interactive proof systems. In: Proc. of 18th ACM Symp. on Theory of Computing, pp. 59\u201368 (1986)","DOI":"10.1145\/12130.12137"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Greenberg, A., Weiss, A.: A Lower Bound for Probabilistic Algorithms for Finite State Machines. Jl. of Comp. and Sys. Sciences, 88\u2013105 (1986)","DOI":"10.1016\/0022-0000(86)90045-0"},{"key":"40_CR14","volume-title":"Introduction to Automata, Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata, Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Ibarra, O., Ravikumar, B.: Sublogarithmic space Turing machines, nonuniform space complexity and closure properties. Mathematical Systems Theory, 1\u201321 (1988)","DOI":"10.1007\/BF02088003"},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Verbeek, R.: There is no polynomial deterministic simulation of probabilistic space with two-way random-tape generator. Information and Computation, 158\u2013162 (1985)","DOI":"10.1016\/S0019-9958(85)80032-2"},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0019-9958(86)80020-1","volume":"71","author":"M. Karpinski","year":"1986","unstructured":"Karpinski, M., Verbeek, R.: On the power of Two-way Random Generators and the Impossibility of Deterministic Poly-Space Simulation. Information and Control\u00a071, 131\u2013142 (1986)","journal-title":"Information and Control"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Kaneps, J.: Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. In: Proc. of Fundamentals of Computation Theory, pp. 287\u2013296 (1991)","DOI":"10.1007\/3-540-54458-5_73"},{"key":"40_CR19","doi-asserted-by":"crossref","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s problem of tag and other topics in the theory of Turing machines. Annals of Mathemetics, 570\u2013581 (1961)","DOI":"10.2307\/1970290"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N.: On Read-Once vs. Multiple Access to Randomness in Logspace. In: Proc. of Fifth IEEE Structure in Complexity Theory, Barcelona, Spain, pp. 179\u2013184 (1990)","DOI":"10.1109\/SCT.1990.113966"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Rabin, M.: Probabilistic finite automata. Information and Control, 230\u2013245 (1963)","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Ravikumar, B.: On the power of probabilistic finite automata with bounded error probability. In: Proc. of the Foundations of Sofware Technology and Theoretical Computer Science, pp. 392\u2013403 (1992)","DOI":"10.1007\/3-540-56287-7_121"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11779148_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T13:57:43Z","timestamp":1736431063000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11779148_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354284","9783540354307"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11779148_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}