{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:38Z","timestamp":1725664178539},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_83","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:32Z","timestamp":1330257572000},"page":"313-324","source":"Crossref","is-referenced-by-count":3,"title":["Growing context-sensitive languages and Church-Rosser languages"],"prefix":"10.1007","author":[{"given":"Gerhard","family":"Buntrock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"G. Buntrock and K. Lory\u015b. On growing context-sensitive languages. In Proc. of 19th ICALP, LNCS, 623:77\u201388, Springer, 1992.","DOI":"10.1007\/3-540-55719-9_65"},{"key":"27_CR2","volume-title":"PhD Diss.","author":"R. V. Book","year":"1969","unstructured":"R. V. Book. Grammars with Time Functions. PhD Diss., Harvard University, Cambridge, MA, 1969."},{"key":"27_CR3","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, 9:171\u2013181, 1978.","journal-title":"Acta Informatica"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R. V. Book","year":"1982","unstructured":"R. V. Book. Confluent and other types of Thue systems. Journal of the ACM, 29:171\u2013182, 1982.","journal-title":"Journal of the ACM"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"R. V. Book and F. Otto. String-Rewriting Systems. Springer, 1993.","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"F.J. Brandenburg. On one-way auxiliary pushdown automata. In Proc. of 3rd GI-Conference on Theoretical Computer Science, LNCS, 48:132\u2013144, Springer, 1977.","DOI":"10.1007\/3-540-08138-0_11"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"G. Buntrock. Growing context-sensitive languages and automata. Preprint, Nr. 69. Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, November 1993.","DOI":"10.1007\/3-540-55719-9_65"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"M. Chytil. Analysis of the non-context-free component of formal languages. In Proc. of 5th MFCS, LNCS, 45:230\u2013236, Springer, 1976.","DOI":"10.1007\/3-540-07854-1_179"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"M. Chytil. Comparison of the active visiting and the crossing complexities. In Proc. of 6th MFCS, LNCS, 53:272\u2013281, Springer, 1977.","DOI":"10.1007\/3-540-08353-7_145"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"E. Dahlhaus and M. K. Warmuth. Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences, 33:456\u2013472, 1986.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/321466.321475","volume":"15","author":"S. Ginsburg","year":"1968","unstructured":"S. Ginsburg and M. A. Harrison. One-way nondeterministic real-time liststorage languages. Journal of the ACM, 15:428\u2013447, 1968.","journal-title":"Journal of the ACM"},{"key":"27_CR12","first-page":"29","volume":"3","author":"A. W. Gladkij","year":"1964","unstructured":"A. W. Gladkij. On the complexity of derivations for context-sensitive grammars. Algebri i Logika Sem., 3:29\u201344, 1964. In Russian.","journal-title":"Algebri i Logika Sem."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and S. R. Mahaney. One-way log-tape reductions. In Proc. of 19th FOCS, 1978, 65\u201371.","DOI":"10.1109\/SFCS.1978.31"},{"key":"27_CR14","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"P. Jan\u010dar, F. Mr\u00e1z, and M. Pl\u00e1tek. A taxonomy of forgetting automata. In Proc. of 18th MFCS, LNCS, 711:527\u2013536, Springer, 1993.","DOI":"10.1007\/3-540-57182-5_44"},{"key":"27_CR16","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01692511","volume":"2","author":"D. E. Knuth","year":"1968","unstructured":"D. E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2:127\u2013145, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"27_CR17","unstructured":"C. Lautemann. One pushdown and a small tape. In K. Wagner, ed., Dirk Siefkes zum 50. Geburtstag, pages 42\u201347. Technische Universit\u00e4t Berlin and Universit\u00e4t Augsburg, 1988."},{"issue":"2","key":"27_CR18","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"R. McNaughton, P. Narendran, and F. Otto. Church-Rosser Thue systems and formal languages. Journal of the ACM, 35(2):324\u2013344, 1988.","journal-title":"Journal of the ACM"},{"key":"27_CR19","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, 21:218\u2013235, 1980.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"27_CR20","doi-asserted-by":"crossref","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(3):405\u2013414, 1978.","journal-title":"Journal of the ACM"},{"key":"27_CR21","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0019-9958(70)80005-5","volume":"17","author":"D. A. Walters","year":"1970","unstructured":"D. A. Walters. Deterministic context-sensitive languages: Part II. Information and Control, 17:41\u201361, 1970.","journal-title":"Information and Control"},{"key":"27_CR22","volume-title":"Computational Complexity","author":"K. Wagner","year":"1986","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. VEB Deutscher Verlag der Wissenschaften and Reidel Verlag, Dordrecht, 1986."}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_83.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:25:14Z","timestamp":1605630314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_83","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}