Institut für Theoretische Informatik
Forschung 1999/2000
Multiple-Limited Lindenmayer Systems
M. Seemann
Lindenmayer systems were introduced by A.Lindenmayer for describing parallel
cell growth. In multiple-limited Lindenmayer systems all identical cells
of an organism are fed by a common limited resource like light or water
that bounds the fully parallel growing of those cells. For every cell each
system S has some rules of growing in store. Step by step S
generates words, each representing an organism, by applying repeatedly
its rules to the Axiom, the beginning organism. The set of all these
words is called the language generated by S. The left tree
of the figure below looks very regular and was generated by an original
(unlimited) Lindenmayer system. The middle one was generated by a multiple-limited
Lindenmayer system where all resources have the same size. The last tree
was generated by a multiple-limited Lindenmayer system where the limit
for left branching cells was ten times smaller than those limits for the
remaining types of cells.
If we restrict the sizes of the resources to be taken from a set K
of
permitted limits then every such set K induces an own family of
languages. It was proved that all these families and several subfamilies
like the propagating and/or the deterministic families, all are so-called
Anti-AFLs,
i.e. they are not closed according to none of the following operations:
union, intersection with regular languages, epsilon-free iteration, epsilon-free
homomorphism, inverse homomorphism, concatenation.
Furthermore, a weak iteration theorem was proved. It gives a necessary
condition for certain infinite languages to be generated by a multiple-limited
Lindenmayer system as described above. More precisely, the theorem says
that almost all organisms described by those certain infinite languages
only can grow linearly if they are generated by such a multiple-limited
Lindenmayer system.
Function-limited 0L Systems
Dietmar Wätjen, David Ostrovsky
Function-limited and uniformly function-limited 0L systems have been
introduced by Fernau and Stier, respectively, as a
generalization of k-limited 0L systems. These systems are now
revisited concentrating on language families
generated by such systems with fixed limitation functions.
The different families of function-limited, uniformly function-limited and
normal T0L languages are compared with one another. In nearly all
cases, we have got incomparability results
in the sense that the families are not included
in one another.
Furthermore, we have compared these families
with some families of the Chomsky
hierarchy. We proved that for every (uniform) limitation function, the
corresponding family of T0L languages is an anti-AFL, that is,
it is not closed with respect to union, catenation, epsilon-free
homomorphism,
(epsilon-free) iteration, and inverse homomorphism.
Fernau and
Stier could not demonstrate the non-closure under
epsilon-free iteration for all language
families considered in their papers. The
cases left open now could be proved, too. Furthermore,
(uniformly) function-limited ET0L systems have been
investigated. Introducing a terminal
alphabet always
increases the generative power of the systems. For all
function-limited E0L systems with bounded limitation functions, we could
prove an iteration theorem which allows to prove the strict
inclusion of the corresponding families of function-limited E0L
languages in the
corresponding families of function-limited ET0L
languages. Again for bounded limitation functions, we proved the strict
inclusion of the family of normal ET0L languages in that of function-limited
ET0L languages. For other limitation functions or for uniform
limitation functions, we have not succeeded
in deriving analogous results.
Restriction of Substitutions in Limited 0L Systems
Dietmar Wätjen
For limited or non-limited
Lindenmayer systems, the generative power of the systems is enlarged
if we introduce terminal alphabets. A terminal alphabet is a
subalphabet of the overall
alphabet of the system considered. From all words occurrring in
a derivation, only words over
terminal symbols constitute the generated language of such an extended
Lindenmayer system. In this work, for every table h of the system
we have introduced a
second subalphabet such that the substitution h is restricted to
this subalphabet. For 0L systems and non-uniformly limited 0L systems, this
definition has not lead to new languages, but for uniformly limited
0L systems, the generative power is enlarged. Furthermore, even in the
case of 0L and limited 0L systems, the substitution restricted systems
allow the so called t-modus of derivation in case of cooperating
distributed systems.
Icons (c) by frust.
05.13.2000, F.Rust (frust@iti.cs.tu-bs.de)
Übersicht
Voriges Jahr
Homepage