{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T23:31:48Z","timestamp":1676676708749},"reference-count":28,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1989,3,1]],"date-time":"1989-03-01T00:00:00Z","timestamp":604713600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8904,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1989,3]]},"DOI":"10.1016\/0890-5401(89)90012-6","type":"journal-article","created":{"date-parts":[[2004,12,2]],"date-time":"2004-12-02T00:24:20Z","timestamp":1101947060000},"page":"269-288","source":"Crossref","is-referenced-by-count":10,"title":["The logarithmic alternation hierarchy collapses: A\u03a32L = A\u03a02L"],"prefix":"10.1016","volume":"80","author":[{"given":"Birgit","family":"Jenner","sequence":"first","affiliation":[]},{"given":"Bernd","family":"Kirsig","sequence":"additional","affiliation":[]},{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(89)90012-6_BIB1","series-title":"Proceedings, Conf. Structure in Complexity Theory, Univ. of California, Berkeley","first-page":"105","article-title":"The Boolean hierarchy: Hardware over NP","volume":"Vol. 223","author":"Cai","year":"1986"},{"issue":"No. 1","key":"10.1016\/0890-5401(89)90012-6_BIB2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0890-5401(89)90012-6_BIB3","series-title":"Proceedings, Third Annual ACM Symposium on the Theory of Computing","first-page":"151","article-title":"The complexity of theorem proving procedures","author":"Cook","year":"1971"},{"issue":"No. 35","key":"10.1016\/0890-5401(89)90012-6_BIB4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","article-title":"The monotone and planar circuit value problems are LOG space complete for P","volume":"9","author":"Goldschlager","year":"1977","journal-title":"SIGACT News"},{"key":"10.1016\/0890-5401(89)90012-6_BIB5","author":"Hopcroft","year":"1979"},{"key":"10.1016\/0890-5401(89)90012-6_BIB6","author":"Immerman","year":"1987"},{"key":"10.1016\/0890-5401(89)90012-6_BIB7","article-title":"Die deterministische polynomielle Hierarchie-Ein polynomielles Analogon der Logarithmischen Alternierungshierarchie","author":"Jenner","year":"1987"},{"key":"10.1016\/0890-5401(89)90012-6_BIB8","series-title":"Proceedings, 5th STACS","first-page":"118","article-title":"Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata","volume":"Vol. 294","author":"Jenner","year":"1988"},{"key":"10.1016\/0890-5401(89)90012-6_BIB9","series-title":"Proceedings, 7th Annual Princeton Conf. on Information Sciences and Systems","first-page":"547","article-title":"Reducibility among combinatorial problems in logn space","author":"Jones","year":"1973"},{"key":"10.1016\/0890-5401(89)90012-6_BIB10","series-title":"The polynomial hierarchy collapses if the Boolean hierarchy collapses","author":"Kadin","year":"1987"},{"key":"10.1016\/0890-5401(89)90012-6_BIB11","series-title":"Logarithmic Hausdorff reductions","author":"Kirsig","year":"1986"},{"key":"10.1016\/0890-5401(89)90012-6_BIB12","series-title":"The difference and truth-table hierarchies for NP","author":"K\u00f6bler","year":"1985"},{"key":"10.1016\/0890-5401(89)90012-6_BIB13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","article-title":"Relativization of questions about log space computability","volume":"10","author":"Ladner","year":"1976","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0890-5401(89)90012-6_BIB14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","article-title":"A comparison of polynomial time reducibilities","volume":"1","author":"Ladner","year":"1975","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB15","series-title":"Proceedings, 12th Symp. of Math. Foundations of Comput. Science","first-page":"518","article-title":"Two characterizations of the logarithmic alternation hierarchy","volume":"Vol. 233","author":"Lange","year":"1986"},{"key":"10.1016\/0890-5401(89)90012-6_BIB16","series-title":"Proceedings, 14th ICALP, Karlsruhe","first-page":"531","article-title":"The logarithmic alternation hierarchy collapses: A\u03a32L = A\u03a02L","volume":"Vol. 267","author":"Lange","year":"1987"},{"key":"10.1016\/0890-5401(89)90012-6_BIB17","series-title":"Proceedings, 13th Annual IEEE Symp. on Switching and Automata Theory 1972","first-page":"125","article-title":"The equivalence problem for regular expressions with squaring requires exponential space","author":"Meyer","year":"1972"},{"key":"10.1016\/0890-5401(89)90012-6_BIB18","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","article-title":"The complexity of facets (and some facets of complexity)","volume":"28","author":"Papadimitriou","year":"1984","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB19","series-title":"Proceedings, 3rd STACS","first-page":"306","article-title":"Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \u03c9-machines","volume":"Vol. 210","author":"Rosier","year":"1986"},{"key":"10.1016\/0890-5401(89)90012-6_BIB20","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","article-title":"Space-bounded hierarchies and probabilistic computations","volume":"28","author":"Ruzzo","year":"1984","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB22","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0035835","article-title":"Collapsing oracle hierarchies, census functions and logarithmically many queries","author":"Sch\u00f6ning","year":"1987"},{"key":"10.1016\/0890-5401(89)90012-6_BIB23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB24","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepsc\u00e9nyi","year":"1987","journal-title":"Bull. European Associ. Theoret. Comput. Sci."},{"issue":"No. 2","key":"10.1016\/0890-5401(89)90012-6_BIB25","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0022-0000(87)90009-2","article-title":"\u03a32SPACE(n) is closed under complement","volume":"35","author":"Toda","year":"1987","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(89)90012-6_BIB26","series-title":"More complicated questions about maxima and minima, and some closures of NP, report","author":"Wagner","year":"1986"},{"issue":"No. 3","key":"10.1016\/0890-5401(89)90012-6_BIB27","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","article-title":"The complexity of combinatorial problems with succint input representation","volume":"23","author":"Wagner","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/0890-5401(89)90012-6_BIB28","series-title":"Proceedings, FCT Conf.","first-page":"485","article-title":"On the Boolean closure of NP","volume":"Vol. 199","author":"Wechsung","year":"1985"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900126?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900126?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T18:27:25Z","timestamp":1549045645000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540189900126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,3]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,3]]}},"alternative-id":["0890540189900126"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(89)90012-6","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1989,3]]}}}