{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:11Z","timestamp":1725483731103},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_37","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:28:20Z","timestamp":1178357300000},"page":"415-425","source":"Crossref","is-referenced-by-count":1,"title":["Alternating and Empty Alternating Auxiliary Stack Automata"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"issue":"1","key":"37_CR1","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"issue":"1","key":"37_CR2","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"S.A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18(1):4\u201318, 1971.","journal-title":"Journal of the ACM"},{"issue":"2","key":"37_CR3","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","volume":"5","author":"O. H. Ibarra","year":"1971","unstructured":"O. H. Ibarra. Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata. Journal of Computer and System Sciences, 5(2):88\u2013117, 1971.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"37_CR4","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BFb0035838","volume-title":"Proceedings of the 5th Annual Symposium on Theoretical Computer Science","author":"B. Jenner","year":"1988","unstructured":"B. Jenner and B. Kirsig. Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. In Proceedings of the 5th Annual Symposium on Theoretical Computer Science, number 294 in LNCS, pages 118\u2013125, Bordeaux, France, 1988. Springer."},{"key":"37_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"R. Ladner and N. Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10:19\u201332, 1976.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"37_CR7","doi-asserted-by":"publisher","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 on Computing, 13(1):135\u2013155, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0019-9958(84)80029-7","volume":"62","author":"R. E. Ladner","year":"1984","unstructured":"R. E. Ladner, L. J. Stockmeyer, and R. J. Lipton. Alternation bounded auxiliary pushdown automata. Information and Control, 62:93\u2013108, 1984.","journal-title":"Information and Control"},{"key":"37_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1007\/3-540-58338-6_96","volume-title":"Proceedings of the 9th Conference on Mathematical Foundations of Computer Science","author":"K.-J. Lange","year":"1994","unstructured":"K.-J. Lange and K. Reinhardt. Empty alternation. In Proceedings of the 9th Conference on Mathematical Foundations of Computer Science, number 841 in LNCS, pages 494\u2013503, Kosice, Slovakia, 1994. Springer."},{"issue":"2","key":"37_CR10","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. L. Ruzzo","year":"1984","unstructured":"W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28(2):216\u2013230, 1984.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"37_CR11","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25(3):405\u2013414, 1978.","journal-title":"Journal of the ACM"},{"issue":"3","key":"37_CR12","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"37_CR13","series-title":"Mathematics and its applications (East Europeans series)","volume-title":"Computational Complexity","author":"K. Wagner","year":"1986","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its applications (East Europeans series). VEB Deutscher Verlag der Wissenschaften, Berlin, 1986."},{"issue":"5","key":"37_CR14","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. W. Wagner","year":"1990","unstructured":"K. W. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, 1990.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T09:32:33Z","timestamp":1550309553000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}