{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:56:04Z","timestamp":1794336964645,"version":"4.9.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":22,"publisher":"Springer-Verlag","isbn-type":[{"value":"354016443X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022661","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T00:51:59Z","timestamp":1132707119000},"page":"85-99","source":"Crossref","is-referenced-by-count":1,"title":["Membership for growing context sensitive grammars is polynomial"],"prefix":"10.1007","author":[{"given":"Elias","family":"Dahlhaus","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred K.","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"8_CR1","first-page":"143","volume":"14","author":"Y. M. Bar-Hillel","year":"1961","unstructured":"Y. M. Bar-Hillel, M. Perles, and E. Shamir, \"On Formal Properties of Simple Phase Structure Grammars,\" Z. Phonetik Sprachwiss. Kommunikationsforschung, Vol. 14, pp. 143\u2013172 (1961).","journal-title":"Z. Phonetik Sprachwiss. Kommunikationsforschung"},{"key":"8_CR2","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/S0022-0000(71)80025-9","volume":"5","author":"R. V. Book","year":"1971","unstructured":"R. V. Book, \"Time Bounded Grammars and their Languages,\" Journal of Computer and Systems Sciences, Vol. 5, pp. 397\u2013429 (1971).","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF00976059","volume":"2","author":"R. V. Book","year":"1973","unstructured":"R. V. Book, \"On the Structure of Context-Sensitive Grammar,\" International Journal of Computer and Information Sciences, Vol. 2, No. 2, pp. 129\u2013139 (1973).","journal-title":"International Journal of Computer and Information Sciences"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00289076","volume":"9","author":"R. V. Book","year":"1978","unstructured":"R. V. Book, \"On the Complexity of Formal Grammars,\" Acta Informatica, Vol. 9, pp. 171\u2013182 (1978).","journal-title":"Acta Informatica"},{"key":"8_CR5","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N. Chomsky","year":"1959","unstructured":"N. Chomsky, \"A Note on Phase-Structure Grammars,\" Information and Control, Vol. 2, pp. 137\u2013167 (1959).","journal-title":"Information and Control"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"S. A. Cook, \"Path Systems and Language Recognition,\" Proc. Second Annual ACM Symposium on Theory of Computing, pp. 70\u201372 (1970).","DOI":"10.1145\/800161.805151"},{"issue":"5\u20136","key":"8_CR7","first-page":"29","volume":"3","author":"A. Gladkii","year":"1964","unstructured":"A. Gladkii, \"On the Complexity of Derivations in Phase-Structure Grammars,\" (in Russian), Algebri i Logika, Sem. 3, Nr. 5\u20136, pp.29\u201344 (1964).","journal-title":"Algebri i Logika"},{"issue":"3","key":"8_CR8","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0022-0000(85)90046-7","volume":"30","author":"J. Gonczarowski","year":"1985","unstructured":"J. Gonczarowski and E. Shamir, \"Pattern Selector Grammars and Several Parsing Algorithms in the Context-Free Style,\" Journal of Computer and System Sciences, Vol. 30, No. 3, pp. 249\u2013273 (1985).","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"8_CR9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(85)90092-1","volume":"37","author":"J. Gonczarowski","year":"1985","unstructured":"J. Gonczarowski and M. K. Warmuth, \"Applications of Scheduling Theory to Formal Language Theory,\" Fundamental Studies Issue of Theoretical Computer Science, Vol. 37, No. 2, pp. 217\u2013243 (1985).","journal-title":"Fundamental Studies Issue of Theoretical Computer Science"},{"key":"8_CR10","unstructured":"J. Gonczarowski and M. K. Warmuth, \"Manipulating Derivation Forests by Scheduling Techniques,\" Technical Report 85-3, Department of Computer Science, Hebrew University of Jerusalem."},{"key":"8_CR11","unstructured":"J. Gonczarowski and M. K. Warmuth, \"On the Complexity of Scattered Grammars,\" in preparation."},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0022-0000(69)80015-2","volume":"3","author":"S. Greibach","year":"1969","unstructured":"S. Greibach and J. Hopcraft, \"Scattered Context Grammars,\" Journal of Computer and Systems Sciences, Vol. 3, pp. 233\u2013249 (1969).","journal-title":"Journal of Computer and Systems Sciences"},{"key":"8_CR13","volume-title":"Introduction to Formal Language Theory","author":"M. A. Harrison","year":"1978","unstructured":"M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass. (1978)."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"R. M. Karp, \"Reducibility among Combinatorial Problems,\" in: R. E. Miller and J. W. Thatcher (eds.) Complexity of Computer Computations, Plenum Press, pp. 85\u2013103, New York (1972).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"8_CR15","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, Vol. 7, pp. 207\u2013223 (1964).","journal-title":"Information and Control"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/S0019-9958(70)90224-X","volume":"16","author":"J. Loeckx","year":"1970","unstructured":"J. Loeckx, \"The Parsing of General Phase-Structure Grammars,\" Information and Control, Vol. 16, pp. 443\u2013464 (1970).","journal-title":"Information and Control"},{"key":"8_CR17","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"W. L. Ruzzo, \"Tree-Size Bounded Alternation,\" Journal of Computer and System Sciences, Vol. 21, pp. 218\u2013235 (1980).","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR18","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"A. Salomaa, Formal Languages, Academic Press, N.Y. (1973)."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"P. M. Lewis, R. E. Stearns and J. Hartmanis, \"Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages,\" Proc. Sixth Annual IEEE Symposium Switching Circuit Theory and Logical Design, pp. 191\u2013212 (1965).","DOI":"10.1109\/FOCS.1965.14"},{"key":"8_CR20","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"H. Sudborough","year":"1978","unstructured":"H. Sudborough, \"On the Tape Complexity of Deterministic Context-Free Languages,\" Journal of the ACM, Vol. 25, pp. 405\u2013414 (1978).","journal-title":"Journal of the ACM"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"J. D. Ullman and A. V. Gelder, \"Parallel Complexity of Logical Query Programs,\" Technical Report, Department of Computer Science, Stanford University (1985).","DOI":"10.1109\/SFCS.1986.40"},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D. H. Younger","year":"1967","unstructured":"D. H. Younger, \"Recognition and Parsing of Context-Free Languages in Time n3,\" Information and Control, Vol. 10, pp. 189\u2013208 (1967).","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","CAAP '86"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0022661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T03:07:58Z","timestamp":1626750478000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354016443X"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0022661","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0022653","asserted-by":"object"}]},"subject":[]}}