{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T18:35:41Z","timestamp":1791398141640,"version":"4.3.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540656913","type":"print"},{"value":"9783540491163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49116-3_42","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:56:14Z","timestamp":1187268974000},"page":"444-454","source":"Crossref","is-referenced-by-count":6,"title":["The Descriptive Complexity Approach to LOGCFL"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,4,12]]},"reference":[{"key":"42_CR1","volume-title":"Handbook of Formal Languages","author":"J.-M. Autebert","year":"1997","unstructured":"J.-M. Autebert, J. Berstel, and L. Boasson. Context-free languages and pushdown automata. In R. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, Berlin Heidelberg, 1997."},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D. A. M. Barrington","year":"1992","unstructured":"D. A. Mix Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien. Regular languages in NC1. Journal of Computer and System Sciences, 44:478\u2013499, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"42_CR3","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(93)90253-P","volume":"107","author":"F. B\u00e9dard","year":"1993","unstructured":"F. B\u00e9dard, F. Lemieux, and P. McKenzie. Extensions to Barrington\u2019s M-program model. Theoretical Computer Science, 107:31\u201361, 1993.","journal-title":"Theoretical Computer Science"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"H.-J. Burtschick","year":"1998","unstructured":"H.-J. Burtschick and H. Vollmer. Lindstr\u00f6m quantifiers and leaf language definability. International Journal of Foundations of Computer Science, 9:277\u2013294, 1998.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"42_CR6","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:4\u201318, 1971.","journal-title":"Journal of the ACM"},{"key":"42_CR7","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. Greibach","year":"1973","unstructured":"S. Greibach. The hardest context-free language. SIAM Journal on Computing, 2:304\u2013310, 1973.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR8","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1998","unstructured":"N. Immerman. Descriptive Complexity. Springer Verlag, New York, 1998."},{"key":"42_CR9","unstructured":"S. Lindell. manuscript, 1994. e-mail communication by Kenneth W. Regan."},{"key":"42_CR10","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"P. Lindstr\u00f6m","year":"1966","unstructured":"P. Lindstr\u00f6m. First order predicate logic with generalized quantifiers. Theoria, 32:186\u2013195, 1966.","journal-title":"Theoria"},{"key":"42_CR11","volume-title":"Handbook of Formal Languages","author":"A. Mateescu","year":"1997","unstructured":"A. Mateescu and A. Salomaa. Aspects of classical language theory. In R. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, chapter 4. Springer Verlag, Berlin Heidelberg, 1997."},{"key":"42_CR12","unstructured":"R. McNaughton and S. Papert. Counter-Free Automata. MIT Press, 1971."},{"key":"42_CR13","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P. P\u00e9ladeau","year":"1991","unstructured":"P. P\u00e9ladeau P. McKenzie and D. Th\u00e9rien. NC1: The automata-theoretic viewpoint. Computational Complexity, 1:330\u2013359, 1991.","journal-title":"Computational Complexity"},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M. P. Sch\u00fctzenberger","year":"1965","unstructured":"M. P. Sch\u00fctzenberger. On finite monoids having only trivial subgroups. Information & Control, 8:190\u2013194, 1965.","journal-title":"Information & Control"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings 19th Symposium on Theory of Computing, pages 77\u201382. ACM Press, 1987.","DOI":"10.1145\/28395.28404"},{"key":"42_CR16","first-page":"163","volume":"66","author":"J. Stern","year":"1985","unstructured":"J. Stern. Complexity of some problems from the theory of automata. Information & Computation, 66:163\u2013176, 1985.","journal-title":"Information & Computation"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston, 1994.","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"42_CR18","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:405\u2013414, 1978.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49116-3_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T12:20:43Z","timestamp":1708172443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49116-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656913","9783540491163"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-49116-3_42","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}