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


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


[1] Aho, A.V.; Ullman, J.D., ()
[2] Cook, S.A., Path systems and language recognition, (), 70-72
[3] Culik, K.; Opatrny, J., ()
[4] Downey, P.J., Formal languages and recursion schemes, ()
[5] Ginsburg, S., ()
[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] {\scG. T. Herman and G. Rozenberg}, “Developmental Systems and Languages,” North-Holland, Amsterdam, to appear. · Zbl 0306.68045
[9] Hopcroft, J.E.; Ullman, J.D., ()
[10] Lewis, P.M.; Stearns, R.E.; Hartmanis, J., Memory-bounds for recognition of context-free and context-sensitive languages, (), 191-202 · Zbl 0272.68054
[11] Lindenmayer, A.; Lindenmayer, A., Mathematical models for cellular interactions in development, J. theoret. biol., 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, () · Zbl 0353.68087
[14] Salomaa, A., On some recent problems concerning developmental, languages, () · Zbl 0278.68070
[15] Salomaa, A., ()
[16] Salomaa, A., Macros, iterated substitution and lindenmayer afls, ()
[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, ()
[19] van Leeuwen, J., F-iteration languages, ()
[20] van Leeuwen, J., On the efficient validation of execution sequences of simple recursive and parallel program-schemata, ()
[21] van Leeuwen, J.; Wood, D., A decomposition theorem for hyperalgebraic extensions of language-families, (), (to appear in Theor. Comput. Sci.)
[22] Younger, D.H., Recognition and parsing of context-free languages in time n3, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.