{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T21:56:01Z","timestamp":1767909361504,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540083429","type":"print"},{"value":"9783540373056","type":"electronic"}],"license":[{"start":{"date-parts":[[1977,1,1]],"date-time":"1977-01-01T00:00:00Z","timestamp":220924800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08342-1_23","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:21:40Z","timestamp":1330186900000},"page":"301-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Complexity of some problems concerning L systems"],"prefix":"10.1007","author":[{"given":"Neil D.","family":"Jones","sequence":"first","affiliation":[]},{"given":"Sven","family":"Skyum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"23_CR1","first-page":"338","volume-title":"Automata, Languages and Programming","author":"H. Alt","year":"1976","unstructured":"Alt, H., Mehlhorn, K. Lower bounds for the space complexity of context-free recognition. Automata, Languages and Programming, 338\u2013354, July 1976, University Press, Edinburgh, Scotland."},{"key":"23_CR2","unstructured":"Hopcroft, J.E., Ullman, J.D. Formal Languages and their Relation to Automata, Addison-Wesley, 1969, 242 pp."},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Jones, N.D., Laaser, W.T., Complete Problems for Deterministic Polynomial Time, J. Theoretical Computer Science, 1976.","DOI":"10.1016\/0304-3975(76)90068-2"},{"key":"23_CR4","unstructured":"Jones, N.D., Skyum, S., EDTOL. Membership in Polynomial Time, Technical Report, University of Aarhus, Denmark."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Lewis, P.M., Stearns, R.E., Hartmanis, J., Memory Bounds for the Recognition of Context-free and Context-sensitive Languages, IEEE Conf. Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, pp. 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J., The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, 13th IEEE Symposium on Switching and Automata Theory, Oct. 1972, pp. 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"23_CR7","volume-title":"Time Complexity of L Languages, Abstracts of papers, Conference on formal languages, automata and development","author":"J. Opatrn\u00fd","year":"1975","unstructured":"Opatrn\u00fd, J., Culik, K. II, Time Complexity of L Languages, Abstracts of papers, Conference on formal languages, automata and development, University of Utrecht, Netherlands, 1975."},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R., Word Problems requiring Exponential Time, 5th ACM Symposium on Theory of Computing, May 1973, pp. 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I. H. Sudborough","year":"1975","unstructured":"Sudborough, I.H., A note on Tape-bounded Complexity Classes and Linear Context-free Languages, J. ACM 22, 1975, pp. 499\u2013500.","journal-title":"J. ACM"},{"key":"23_CR10","series-title":"Technical Report","volume-title":"The Complexity of the Membership Problem for some Extensions of Context-free Languages","author":"I. H. Sudborough","year":"1976","unstructured":"Sudborough, I.H., The Complexity of the Membership Problem for some Extensions of Context-free Languages, Technical Report, Northwestern University Computer Science Dept., Evanston, Ill., 1976."},{"key":"23_CR11","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0020-0190(75)90027-7","volume":"3","author":"J. Leeuwen van","year":"1975","unstructured":"van Leeuwen, J., The Membership Question for ET0L Languages is Polynomially Complete, Information Processing Letters 3, 1975, pp. 138\u2013143.","journal-title":"Information Processing Letters"},{"key":"23_CR12","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0022-0000(75)80068-7","volume":"15","author":"J. Leeuwen van","year":"1975","unstructured":"van Leeuwen, J., The Tape Complexity of Context-independent Developmental Languages, J. Computer and Systems Sciences 15, 1975, pp. 203\u2013211.","journal-title":"J. Computer and Systems Sciences"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Younger, D.H., Recognition and Parsing of Context-free Languages in Time n3, Information and Control 10:2, pp. 189\u2013208.","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08342-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:00:06Z","timestamp":1742587206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08342-1_23"}},"subtitle":["Preliminary report"],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083429","9783540373056"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-08342-1_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977]]},"assertion":[{"value":"24 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}