{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:02Z","timestamp":1725663722660},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_133","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:21:18Z","timestamp":1330262478000},"page":"83-96","source":"Crossref","is-referenced-by-count":1,"title":["The alternation hierarchy for machines with sublogarithmic space is infinite"],"prefix":"10.1007","author":[{"given":"Burchard","family":"Braunm\u00fchl","sequence":"first","affiliation":[]},{"given":"Romain","family":"Gengler","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Rettinger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01271368","volume":"3\/3","author":"von B. Braunm\u00fchl","year":"1993","unstructured":"B. von Braunm\u00fchl, R. Gengler, and R. Rettinger. The alternation hierarchy with sublogarithmic space is infinite. Computational Complexity, 3\/3:207\u2013230, 1993. To appear.","journal-title":"Computational Complexity"},{"key":"7_CR2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran. Arthur-Merlin games: a randomized proof-system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR3","unstructured":"B. v. Braunm\u00fchl. Alternationshierarchien von Turingmaschinen mit kleinem Speicher. Informatik Berichte 83, Inst. f. Informatik, Universit\u00e4t Bonn, 1991."},{"key":"7_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(87)90085-8","volume":"25","author":"J. H. Chang","year":"1987","unstructured":"J. H. Chang, O. H. Ibarra, B. Ravikumar, and L. Berman. Some observations concerning Turing machines using small space. Information Processing Letters, 25:1\u20139, 1987. Erratum, Information Processing Letters, 25:53, 1988.","journal-title":"Information Processing Letters"},{"key":"7_CR5","first-page":"158","volume":"23","author":"R. Freivalds","year":"1979","unstructured":"R. Freivalds. On time complexity of deterministic and nondeterministic Turing machines. Latvijski Mathemati\u010deskij Eshegodnik, 23:158\u2013165, 1979. In Russian.","journal-title":"Latvijski Mathemati\u010deskij Eshegodnik"},{"key":"7_CR6","volume-title":"Research report","author":"V. Geffert","year":"1993","unstructured":"V. Geffert. A hierarchy that does not collapse: Alternations in low level space. Research report, \u0161af\u00e1rik University, Ko\u0161ice, 1993."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"L. A. Hemachandra. The strong exponential hierarchy collapses. In Proc. 19th. STOC Conference, pages 110\u2013122, 1987.","DOI":"10.1145\/28395.28408"},{"issue":"no.10","key":"7_CR8","first-page":"990","volume":"E 70","author":"A. Ito","year":"1987","unstructured":"A. Ito, K. Inoue, and I. Takanami. A note on alternating Turing machines using small space. The Trans. of the IEICE, E 70 no. 10:990\u2013996, 1987.","journal-title":"The Trans. of the IEICE"},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. NSPACE is closed under complement. SIAM J. Comput., 17:935\u2013938, 1988.","journal-title":"SIAM J. Comput."},{"key":"7_CR10","volume-title":"Research report","author":"K. Iwama","year":"1986","unstructured":"K. Iwama. ASPACE(o(log log)) is regular. Research report, KSU\/ICS Kyoto Sangyo University, Kyoto, 603, Japan, March 1986. See also SIAM J. Comput. 22:136\u2013146, 1993."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"M. Li\u015akiewicz and K. Lory\u015a. On reversal complexity for alternating Turing machines. In Proc. 30st FOCS, pages 618\u2013623, 1989.","DOI":"10.1109\/SFCS.1989.63544"},{"key":"7_CR12","first-page":"16","volume":"665","author":"M. Li\u015akiewicz","year":"1993","unstructured":"M. Li\u015akiewicz and R. Reischuk. Separating the lower levels of the sublogarithmic space hierarchy. In Proc. 10. STACS, LNCS 665, pages 16\u201328, 1993.","journal-title":"Proc. 10. STACS, LNCS"},{"key":"7_CR13","volume-title":"Technical report","author":"M. Liskiewicz","year":"1993","unstructured":"M. Liskiewicz and R. Reischuk. The sublogarithmic space world. Technical report, Institut f\u00fcr Theoretische Informatik, TH Darmstadt, 1993."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. In Proc 15. Ann. ACM Symp. on Theory of Computing, pages 330\u2013335, 1983.","DOI":"10.1145\/800061.808733"},{"key":"7_CR15","doi-asserted-by":"crossref","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:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"7_CR16","first-page":"2","volume":"665","author":"K. W. Wagner","year":"1993","unstructured":"K. W. Wagner. The alternation hierarchy for sublogarithmic space: an exciting race to STACS'93 (Editorial note). In Proc. 10. STAGS, LNCS 665, pages 2\u20134, 1993.","journal-title":"Proc. 10. STAGS"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_133.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:52Z","timestamp":1605647632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_133","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}