{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:41Z","timestamp":1725664181596},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995]]},"DOI":"10.1007\/3-540-59042-0_107","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:52Z","timestamp":1330257592000},"page":"583-596","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the structure of log-space probabilistic complexity classes"],"prefix":"10.1007","author":[{"given":"Ioan I.","family":"Macarie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L. and Moran, S. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comp. and System Sc., Vol. 36, 1988, pp. 254\u2013276.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR2","unstructured":"Condon, A. Computational Models of Games, MIT Press, 1989."},{"key":"51_CR3","unstructured":"Condon, A. The Complexity of Space Bounded Interactive Proof Systems. Complexity Theory: current research, ed. Spies, K.A., Homer, S., and Schoning, U., Cambridge Univ. 1993, pp. 147\u2013189."},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"Condon, A., Hellerstein, L., Pottle, S., and Wigderson, A. On the Power of Finite Automata with both Nondeterministic and Probabilistic States. Proceedings STOC'94, 1994, pp. 676\u2013685.","DOI":"10.1145\/195058.195431"},{"key":"51_CR5","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"Dwork, C., and Stockmeyer, L. Finite state verifiers I: the power of interaction. J. ACM, Vol. 39, 1992, pp. 800\u2013828.","journal-title":"J. ACM"},{"key":"51_CR6","first-page":"33","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R. Probabilistic two-way machines. Proceedings, Int. Sympos. Math. Found. of Comput. Sci. 1981, LNCS 118, 1981, pp. 33\u201345.","journal-title":"LNCS"},{"key":"51_CR7","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. Vol 6, 1977, pp. 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"51_CR8","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1989, pp. 186\u2013208.","journal-title":"SIAM J. Comput."},{"key":"51_CR9","first-page":"73","volume-title":"Randomness and Computation, Vol. 5 of Advances in Computing Research","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., and Sipser, M. Public coins vs. private coins in interactive proof systems. Randomness and Computation, Vol. 5 of Advances in Computing Research, JAI Press, Greenwich, 1989, pp. 73\u201390."},{"key":"51_CR10","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"Hartmanis, J. On Non-Determinancy in Simple Computing Devices. Acta Informatica 1, 1972, pp. 336\u2013344","journal-title":"Acta Informatica"},{"key":"51_CR11","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F. C. Hennie","year":"1966","unstructured":"Hennie, F. C., and Stearns, R. E. Two-tape simulation of multitape Turing machines. J. ACM, Vol. 13, 1966, pp. 533\u2013546.","journal-title":"J. ACM"},{"key":"51_CR12","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/S0022-0000(73)80048-0","volume":"7","author":"O. H. Ibarra","year":"1973","unstructured":"Ibarra, O. H. On two-way multihead automata. J. Comp. and System Sc., Vol. 7, 1973, pp. 28\u201336.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR13","first-page":"310","volume":"194","author":"H. Jung","year":"1985","unstructured":"Jung, H. On probabilistic time and space. Proceedings, ICALP 1985, LNCS 194, pp. 310\u2013317.","journal-title":"LNCS"},{"key":"51_CR14","first-page":"191","volume":"20","author":"L. G. Khachiyan","year":"1979","unstructured":"Khachiyan, L. G. A polynomial algorithm for linear programming. Soviet Math Dokl., Vol. 20, 1979, pp. 191\u2013194.","journal-title":"Soviet Math Dokl."},{"key":"51_CR15","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(88)90122-3","volume":"61","author":"K.N. King","year":"1988","unstructured":"King, K.N. Alternating multihead finite automata. Theoretical Computer Science, Vol. 61, 1988, pp. 149\u2013174.","journal-title":"Theoretical Computer Science"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Lewis II, P.M., Steam, 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":"51_CR17","first-page":"109","volume":"775","author":"I. I. Macarie","year":"1994","unstructured":"Macarie, I. I. Space-efficient deterministic simulations of probabilistic automata. Proceedings STACS'94, LNCS 775, 1994, pp. 109\u2013122.","journal-title":"LNCS"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Macarie, I. I. Multihead two-way probabilistic finite automata. To appear in Proceedings LATIN'95, 1995; also as Properties of Multihead Two-Way Probabilistic Finite Automata. TR 477, August 1994, Dept. of Computer Science, University of Rochester.","DOI":"10.1007\/3-540-59175-3_103"},{"key":"51_CR19","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00263746","volume":"6","author":"B. Monien","year":"1976","unstructured":"Monien, B. Transformational Methods and their Application to Complexity Problems. Acta Informatica 6, 1976, pp. 95\u2013108; Corrigendum, Acta Informatica 8, 1977, pp. 383\u2013384.","journal-title":"Acta Informatica"},{"issue":"No.1","key":"51_CR20","first-page":"67","volume":"14","author":"B. Monien","year":"1980","unstructured":"Monien, B. Two-way Multihead Automata over a one-letter alphabet. R.A.I.R.O. Informatique theoretique\/Theoretical Informatics, Vol. 14, No. 1, 1980, pp. 67\u201382.","journal-title":"R.A.I.R.O. Informatique theoretique\/Theoretical Informatics"},{"key":"51_CR21","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0022-0000(85)90045-5","volume":"31","author":"C. H. Papadimitriou","year":"1985","unstructured":"Papadimitriou, C. H. Games against nature. J. Comp. and System Sc., Vol. 31, 1985, pp. 288\u2013301.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR22","doi-asserted-by":"crossref","unstructured":"Ruby, S., and Fisher, P.C. Translational methods and computational complexity. Conf. Rec. IEEE Symp. on Switching Circuit Theory and Logical Design, 1965, pp. 173\u2013178.","DOI":"10.1109\/FOCS.1965.33"},{"key":"51_CR23","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. Ruzzo","year":"1984","unstructured":"Ruzzo, W., Simon, J., and Tompa, M. Space-bounded hierarchies and probabilistic computation. J. Comp. and System Sc., Vol. 28, 1984, pp. 216\u2013230.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"Savitch, W. J. Relationships between nondeterministic and deterministic tape complexity. J. Comp. and System Sc., Vol. 4, 1970, pp. 177\u2013192.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR25","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0022-0000(77)80042-1","volume":"14","author":"J. I. Seiferas","year":"1977","unstructured":"Seiferas, J. I. Relating Refined Space Complexity Classes. J. Comp. and System Sc., Vol. 14, 1977, pp. 100\u2013129.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR26","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0022-0000(77)80041-X","volume":"14","author":"J. I. Seiferas","year":"1977","unstructured":"Seiferas, J. I. Techniques for Separating Space Complexity Classes. J. Comp. and System Sc., Vol. 14, 1977, pp. 73\u201399.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR27","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. I. Seiferas","year":"1978","unstructured":"Seiferas, J. I., Fischer, M.J., and Meyer, A.R. Separating Nondeterministic Time Complexity Classes. J. ACM, Vol. 25, 1978, pp. 146\u2013167.","journal-title":"J. ACM"},{"key":"51_CR28","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"Sudborough, I. H. On Tape-Bounded Complexity Classes and Multihead Finite Automata. J. Comp. and System Sc., Vol. 10, 1975, pp. 62\u201376.","journal-title":"J. Comp. and System Sc."},{"key":"51_CR29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/322063.322076","volume":"25","author":"A.C. Yao","year":"1978","unstructured":"Yao, A.C. and Rivest, R.L. K+1 heads are better than K. J. ACM, Vol. 25, 1978, pp. 337\u2013340.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:31:25Z","timestamp":1578508285000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_107"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_107","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}