Skip to main content
Top

1986 | Book

The Book of L

Authors: Professor Dr. G. Rozenberg, Professor A. Salomaa

Publisher: Springer Berlin Heidelberg

insite
SEARCH

About this book

This book is dedicated to Aristid Lindenmayer on the occasion of his 60th birthday on November 17, 1985. Contributions range from mathematics and theoretical computer science to biology. Aristid Lindenmayer introduced language-theoretic models for developmental biology in 1968. Since then the models have been cus­ tomarily referred to as L systems. Lindenmayer's invention turned out to be one of the most beautiful examples of interdisciplinary science: work in one area (developmental biology) induces most fruitful ideas in other areas (theory of formal languages and automata, and formal power series). As evident from the articles and references in this book, the in­ terest in L systems is continuously growing. For newcomers the first contact with L systems usually happens via the most basic class of L systems, namely, DOL systems. Here "0" stands for zero context between developing cells. It has been a major typographical problem that printers are unable to distinguish between 0 (zero) and 0 (oh). Thus, DOL was almost always printed with "oh" rather than "zero", and also pronounced that way. However, this misunderstanding turned out to be very fortunate. The wrong spelling "DOL" of "DOL" could be read in the suggestive way: DO L Indeed, hundreds of researchers have followed this suggestion. Some of them appear as contributors to this book. Of the many who could not contribute, we in particular regret the absence of A. Ehrenfeucht, G. Herman and H.A. Maurer whose influence in the theory of L systems has been most significant.

Table of Contents

Frontmatter
Investigations Into Drosophila Wing Development—Results from a Lindenmayer Model

In this time of significant and exciting new understandings in genetics, there has been a persistent, but largely unfulfilled expectation that the instructions for generating an organism are somehow directly encoded in its genetic program, and that full understanding of developmental mechanisms would accompany knowledge of the molecular mechanisms of gene control. We are now realizing that a simple, one-step explanation of development at this ultimate reductionist level is unlikely. As Brenner puts it (quoted in Lewin, 1984) “Ultimately the organism must be explicable in terms of its genes,… But the representation will not be explicit. We need to understand the grammar of development to make sense of it.” It is this grammar of spatial and dynamic organization of complex systems that Lindenmayer’s algorithms seek to model.

Lois A. Abbott
Fibonacci Words — A Survey

Fibonacci words have many amazing combinatorial properties. Like Fibonacci numbers they are easy to define, and many of their properties are easy to prove, once discovered. The aim of this survey is to sketch some of the combinatorial properties related to factors (subwords) of Fibonacci words, and also to describe basic arithmetic operations (i.e. normalization and addition) in the Fibonacci number system. No attempt was made to be complete.

Jean Berstel
Planar Map Generation by Parallel Binary Fission/Fusion Grammars

A new class of formal grammatical systems, based upon simultaneous (parallel) rewriting of symbols in strings, was introduced by A. Lindenmayer [1], intended as a theoretical model for development of filamentous biological organisms, e.g., by cell-division. Lindenmayer’s contributions have stimulated widespread interest and research in theoretical models for parallel generation in computer science as well as in biology. Initial advances pertained to string-based systems, i.e., linear or one-dimensional structures, but were followed by numerous proposals for addressing the difficult problem of generalization to nonlinear systems, capable of modeling development in two- or three-dimensional organisms or complex data structures. Some references to multi-dimensional or graph generation are given here [2,3,4,6,7,8,9,10,12,13,14,17], with emphasis on those relating to parallel generation, but space permits us only limited coverage, which may be augmented by consulting a recent comprehensive bibliography [16].

Jack W. Carlyle, Sheila A. Greibach, Azaria Paz
Modular Trellises

Modular trellises are infinite two-dimensional words which are limits of developmental sequences of a very natural two-dimensional generalization of PDOL-systems.The original motivation to investigate modular trellises came from the area of systolic automata. Modular trellises represent there a class of very modular nonhomogeneous arrays of processors.Modular trellises are also a natural generalization of the Cobham’s /Co 72/ construction of uniform tag sequences based on iterating uniform morphisms.We first present here various properties of modular trellises and then we give various characterizations of them /in terms of sorting automata and in terms of fixpoints of morphisms and substitutions/. We discuss also the relation between modular and regular trellises /CGS 84/. Finally, decidability of various pattern occurrence problems is shown and decidability of the equivalence problem is discussed.

A. Černý, J. Gruska
A New Proof for the Dol Sequence Equivalence Problem and its Implications

Recently, the validity of the Ehrenfeucht Conjecture on test sets for morphisms has been established. Based on this result we give an entirely new proof of the decidability of the DOL sequence equivalence problem. The new technique is more powerful and allows us to prove that the sequence equivalence problems for HDOL and DTOL sequences are decidable, as well.We also survey the known results on various generalizations of the DOL sequence equivalence problem.

K. Culik II, J. Karhumäki
On Compound Lindenmayer Systems

Motivated by remarks by A, Lindenmayer on the biological relevance of tabled L systems we introduce compound L systems. We study their hierarchy, give their closure properties with respect to AFL-operations and prove the decidability of their sequence equivalence problem for compound L systems with two tables.

Jürgen Dassow
Graph Grammars with Application Conditions

The algebraic approach of graph grammars is extended by a very general notion of application conditions which can be defined separately for each production. This extended approach is applied to a small library system in order to show the flexibility of this concept for the design of systems in computer science and related areas. In addition to the general concept we study some special cases of graph grammars with application conditions with respect to their generative power. Finally we state some facts how to extend known results in the algebraic theory of graph grammars to the case with application conditions.

H. Ehrig, A. Habel
The ETOL Hierarchy is in the oi Hierarchy

There exist several interesting hierarchies of classes of formal languages that start with rather small well-known classes (such as the regular or context-free languages) and contain larger and larger classes, obtained by the iteration of some simple concept. Well-known examples of such hierarchies are the OI hierarchy and the IO hierarchy CWan,Mai,Masl,EngSch,DamJ, the ETOL (control) hierarchy [AsvvLe,Eng2], the 2-way GSM hierarchy [Gre2,Eng2], and the top-down tree transducer hierarchy [OgdRou,Bak,Eng2]. As a contribution to the comparison of these hierarchies we show that the ETOL hierarchy is contained in the OI hierarchy (note that the 2-way GSM hierarchy is contained in the ETOL hierarchy). Since the ETOL hierarchy is obtained by iterating control on ETOL systems (studied in [Nie,GinRoz,Asv,EngRozSlu,Lan]), and the OI hierarchy can be obtained, as recently proved in [DamGoe] (see also [Mas2,EngVog2]), by iterating pushdowns as storage for one-way automata, this is another indication that iterated control is related to iterated pushdowns [Vog].

Joost Engelfriet
Polyhedral cell Shapes

Many authors have discussed the shapes of cells of the parenchyma of plants, and remarked on their similarity of form to bubbles in foam, to the grains of certain metal alloys, and to compressed lead shot, balls of “Plasticene,” and of peas, which have imbibed water while packed in a closed container. In all of these cases the “cells” have a great variety of polyhedral forms, and are closely packed so as to fill space. I will review some of the studies of cell shapes which have been published, and the ideas which have been proposed to account for these shapes. A partial enumeration of the possible polyhedra will be discussed, and some consideration will be given to the packing of these polyhedra.

Ralph O. Erickson
On Cyclically Overlap-free Words in Binary Alphabets

We shall be concerned with avoidable patterns of words on two symbols, a and b. The pattern we are interested in is overlapness: a word x avoids overlapping or is overlap-free if it has no two occurrences of a factor that overlap each other. For example the word aababaa does not avoid overlapping since it contains the factor aba in two occurrences such that these have a common part.

T. Harju
The Theoretical Basis of the Transplantation Experiment

An important question of developmental biology is, whether the parts of an individual pass through a given sequence of states independently from one another, so that the coordination of different developmental processes depends only on a time correlation or whether the development of one part is influenced by transportable agents (e.g. inductors, growth promotors, gene products, hormones) or morphological relations (e.g. cell contact, innervation). As this special problem can arise in different forms, one will be considered as example for the whole group.

Cornelia Harte
Fixed and Stationary ω —Words and ω —Languages

Explicit representations of the ω-words that are fixed (resp., stationary) relative to a function h: A -→ A* are given. A procedure is provided for constructing a concise expression for the fixed (resp., stationary) ω -language of such an h. The equivalence problem for fixed (resp., stationary) ω-languages of functions h & k: A -→ A* is shown to be decidable. The fundamental tool for this latter procedure is the recently developed algorithm of K. Culik II & T. Harju for deciding the ω -sequence equivalence problem.

Tom Head, Barbara Lando
DOL Schemes and Recurrent Words

Let X be a finite alphabet, X* the free monoid generated by X and X+ = X* {1}, where 1 denotes the empty word. Elements of X* are called words and subsets of X* are called languages. A DOL scheme is a pair D = (X,h) where X is a finite alphabet and h is an endomorphism of X*; a DOL system is a triple G = (X,h,ω) where (X,h) is a DOL scheme and ω is a word of X* called the axiom of G (see [4], [5]). The language L(G) generated by G is defined by L(G) = {hn(ω) | n ≥ 0}. A word u is called alive if hn(u) ≠ 1 for n ≥ 1.

M. Ito, G. Thierrin
Stochastic OL Systems and Formal Power Series

It is a common problem in the study of stochastic grammars and languages and, in particular, of stochastic L systems that seemingly very little can be said about the probabilities of the word structures derived; in fact, most of the results obtained so far in these areas deal with word lengths and Parikh vectors rather than with the words themselves. Thus the stochastic generating process of the language is hardly reflected by the typical results.

H. Jürgensen, D. E. Matthews
Complexity of L-Systems
Theme and Études

Despite of the fact that the complexity theory forms a significant and rapidly growing part of theoretical computer science the study of complexity of L-systems is in its beginnings. In the following three études we wish to sketch out some possible directions of such investigations. From the two standard ways of dealing with complexity in TCS — computational and descriptional complexity — we prefer to discuss here the descriptional complexity of L-systems. A survey of descriptional complexity and its comparison with computational complexity of languages can be found in [2]. Results on the computational complexity of L-systems and that on subword complexity of L-systems will be omitted here.

A. Kelemenová
Compartmental Hybrid State Production-Diffusion Systems with Application to Prestalk-Prespore Pattern Regulation in Cellular Slime Molds

Since the works of Rashevsky(1940) and Turing(1952), the modelings of cell differentiation have been more or less identified with those of pattern formation of some chemical substances (morphogens). Their main concern is to account for the scheme of cell differentiation starting from a set of seemingly identical cells. The “diffusive instability” plays an essential role there for breaking the initial uniform state and producing some heterogeneous one. Thus the ultimate patterns obtained in a reaction-diffusion system are supposed to be responsible for the emerging cell state differences.(See, for example, the books by Nicolis and Prigogine(1 977), Murray(1977), and Meinhardt(1982).)

Youichi Kobuchi
Hierarchical Aspects of Plant Development

A universally accepted concept in biology is that organisms have a hierarchical organization such as the cells-tissues-organs-organism series with other levels both above and below this sequence. While this idea is simple to illustrate there is considerable difficulty in providing a definition of each level and distinctions between adjacent levels. When is a group of cells just a group of cells and when is it a tissue, and what makes a group of tissues an organ and how are organs related to constitute an organism? Generally it is thought that there must be some intergrating feature(s) by which a collection of cells, tissues and organs, respectively, become tissues, organs and organism but the identification of the intergration features and their specific roles has not been easy.

Robert W. Korn
Rule Trees Represent Derivations in Edge Replacement Systems

Whoever is looking for context-free graph grammars should consider edge replacement systems as a possibility. This advice is supported by the investigation of rule trees and their relationship to the derivations in an edge replacement system. It turns out that rule trees are quite similar to derivation trees which are an essential element in the theory of context-free Chomsky grammars.

Hans-Jörg Kreowski
Languages Defined by Indian Parallel Systems

A special kind of parallel systems, namely Indian parallel systems, is studied. In the context-independent case the application of homomorphisms on sentential form languages is found to be more powerful than the use of a terminal subalphabet, both for systems with one or finitely many tables. Especially, the language family obtained by systems with one table using a terminal subalphabet is (nearly) an Anti-AFL. The effect of having at most one or finitely many axioms, erasing in the productions, and of applying codings, weak codings, non-erasing or arbitrary homomorphisms is considered, and a (not yet) complete hierarchy is presented, including also the relations to the context-free and ETOL-languages. Some results in the context-dependent case are given too.

Manfred Kudlek
L Systems and Nlog — Reductions

Jones and Skyum in [J Sk 77], [J Sk 79], and [J Sk 81], as well as, van Leeuwen in [vL] and Sudborough in [Su77] classified the complexities of various problems concerning L systems. This was done by showing these problems, formulated as languages, to be complete for complexity classes like NSPACE(log n), DTIME(Poly), NTIME(Poly), or DSPACE(Poly) with respect to deterministic logarithmic space-bounded many-one reductions. The aim of this paper is to do the same for fixed membership problems of context-free L systems with respect to nondeterministic log-space bounded many-one reductions (see [Lan 84]).

Klaus-Jörn Lange
The Parikh-Boundedness of Etol Languages of Finite Index

We prove that ETOL languages of finite index are Parikh-bounded. Namely, every ETOL language of finite index contains a letter-equivalent bounded sublanguage.

M. Latteux, A. Terlutte
Computer Networks with Compact Routing Tables

The routing problem in computer networks is traditionally solved by providing detailed routing information for all destinations at every node. We consider the problem of routing messages with only a small amount of information at every node. For example, for every connected N-node network a scheme can be devised such that every message can be routed within O(√N) routing decisions. Improving on an observation of Santoro & Khatib [3] for trees we derive a general method of routing messages in arbitrary networks using tables of a size corresponding to the number of links at a node, while utilizing all links in the network.

J. van Leeuwen, R. B. Tan
Unconventional Leaves (An Application of Map ol-Systems to Biology)

Regularities of the positioning of cell division walls during the development of meristematic plant tissues may have morphogenetic consequences. A class of developmental constructions, double wall map generating OL-systems, was explored exhaustively and accounts for the number of concevable possibilities of wall insertions. The typology over theoretical organized cell layer configurations, which has been established in earlier works on the base of these systems, is completed here by an investigation on leaf-like structures.

Hermann B. Lück, Jacqueline Lück
A Uniform Model for the Growth of Biological Organisms: Cooperating Sequential Processes

A biological organism is a collection of cells separated by membranes. It is alive if events occur in some of the cells, which cause the cells to change state. It can develop if events occur in some of the cells, which cause the cells to divide and coalesce. Many models of this view of developing organisms have been studied — graph systems, map systems and L-systems. We shall show that each of these is a special case of a simple uniform model: cooperating sequential processes. This model can be summarised by: a process is a formal mathematical objectglobal processes are constructed from local processesproductions describe how one local process changes into another in a single stepproductions cooperate to change one global process into anotherthe development of an organism corresponds to the development of a global process from a seed.

Brian H. Mayoh
Graph Technology Applied to a Software Project

This paper describes the graph technology which is applied to a software development environment (abbreviated SDE) project. This graph technology consists of a careful design of internal representations for software documents as graphs, of a specification of the operations on these graphs induced by activations of tools of the environment, and of a mechanical proceeding how to get an implementation of these tools from the specification. This graph technology is one of the bases for the adaptability considerations of the project, i.e. the investigation how to derive something like a ’standard’ architecture for a SDE if graphs are used on the modelling side by the designer.

Manfred Nagl
Some Systems for Map Generation

New types of binary, propagating map generating systems are introduced. The first one is binary, propagating map OL systems with markers (mBPMOL systems). The second one is binary, propagating map IL systems with markers (mBPMIL systems). After defining the two systems, we consider the following decision problems (1) and (2) on these systems: (1)Whether or not an arbitrary mBPMOL system is deterministic ?(2)Whether or not an arbitrary mBPMIL system is deterministic ? These decision problems are solved. Further, decision problems of stability in these two systems are discussed. Finally, some relevant remarks related to map generating systems are given

A. Nakamura, A. Lindenmayer, K. Aizawa
A Programming Language for Lindenmayer Systems

We introduce a programming language for L-systems, based on the ideas behind Milner’s (S)CCS. We sketch a calculus of these programs, and illustrate the use of such a calculus in proving that the formal languages associated with our programs form a very well-known class of languages in L-theory.

Mogens Nielsen
A Note on Significance of Cellular Interaction in L-system

It will naturally be expected that the number of necessary states for a PDIL system GI is not greater than that for a PDOL system GO such that GI and GO generate growth processes which are equivalent in a certain sense. Intention of this short note is to indicate a fact that existence of cellular interaction compensates or reduces the number of necessary states in comparison with interactionless system. In this note, for the sake of simplicity, we treat the propagative deterministic L system, while generalization is expected.

Hidenosuke Nishio
Eol Grammars and Search Trees

We consider EOL grammars as tree generating mechanisms. This leads to questions of height, weight, and structural equivalence of EOL grammars. Height equivalence is solved completely, weight equivalence remains open, and structural equivalence is solved for three special cases. We characterize those EOL grammars which generate exactly the set of 2,3-trees.

Thomas Ottmann, Derick Wood
Variation in Inflorescence Structure in Cotoneaster Franchetti

Cotoneaster franchetti (Rosaceae) is a garden ornamental shrub which in the climate of Christchurch reaches a height of about three metres, with long curving sprays, and bears some leaves right through the winter. The flowers are small and pink, in inflorescences of about ten flowers on short spurs from the axils of the leaves on the sprays of the previous year. The reseach leading to this paper was directed towards a mathematical model describing the construction of these inflorescences. As will appear, the results are not as expected.

D. F. Robinson
Partial Path Groups and Parallel Graph Contractions

We define an algebraic structure on the paths in a graph based on a coloring of the arcs. Using this structure, basic classes of graphs (trees, hypercubes, arrays, cliques, etc.) are characterized by simple algebraic properties. The structure provides a framework for defining parallel contraction operations on a graph, in which many pairs of nodes are simultaneously collapsed into single nodes, but the degree of the graph does not increase. Such operations are useful in defining systematic strategies for simulating large networks of processors by smaller ones, or in building “pyramids” of networks.

Azriel Rosenfeld
When L was Young

Instead of a technical paper, the editors of this book want to celebrate Aristid’s birthday in a very informal way: by personal recollections from the early days of L systems. Our contribution is intended to be very non-scientific. Neither interviews nor library studies were made. The presented material results from several extended Salosauna sessions. We are completely aware of the fact that several important details are missing, e.g., the story of Gabor Herman getting involved. In spite of eventual inaccuracies, we still hope that our contribution will be of interest for both the L and the non-L crowd.

Grzegorz Rozenberg, Arto Salomaa
Equivalence Problems for Regular sets of Word Morphisms

Despite its firm basis in theoretical biology L systems theory has had some far reaching repercussions in mathematics and theoretical computer science. One of these is the emphasis on iterated composition of morphisms on a free monoid (word morphisms). This leads naturally to set equivalence problems, familiar from formal language theory, and sequence equivalence problems (variously known also as strong equivalence, graph equivalence or tree equivalence problems in deterministic L systems theory).

Keijo Ruohonen
Parentheses Grammars and Lindenmayer Grammars

The pioneering research of Lindenmayer and his co-workers on what are now called OL-systems has yield a rich mathematical theory for modeling the development of organism without cellular interaction. Concrete examples of the biological relevance of the theory of OL-systems can be found in some of the earliest literature on the subject. [L1] Yet, cellular interaction seems to be necessary for some types of development. Various extensions of the OL-systems, yield systems with provably stronger generative power. A general model for modeling cellular interaction was introduced by Lindenmayer very early in the history of L-systems. [L2] This led to a search for models with more limited types of interaction. One of the most studied of these models is the ETOL-system introduced by Rozenberg [R1, R2]

Walter J. Savitch
Array Languages and Lindenmayer Systems —A Survey

In 1968 Lindenmayer introduced a mathematical model of developmental systems [28]. This involves parallel rewriting in which each letter in a string is rewritten using production rules and there is no distinction between terminal and nonterminal symbols reflecting the simultaneous growth of each cell during different stages of development. Since then L-systems have been studied extensively, resulting in the number of research papers growing exponentially [19,29,54,56]. An interesting comment from a referee is a pointer to the extent to which the theory had developed within a span of five years. In 1973 we submitted a paper entitled Parallel O-Lindenmayer Languages which we abbreviated as POL [69]. Then pat came the referee’s comment: “P already stands for ’propagating’ and almost all letters of the alphabet have been used up. You may try PaOL”.

Rani Siromoney
Symmetric Distributed Termination

In this paper we present a simple algorithm for deciding when to terminate a distributed computation. Former solutions to the termination problem, e.g. [2, 5], are restricted to rings and undirected connected networks, resp., and they rely on the existence of a special master processor present in the network. The class of configurations for which our algorithm is applicable is the most general possible, namely the class of configurations, where the underlying (directed) networks are strongly connected. If the network is not strongly connected then there exists a group of processors which cannot send messages to the rest and it becomes impossible to detect when to terminate. Furthermore, the algorithm does not require a special master processor acting differently from the others. The only information needed is an upper bound on the diameter of the network (the number of processors, for example). The protocol for all processors is in other words identical.

Sven Skyum, Ole Eriksen
Development, Growth and Time

We propose a simple mathematical model for filamentous growth and development. The new model relates stereotype elemental (cellular) behavior to empirically observed overall growth curves. As examples we obtain the sigmoidal growth curves. Basic is the separation of subjective or physiological time of the organism from objective or absolute time and the relation between them. The underlying philosophy is related to Lindenmayer’s developmental model.

Paul M. B. Vitãnyi
On the Set of all Subgraphs of the Graphs in a Boundary NLC Graph Language

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and which establish connections between the embedded graph and neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels in the generated graphs, languages of unlabeled graphs). NLC grammars have been introduced in [JRzl,2] as a basic framework for the mathematical investigation of graph grammars. Other concepts for graph grammars can be found e.g. in [RsM,P,CL,E,N,HbK,JRz] (of course, this is not an exhaustive list). Boundary NLC grammars, BNLC grammars for short, are NLC grammars which are distinguished by the properties that (i) the left-hand side of each production is a nonterminal label and (ii) all the graphs involved (i.e., the axiom graph of the grammar and the right-hand sides of the productions) are such that nodes labeled by nonterminals are never adjacent. BNLC grammars have been investigated in [RzW1,2,3].

Emo Welzl
Graph-Controlled Systems — An Extension of OL systems

In a study of Lindenmayer developmental systems tabled OL systems(TOL systems, for short) has been investigated to examine the influence of changing environments on the growth of biological organism. For this purpose, many other extended types of OL systems have been proposed, and most of them concerns how one can control the way of applying tables to obtain a new language generating mechanism, and we observe that none of them try to give variety to tables themselves rather than the use of the tables.

Takashi Yokomori
Metadata
Title
The Book of L
Authors
Professor Dr. G. Rozenberg
Professor A. Salomaa
Copyright Year
1986
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-95486-3
Print ISBN
978-3-642-95488-7
DOI
https://doi.org/10.1007/978-3-642-95486-3