{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T16:52:21Z","timestamp":1769359941671,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1979,12,1]],"date-time":"1979-12-01T00:00:00Z","timestamp":312854400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1979,12]]},"DOI":"10.1007\/bf01744286","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T08:45:05Z","timestamp":1118911505000},"page":"29-43","source":"Crossref","is-referenced-by-count":22,"title":["Complexity of some problems concerningL systems"],"prefix":"10.1007","volume":"13","author":[{"given":"Neil D.","family":"Jones","sequence":"first","affiliation":[]},{"given":"Sven","family":"Skyum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01744286_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974."},{"key":"BF01744286_CR2","unstructured":"H. Alt and K. Mehlhorn, Lower bounds for the space complexity of context-free recognition, in S. Michaelson, and R. Milner,Automata, Languages and Programming, (3rd Coll., Edinburgh), University Press, Edinburgh, Scotland, 338\u2013354, 1976."},{"key":"BF01744286_CR3","first-page":"169","volume":"13","author":"T. Harju","year":"1977","unstructured":"T. Harju, A polynomial recognition algorithm for the EDT0L languages, Elektro. Inform. Kybernetik 13, 169\u2013177, 1977.","journal-title":"Elektro. Inform. Kybernetik"},{"key":"BF01744286_CR4","volume-title":"Developmental Systems and Languages","author":"G. T. Herman","year":"1975","unstructured":"G. T. Herman and G. Rozenberg,Developmental Systems and Languages, North-Holland, Amsterdan, 1975."},{"key":"BF01744286_CR5","volume-title":"Formal Languages and their Relation to Automata","author":"J. E. Hopcroft","year":"1969","unstructured":"J. E. Hopcroft and J. D. Ullman,Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969."},{"key":"BF01744286_CR6","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1976","unstructured":"N. D. Jones and W. T Laaser, Complete problems for deterministic polynomial Time,Theoretical Comp. Sci. 3, 105\u2013118, 1976.","journal-title":"Theoretical Comp. Sci."},{"key":"BF01744286_CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0019-9958(77)90058-4","volume":"35","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones and S. Skyum, Recognition of deterministic ET0L languages in logarithmic space.Information and Control 35, 177\u2013181, 1977.","journal-title":"Information and Control"},{"key":"BF01744286_CR8","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-08342-1_23","volume":"52","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones and S. Skyum, Complexity of some problems concerningL systems, A. Salomaa and M. Steinby,Automata, Languages and Programming, (4th Coll., Turku), Springer Lecture Notes in Computer Science 52, 301\u2013308, 1977.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"BF01744286_CR9","doi-asserted-by":"crossref","unstructured":"P. M. Lewis III R. E. Stearns and J. Hartmanis, Memory bounds for the recognition of context-free and context-sensitive languages,IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, 191\u2013202, 1965.","DOI":"10.1109\/FOCS.1965.14"},{"key":"BF01744286_CR10","doi-asserted-by":"crossref","unstructured":"A. R. Meyer and L. J. Stockmeyer, The Equivalence problem for regular expressions with squaring requires exponential space,Conf. Rec. 13th Annual IEEE Symposium on Switching and Automata Theory, Baltimore, 125\u2013129, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"BF01744286_CR11","doi-asserted-by":"crossref","unstructured":"J. Seiferas, M. Fischer, and A. Meyer, Refinements of nondeterministic time and space hierarchies,Conf. Rec. 14th Annual IEEE Symposium on Switching and Automata Theory, Iowa, 130\u2013137, 1973.","DOI":"10.1109\/SWAT.1973.25"},{"key":"BF01744286_CR12","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time,Proc. 5th Annual ACM Symposium on Theory of Computing, Austin, May 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"BF01744286_CR13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough, A note on tape-bounded complexity classes and linear context-free languages,J. ACM 22, 499\u2013500, 1975.","journal-title":"J. ACM"},{"key":"BF01744286_CR14","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/3-540-08342-1_40","volume":"52","author":"I. H. Sudborough","year":"1977","unstructured":"I. H. Sudborough, The time and tape complexity of developmental languages, in: Salomaa, A., Steinby, M.,Automata, Languages and Programming, (4th Coll., Turku), Springer Lecture Notes in Computer Science 52, 509\u2013523, 1977.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"BF01744286_CR15","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant, General context-free recognition in less than cubic time.J. Computer and Systems Sciences 10, 308\u2013315, 1975.","journal-title":"J. Computer and Systems Sciences"},{"key":"BF01744286_CR16","unstructured":"J. van Leeuwen, Deterministically recognizing E0L languages in timeO(n 3.81). Tech. Rep. Math. Centrum, Amsterdam (1975)."},{"key":"BF01744286_CR17","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0020-0190(75)90027-7","volume":"3","author":"J. Leeuwen van","year":"1975","unstructured":"J. van Leeuwen, The membership question for ET0L languages is polynomially complete,Information Processing Letters 3, 138\u2013143, 1975.","journal-title":"Information Processing Letters"},{"key":"BF01744286_CR18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0022-0000(75)80068-7","volume":"15","author":"J. Leeuwen van","year":"1975","unstructured":"J. van Leeuwen, The tape complexity of context-independent developmental languages,J. Computer and Systems Sciences 15, 203\u2013211, 1975.","journal-title":"J. Computer and Systems Sciences"},{"key":"BF01744286_CR19","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-06867-8_5","volume":"15","author":"P. M. B. Vit\u00e1nyi","year":"1974","unstructured":"P. M. B. Vit\u00e1nyi, On the size of D0L languages, in Rozenberg, G. and Salomaa, A. (ed.)L Systems, Springer Lecture Notes in Computer Science 15, 72\u201377, 1974.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"BF01744286_CR20","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 Timen 3,Information and Control 10, 189\u2013208, 1967.","journal-title":"Information and Control"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744286.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744286\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:25:02Z","timestamp":1586287502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,12]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1979,12]]}},"alternative-id":["BF01744286"],"URL":"https:\/\/doi.org\/10.1007\/bf01744286","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,12]]}}}