{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:34:47Z","timestamp":1742913287634,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637462"},{"type":"electronic","value":"9783540696407"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0052085","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T05:02:10Z","timestamp":1149656530000},"page":"163-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Closure under complementation of logspace complexity classes - A survey -"],"prefix":"10.1007","author":[{"given":"Birgit","family":"Jenner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,16]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi. An O(n log n) sorting network. In Proc.of 15th ACM STOC, pages 1\u20139. Association for Computing Machinery, 1983.","DOI":"10.1145\/800061.808726"},{"key":"14_CR2","unstructured":"C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Technical Report ECCC-TR96-039, http:\/\/www.eccc.unitrier.de\/eccc\/, 1996."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. \u00e0lvarez","year":"1993","unstructured":"C. \u00e0lvarez and B. Jenner. A very hard log-space counting class. Theoretical Computer Science, 107:3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01268143","volume":"5","author":"C. \u00e0lvarez","year":"1995","unstructured":"C. \u00e0lvarez and B. Jenner. A note on logspace optimization. J. of Computational Complexity, 5:155\u2013166, 1995.","journal-title":"J. of Computational Complexity"},{"issue":"1","key":"14_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/inco.1995.1122","volume":"121","author":"Y. Ben-Asher","year":"1995","unstructured":"Y. Ben-Asher, K.-J. Lange, D. Peleg, and A. Schuster. The complexity of reconfiguring network models. Information and Computation, 121(1):41\u201358, 1995.","journal-title":"Information and Computation"},{"issue":"3","key":"14_CR6","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM J. on Computing, 18(3):559\u2013578, 1989. & Erratum: 18(6):1283, 1989.","journal-title":"SIAM J. on Computing"},{"key":"14_CR7","volume-title":"Technical Report CS103","author":"S.R. Buss","year":"1988","unstructured":"S.R. Buss, S.A. Cook, P.W. Dymond, and L. Hay. The log space oracle hierarchy collapses. Technical Report CS103, Dept. of Computer Science and Engineering, Univ. of California, San Diego, CA, 1988."},{"key":"14_CR8","volume-title":"Technical Report TR 95-40","author":"J. Cai","year":"1995","unstructured":"J. Cai and D. Sivakumar. Resolution of Hartmanis' conjecture for NL-hard sparse sets. Technical Report TR 95-40, SUNY Buffalo, 1995."},{"issue":"1","key":"14_CR9","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. J. of the ACM, 28(1):114\u2013133, 1981.","journal-title":"J. of the ACM"},{"key":"14_CR10","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. J. of the ACM, 18:4\u201318, 1971.","journal-title":"J. of the ACM"},{"issue":"1\u20132","key":"14_CR11","first-page":"75","volume":"XXVII","author":"S. A. Cook","year":"1981","unstructured":"S. A. Cook. Towards a complexity theory of synchronous parallel computation. L'Enseignement Math\u00e9matique, XXVII(1\u20132):75\u2013100, 1981.","journal-title":"L'Enseignement Math\u00e9matique"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1):2\u201322, 1985.","journal-title":"Information and Control"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S. A. Cook","year":"1987","unstructured":"S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. J. of Algorithms, 8:385\u2013394, 1987.","journal-title":"J. of Algorithms"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"P. W. Dymond and S. A. Cook. Hardware complexity and parallel computation. In Proc. of 10th FOCS, pages 360\u2013372. IEEE, 1980.","DOI":"10.1109\/SFCS.1980.22"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L.M. Goldschlager","year":"1982","unstructured":"L.M. Goldschlager. Synchronous parallel computation. JACM, 29:1073\u20131086, 1982.","journal-title":"JACM"},{"key":"14_CR16","first-page":"1","volume":"7","author":"J. Hartmanis","year":"1974","unstructured":"J. Hartmanis and H.B. Hunt. The LBA problem and its importance in the theory of computing. In Complexity of Computation, pages 1\u201326. SIAM-AMS Proceedings, Vol. 7, 1974.","journal-title":"SIAM-AMS Proceedings"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM J. on Computing, 16(4):760\u2013778, 1987.","journal-title":"SIAM J. on Computing"},{"issue":"5","key":"14_CR18","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 J. on Computing, 17(5):935\u2013938, 1988.","journal-title":"SIAM J. on Computing"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(95)00017-7","volume":"54","author":"B. Jenner","year":"1995","unstructured":"B. Jenner. Knapsack problems for NL. Inform. Proc. Letters, 54:169\u2013174, 1995.","journal-title":"Inform. Proc. Letters"},{"key":"14_CR20","unstructured":"B. Jenner. Between NC\n                        \n                  1\n                \n                        and NC\n                        \n                  2\n                : Classification of Problems by Logspace Resources. Manuscript of habilitation thesis, 1997."},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0890-5401(89)90012-6","volume":"80","author":"B. Jenner","year":"1989","unstructured":"B. Jenner, B. Kirsig, and K.-J. Lange. The logarithmic alternation hierarchy collapses: A\u2211\n                        2\n                    L\n                  =A\u220f\n                        2\n                    L\n                  . Information and Computation, 80:269\u2013288, 1989.","journal-title":"Information and Computation"},{"key":"14_CR22","unstructured":"B. Jenner, K.-J. Lange, and P. McKenzie. Tree isomorphism and some other complete problems for deterministic logspace. Technical Report #1059, DIRO, Universit\u00e9 de Montr\u00e9al, 1997."},{"key":"14_CR23","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"N. Jones. Space-bounded reducibility among combinatorial problems. J. of Computer and System Sciences, 11:68\u201385, 1975.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Mathematical Systems Theory, 10:1\u201317, 1976.","journal-title":"Mathematical Systems Theory"},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"S.-Y. Kuroda","year":"1964","unstructured":"S.-Y. Kuroda. Classes of languages and linear-bounded automata. Information and Control, 7:207\u2013223, 1964.","journal-title":"Information and Control"},{"key":"14_CR26","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"},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H. R. Lewis","year":"1982","unstructured":"H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19:161\u2013187, 1982.","journal-title":"Theoretical Computer Science"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"S. Lindell. A logspace algorithm for tree canonization. In Proc. of the 24th STOC, pages 400\u2013404. ACM, 1992.","DOI":"10.1145\/129712.129750"},{"issue":"2","key":"14_CR29","first-page":"227","volume":"118","author":"R. Niedermeier","year":"1995","unstructured":"R. Niedermeier and P. Rossmanith. Unambiguous auxiliary pushdown autoata and semi-unbounded fan-in circuits. IC, 118(2):227\u2013245, 1995.","journal-title":"IC"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chicago J. of Theoretical Computer Science, Volume 1995:Article 1, 1995.","DOI":"10.7146\/brics.v1i31.21612"},{"key":"14_CR31","first-page":"47","volume":"529","author":"A. Razborov","year":"1991","unstructured":"A. Razborov. Lower bounds for deterministic and nondeterministic branching programs. In Proc. of the 8th FCT, LNCS 529, pages 47\u201360, 1991.","journal-title":"LNCS"},{"issue":"2","key":"14_CR32","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J. H. Reif","year":"1984","unstructured":"J. H. Reif. Symmetric complementation. J. of the ACM, 31(2):401\u2013421, 1984.","journal-title":"J. of the ACM"},{"key":"14_CR33","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. J. of Computer and System Sciences, 21:218\u2013235, 1980.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR34","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo. On uniform circuit complexity. J. of Computer and System Sciences, 22:365\u2013338, 1981.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR35","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. J. of Computer and System Sciences, 28:216\u2013230, 1984.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR36","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. The power of counting. In Complexity Theory Retrospective, pages 205\u2013223. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_9"},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning and K. Wagner. Collapsing oracles, hierarchies, census functions, and logarithmically many queries. In Proc. of the 5th STACS, number 294 in LNCS, pages 91\u201397. Springer-Verlag, 1988.","DOI":"10.1007\/BFb0035835"},{"key":"14_CR38","unstructured":"I. Simon. On some subrecursive reducibilities. Ph.D. thesis, Stanford University, Computer Science Department, Technical Report STAN-CS-77-608, 1977."},{"issue":"2","key":"14_CR39","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"S. Skyum and L. G. Valiant. A complexity theory based on boolean algebra. J. of the ACM, 32(2):484\u2013502, 1985.","journal-title":"J. of the ACM"},{"key":"14_CR40","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough. On tape-bounded complexity classes and multihead finite automata. J. of Computer and System Sciences, 10:62\u201376, 1975.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR41","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. J. of the ACM, 25:405\u2013414, 1978.","journal-title":"J. of the ACM"},{"key":"14_CR42","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:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"14_CR43","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0022-0000(87)90009-2","volume":"35","author":"S. Toda","year":"1987","unstructured":"S. Toda. \u03c32\n                        NSPACE(n) is closed under complement. J. of Computer and System Sciences, 35:145\u2013152, 1987.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR44","doi-asserted-by":"publisher","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. J. of Computer and System Sciences, 43:380\u2013404, 1991.","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR45","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"H. Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM J. on Computing, 21:655\u2013670, 1992.","journal-title":"SIAM J. on Computing"},{"key":"14_CR46","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1006\/jagm.1994.1022","volume":"16","author":"E. Wanke","year":"1994","unstructured":"E. Wanke. Bounded tree-width and LOGCFL. J. of Algorithms, 16:470\u2013491, 1994.","journal-title":"J. of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0052085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T23:18:25Z","timestamp":1676675905000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0052085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637462","9783540696407"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/bfb0052085","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"16 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}