Complexity of some problems concerning L systems. (English) Zbl 0449.68038


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. · Zbl 0326.68005
[2] 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–354, 1976. · Zbl 0368.68069
[3] T. Harju, A polynomial recognition algorithm for the EDT0L languages, Elektro. Inform. Kybernetik 13, 169–177, 1977. · Zbl 0365.68043
[4] G. T. Herman and G. Rozenberg,Developmental Systems and Languages, North-Holland, Amsterdan, 1975. · Zbl 0306.68045
[5] J. E. Hopcroft and J. D. Ullman,Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. · Zbl 0196.01701
[6] N. D. Jones and W. T Laaser, Complete problems for deterministic polynomial Time,Theoretical Comp. Sci. 3, 105–118, 1976. · Zbl 0352.68068 · doi:10.1016/0304-3975(76)90068-2
[7] N. D. Jones and S. Skyum, Recognition of deterministic ET0L languages in logarithmic space.Information and Control 35, 177–181, 1977. · Zbl 0374.68050 · doi:10.1016/S0019-9958(77)90058-4
[8] 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–308, 1977.
[9] 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–202, 1965.
[10] 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–129, 1972.
[11] 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–137, 1973.
[12] L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time,Proc. 5th Annual ACM Symposium on Theory of Computing, Austin, May 1–9, 1973. · Zbl 0359.68050
[13] I. H. Sudborough, A note on tape-bounded complexity classes and linear context-free languages,J. ACM 22, 499–500, 1975. · Zbl 0318.68048 · doi:10.1145/321906.321913
[14] 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–523, 1977.
[15] L. G. Valiant, General context-free recognition in less than cubic time.J. Computer and Systems Sciences 10, 308–315, 1975. · Zbl 0312.68042 · doi:10.1016/S0022-0000(75)80046-8
[16] J. van Leeuwen, Deterministically recognizing E0L languages in timeO(n 3.81). Tech. Rep. Math. Centrum, Amsterdam (1975).
[17] J. van Leeuwen, The membership question for ET0L languages is polynomially complete,Information Processing Letters 3, 138–143, 1975. · Zbl 0309.68065 · doi:10.1016/0020-0190(75)90027-7
[18] J. van Leeuwen, The tape complexity of context-independent developmental languages,J. Computer and Systems Sciences 15, 203–211, 1975. · Zbl 0314.68017
[19] P. M. B. Vitányi, On the size of D0L languages, in Rozenberg, G. and Salomaa, A. (ed.)L Systems, Springer Lecture Notes in Computer Science 15, 72–77, 1974.
[20] D. H. Younger, Recognition and parsing of context-free languages in Timen 3,Information and Control 10, 189–208, 1967. · Zbl 0149.24803 · doi:10.1016/S0019-9958(67)80007-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.