{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:04Z","timestamp":1742617204550,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"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-60249-6_66","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:57:58Z","timestamp":1330279078000},"page":"343-352","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Properties of probabilistic pushdown automata"],"prefix":"10.1007","author":[{"given":"Ioan I.","family":"Macarie","sequence":"first","affiliation":[]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and J. Jiao. Depth reduction for noncommutative arithmetic circuit. In Proceedings of the 25th Symposium on Theory of Computing, pages 515\u2013522. ACM Press, 1993.","DOI":"10.1145\/167088.167226"},{"issue":"4","key":"29_CR2","first-page":"283","volume":"13","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. On Relativising Auxiliary Pushdown Machines. Mathematical Systems Theory, 13(4):283\u2013299, 1980.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"29_CR3","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28(1):114\u2013133, January 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR4","unstructured":"A. Condon. Computational models of games. M.I.T. Press, 1989."},{"issue":"1","key":"29_CR5","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"S. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the Association for Computing Machinery, 18(1):4\u201318, January 1971.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"R. Freivalds. Probabilistic two-way machines. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, pages 33\u201345. Springer-Verlag Lecture Notes in Computer Science #118, 1981.","DOI":"10.1007\/3-540-10856-4_72"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Z. Galil. Two-way deterministic pushdown automata and some open problems in the theory of computation. In Proceedings of the 15th Symposium on Switching and Automata Theory, pages 170\u2013177, 1974.","DOI":"10.1109\/SWAT.1974.29"},{"issue":"4","key":"29_CR8","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR9","series-title":"Advances in Computing Research # 5","first-page":"73","volume-title":"Randomness and Computation","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, pages 73\u201390. Advances in Computing Research # 5, JAI Press Inc., Greenwich, CT, 1989."},{"key":"29_CR10","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"J. Hartmanis. On non-determinancy in simple computing devices. Acta Informatica, 1:336\u2013344, 1972.","journal-title":"Acta Informatica"},{"key":"29_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979."},{"issue":"4","key":"29_CR12","first-page":"63","volume":"1","author":"J. Kaneps","year":"1989","unstructured":"J. Kaneps. Stochasticity of the languages recognized by 2-way finite probabilistic automata. Diskretnaya Mtematika, 1(4):63\u201377, 1989. (Russian).","journal-title":"Diskretnaya Mtematika"},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(88)90122-3","volume":"61","author":"K. King","year":"1988","unstructured":"K. King. Alternating multihead finite automata. Theoretical Computer Science, 61:149\u2013174, 1988.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"29_CR14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R. Ladner","year":"1984","unstructured":"R. Ladner, L. Stockmeyer, and R. Lipton. Alternating pushdown and stack automata. SIAM Journal on Computing, 13(1):135\u2013155, February 1984.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"I.I. Macarie. On the structure of log-space probabilistic complexity classes. In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, pages 583\u2013596. Springer-Verlag Lecture Notes in Computer Science #900, 1995.","DOI":"10.1007\/3-540-59042-0_107"},{"key":"29_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00263746","volume":"6","author":"B. Monien","year":"1976","unstructured":"B. Monien. Transformational methods and their application to complexity problems. Acta Informatica, 6:95\u2013108, 1976. Corrigendum, 8:383\u2013384, 1977.","journal-title":"Acta Informatica"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou. Games against nature. In Proceedings of the 24th Symposium on Foundations of Computer Science, pages 446\u2013450. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.20"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. Ruzzo","year":"1980","unstructured":"W. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Science, 21:218\u2013235, 1980.","journal-title":"Journal of Computer and System Science"},{"key":"29_CR19","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. Sudborough","year":"1975","unstructured":"I. Sudborough. On tape-bounded complexity classes and multihead finite automata. Journal of Computer and System Science, 10:62\u201376, 1975.","journal-title":"Journal of Computer and System Science"},{"issue":"3","key":"29_CR20","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. Sudborough","year":"1978","unstructured":"I. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25(3):405\u2013414, July 1978.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR21","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Science, 43:380\u2013404, 1991.","journal-title":"Journal of Computer and System Science"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the 6th Conference on Structure in Complexity Theory, pages 270\u2013284. IEEE Computer Society Press, 1991.","DOI":"10.1109\/SCT.1991.160269"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:57:06Z","timestamp":1742597826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_66"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_66","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":"30 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}