{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:39Z","timestamp":1725663699275},"publisher-location":"Berlin, Heidelberg","reference-count":18,"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_174","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:46Z","timestamp":1330262446000},"page":"593-606","source":"Crossref","is-referenced-by-count":1,"title":["The variable membership problem: Succinctness versus complexity"],"prefix":"10.1007","author":[{"given":"Gerhard","family":"Buntrock","sequence":"first","affiliation":[]},{"given":"Krzysztof","family":"Lory\u015a","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Jos\u00e9 L. Balc\u00e1zar, Josep D\u00edaz, and Joaquim Gabarr\u00f3. Structural Complexity Theory I. Springer, 1988.","key":"48_CR1","DOI":"10.1007\/978-3-642-97062-7"},{"doi-asserted-by":"crossref","unstructured":"Jos\u00e9 L. Balc\u00e1zar, Josep D\u00edaz, and Joaquim Gabarr\u00f3. Structural Complexity Theory II. Springer, 1990.","key":"48_CR2","DOI":"10.1007\/978-3-642-75357-2"},{"doi-asserted-by":"crossref","unstructured":"Gerhard Buntrock and Krzysztof Lory\u015a. On growing context-sensitive languages. In Proc. of 19th ICALP, volume 623 of LNCS, pages 77\u201388. Springer, 1992.","key":"48_CR3","DOI":"10.1007\/3-540-55719-9_65"},{"key":"48_CR4","volume-title":"Technical Report 69","author":"G. Buntrock","year":"1993","unstructured":"Gerhard Buntrock. Growing context-sensitive languages and automata. Technical Report 69, Universit\u00e4t W\u00fcrzburg, Institut f\u00fcr Informatik, Am Exerzierplatz 3, D-97072 W\u00fcrzburg, November 1993."},{"key":"48_CR5","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1080\/00207169008803946","volume":"37","author":"S. Cho","year":"1990","unstructured":"Sang Cho and Dung T. Huynh. The complexity of membership for deterministic growing context-sensitive grammars. International Journal of Computer Mathematics, 37:185\u2013188, 1990.","journal-title":"International Journal of Computer Mathematics"},{"key":"48_CR6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF00288653","volume":"3","author":"A. B. Cremers","year":"1973","unstructured":"A. B. Cremers. Normal forms for context-sensitive grammars. Acta Informatica, 3:59\u201373, 1973.","journal-title":"Acta Informatica"},{"doi-asserted-by":"crossref","unstructured":"Carsten Damm, Markus Holzer, and Klaus-J\u00f6rn Lange. The parallel complexity of iterated morphisms and the arithmetic of small numbers. In Proc. of 17th MFCS, volume 629 of LNCS, pages 227\u2013235. Springer, 1992.","key":"48_CR7","DOI":"10.1007\/3-540-55808-X_21"},{"key":"48_CR8","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Elias Dahlhaus and Manfred K. Warmuth. Membership for growing contextsensitive grammars is polynomial. Journal of Computer and System Sciences, 33:456\u2013472, 1986.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"48_CR9","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF00289308","volume":"16","author":"L. M. Goldschlager","year":"1981","unstructured":"Leslie M. Goldschlager. \u03b5-productions in context-free grammars. Acta Informatica, 16(3):303\u2013308, 1981.","journal-title":"Acta Informatica"},{"unstructured":"John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.","key":"48_CR10"},{"key":"48_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"Neil D. Jones and William T. Laaser. Complete problems for deterministic polynomial time. Theoretical Computer Science, 3:105\u2013117, 1977.","journal-title":"Theoretical Computer Science"},{"key":"48_CR12","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Richard M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations. Plenum Press, New York, 1972."},{"key":"48_CR13","doi-asserted-by":"crossref","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"},{"doi-asserted-by":"crossref","unstructured":"Albert R. Meyer and Larry J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proc. of the 13th Annual IEEE Symposium on Switching and Automata Theory, pages 125\u2013129, 1972.","key":"48_CR14","DOI":"10.1109\/SWAT.1972.29"},{"key":"48_CR15","volume-title":"COINS Technical Report CAR-TR-267 & CS-TR-1787 & AFOSR-86-0092","author":"P. Narendran","year":"1987","unstructured":"Paliath Narendran and Kamela Krithivasan. On the membership problem for some grammars. COINS Technical Report CAR-TR-267 & CS-TR-1787 & AFOSR-86-0092, Center for Automaton Research, University of Maryland, College Park, MD 20742, March 1987."},{"key":"48_CR16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"Walter L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21:218\u2013235, 1980.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: preliminary report. In Proc. of 5th STOC, pages 1\u20139, 1973.","key":"48_CR17","DOI":"10.1145\/800125.804029"},{"key":"48_CR18","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"Klaus W. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatics, 23:325\u2013356, 1986.","journal-title":"Acta Informatics"}],"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_174.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:01Z","timestamp":1605647641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_174","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}