Abstract
This paper introduces a new family of languages which originated from a study of some mathematical models for the development of biological organisms. Various properties of this family are established and in particular it is proved that it forms a full abstract family of languages. It is compared with some other families of languages which have already been studied and which either originated from the study of models for biological development or belong to the now standard Chomsky hierarchy. A characterization theorem for context-free languages is also established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. Baker and G. T. Herman, “Simulation of organisms using a developmental model, Parts I and II,”Int. J. Bio-Med. Comp., to appear.
E. F. Codd,Cellular Automata (Academic Press, New York, 1968).
D. van Dalen, “A note on some systems of Lindenmayer,”Math. Systems Theory 5:128–140 (1971).
P. Doucet, “On the membership question in some Lindenmayer systems,”Indag. Math. 34:45–52 (1972).
H. Feliciangeli and G. T. Herman, “Algorithms for producing grammars from sample derivations,”J. Comp. Syst. Sci., to appear.
S. Ginsburg,The Mathematical Theory of Context-Free Languages (McGraw-Hill, New York, 1966).
S. Ginsburg and S. Greibach, “Abstract families of languages,”Mem. Am. Math. Soc. 87:1–32 (1969).
G. T. Herman, “The computing ability of a developmental model for filamentous organisms,”J. Theoret. Biol. 25:421–435 (1969).
G. T. Herman, “The role of environment in developmental models,”J. Theoret. Biol. 29:329–341 (1970.
G. T. Herman, “Models for cellular interactions in development without polarity of individual cells, Parts I and II.”Int. J. Systems Sci. 2:271–289 (1971):3:149–175 (1972).
G. T. Herman, “Closure properties of families of languages associated with biological systems,” submitted to a technical journal, abstract inProc. 5th Annual Princeton Conf. Inf. Sciences Syst., 1971.
G. T. Herman, “Polar organisms with apolar individual cells,” inProc. Int. Congr. on Logic, Math, and Phil, of Science, 1971.
G. T. Herman, “The syntactic inference problem as applied to biological systems,” to appear inMachine Intelligence 7.
G. T. Herman, “A biologically motivated extension of Algol-like languages,” to appear inInformation and Control.
G. T. Herman, K. P. Lee, J. van Leeuwen, and G. Rozenberg, “Characterization of unary developmental languages,” to appear inDiscrete Mathematics.
G. T. Herman, A. Lindenmayer, and G. Rozenberg, “Description of developmental systems using recurrence systems,” submitted to a technical journal.
J. E. Hopcroft and J. D. Ullman,Formal Languages and Their Relation to Automata (Addison-Wesley, Reading, Mass., 1969).
A. Lindenmayer, “Mathematical models for cellular interactions in development, Parts I and II,”J. Theoret. Biol. 18:280–315 (1968).
A. Lindenmayer, “Developmental systems without cellular interactions, their languages and grammars,”J. Theoret. Biol. 30:455–484 (1971).
A. Lindenmayer, “Cellular automata, formal languages and developmental systems,” inProc. Int. Congr. on Logic, Math, and Phil, of Science, 1971.
A. Lindenmayer and G. Rozenberg, “Developmental systems and languages,” inProc. 4th ACM Symp. Theory Comp. (1972), pp. 214–221.
A. Paz and A. Salomaa, “Integral sequential word functions and growth equivalence of Lindenmayer systems,” submitted to a technical journal.
D. J. Rosenkrantz, “Programmed grammars and classes of formal languages,”J. Assoc. Comp. Mach. 16:107–131 (1969).
G. Rozenberg, “TOL systems and languages,” to appear inInformation and Control.
G. Rozenberg, “OnQL languages with restricted use of productions,” to appear inJ. Comp. Syst. Sci.
G. Rozenberg, “The equivalence problem for deterministic TOL-systems is undecidable,”Inf. Processing Letters,1:201–204 (1972).
G. Rozenberg, “Z-systems with interactions,” to appear inJ. Comp. Syst. Sci.
G. Rozenberg, “DOL sequences,” submitted to a technical journal.
G. Rozenberg, “Circularities inDOL sequences,” to appear inRevue Raum, de Math. Pures et Appl.
G. Rozenberg, “Direct proofs of the unsolvability of the equivalence problem for sentential forms of context-free grammars and the equivalence problem forQL systems,” to appear inInf. Processing Letters.
G. Rozenberg, “On a machine model forL-systems without interactions,” submitted to a technical journal.
G. Rozenberg and P. Doucet, “On OL languages,”Information and Control 19:302–318 (1971).
G. Rozenberg and K. P. Lee, “Some properties of the class ofL-languages with interactions,” submitted to a technical journal.
G. Rozenberg and K. P. Lee, “Developmental systems with finite axiom sets, Parts I and II,” submitted to a technical journal.
G. Rozenberg and A. Lindenmayer, “Developmental systems with locally catenative formulas,” submitted to a technical journal.
V. Surapipith and A. Lindenmayer, “Thioquanine-dependent light sensitivity of Perithecial initiation in Sordia flmicola,”J. Gen. Microb. 57:227–237 (1969).
Author information
Authors and Affiliations
Additional information
This research has been supported by NSF Grant GJ 998.
Rights and permissions
About this article
Cite this article
Rozenberg, G. Extension of tabled 0L-systems and languages. International Journal of Computer and Information Sciences 2, 311–336 (1973). https://doi.org/10.1007/BF00985664
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00985664