×

The tape-complexity of context-independent developmental languages. (English) Zbl 0314.68017


MSC:

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

References:

[1] Aho, A. V.; Ullman, J. D., (The Theory of Parsing, Translation, and Compiling, Vol. I (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J.)
[2] Cook, S. A., Path systems and language recognition, (Proc. ACM Symp. on Theory of Computing (1970)), 70-72
[3] Culik, K.; Opatrny, J., (Macro \(0L\)-languages, Tech. Rept. CS-73-06 (1973), Dept. of Applied Analysis and Computer Science., Univ. of Waterloo: Dept. of Applied Analysis and Computer Science., Univ. of Waterloo Waterloo, Canada)
[4] Downey, P. J., Formal languages and recursion schemes, (Ph.D. Thesis, TR 16-74 (1974), Center for Research in Computing Technology, Harvard Univ.: Center for Research in Computing Technology, Harvard Univ. Cambridge, Mass.)
[5] Ginsburg, S., (Algebraic and Automata-Theoretic Properties of Formal Languages (1974), North-Holland: North-Holland Amsterdam) · Zbl 0352.68094
[6] Ginsburg, S.; Greibach, S. A.; Hopcroft, J. E., Studies in abstract families of languages, Mem. Amer. Math. Soc., 87 (1969) · Zbl 0194.31402
[7] Herman, G. T., A biologically motivated extension of ALGOL-like languages, Inform. Contr., 22, 487-502 (1973) · Zbl 0257.68009
[8] G. T. Herman and G. Rozenberg; G. T. Herman and G. Rozenberg · Zbl 0306.68045
[9] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[10] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory-bounds for recognition of context-free and context-sensitive languages, (IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965)), 191-202 · Zbl 0272.68054
[11] Lindenmayer, A., Mathematical models for cellular interactions in development, J. Theoret. Biol., 28, 300-315 (1968)
[12] Lindenmayer, A., Developmental systems without cellular interactions, their languages and grammars, J. Theoret. Biol., 30, 455-484 (1971)
[13] Lindenmayer, A., Cellular automata, formal languages and developmental systems, (Proc. Fourth Internat. Cong. on Logic, Methods and Philosophy of Science. Proc. Fourth Internat. Cong. on Logic, Methods and Philosophy of Science, Bucharest (1971)) · Zbl 0353.68087
[14] Salomaa, A., On some recent problems concerning developmental, languages, (Paper presented at Computer Science Conference. Paper presented at Computer Science Conference, Bonn, West Germany (1973)) · Zbl 0278.68070
[15] Salomaa, A., (Formal Languages (1973), Academic Press: Academic Press New York) · Zbl 0262.68025
[16] Salomaa, A., Macros, iterated substitution and Lindenmayer AFLs, (DAIMI-PB18 (1973), Dept. of Computer Science, Univ. of Aarhus: Dept. of Computer Science, Univ. of Aarhus Aarhus, Denmark)
[17] Savitch, W. J., Relationships between non-deterministic and deterministic tape-complexities, J. Comput System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[18] van Leeuwen, J., Preset push-down automata and \(0L\)-grammars, (Tech. Rept. 10 (1973), Univ. of California: Univ. of California Berkeley)
[19] van Leeuwen, J., \(F\)-iteration languages, (Tech. Memorandum (1973), Univ. of California: Univ. of California Berkeley)
[20] van Leeuwen, J., On the efficient validation of execution sequences of simple recursive and parallel program-schemata, (Paper presented at Symp on Complexity of Sequential and Parallel Numerical Algorithms. Paper presented at Symp on Complexity of Sequential and Parallel Numerical Algorithms, Carnegie-Mellon Univ., Pittsburgh, Pa. (1973))
[21] van Leeuwen, J.; Wood, D., A decomposition theorem for hyperalgebraic extensions of language-families, (Tech. Rept. 74/6 (1974), Dept. of Applied Mathematics, McMaster University: Dept. of Applied Mathematics, McMaster University Hamilton, Ontario, Canada), (to appear in Theor. Comput. Sci.)
[22] Younger, D. H., Recognition and parsing of context-free languages in time \(n^3\), Inform. Contr., 19, 189-208 (1967) · Zbl 0149.24803
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.