Vorlesung im Sommersemester 2001, freitags 11:15-12:45, HS 21, Dr. J. Waldmann

L-Systeme


Teilnehmerkreis:

Vorlesung für Studenten der Informatik oder Mathematik im Hauptstudium, mit Schwerpunkt Theoretische Informatik.

Übersicht:

L-Systeme sind Modelle für parallele Ersetzungsprozesse. Der Begriff wurde 1968 von Aristid Lindenmayer vorgeschlagen, um natürliches Wachstum von mehrzelligen Organismen (Pflanzen) zu beschreiben. In der Vorlesung betrachten wir mathematische Grundlagen und Eigenschaften sowie Anwendungen und Erweiterungen von L-Systemen.

L-Systeme beschreiben wir durch iterierte Morphismen auf Wörtern. Im Limes bestimmen diese ein unendliches Wort. Bereits ca. 1910 untersuchte Axel Thue Eigenschaften solcher Wörter. Diese Kombinatorik auf (unendlichen) Wörtern lernen wir als Beginn der Theorie der formalen Sprachen kennen. Wir betrachten dann aktuelle gelöste und ungelöste Fragen zu Morphismen, insbesondere zu vermeidbaren Mustern sowie verschiedene Äquivalenz-Probleme.

Diese streng mathematischen Untersuchungen lockern wir auf durch viele computergenerierte Beispiele. Insbesondere betrachten wir mehrere Varianten, den einfachen Begriff des iterierten Morphismus zu erweitern, damit sich biologische Phänomene besser beschreiben lassen.

Literatur

G. Rozenberg, A. Salomaa: The Mathematical Theory of L Systems
Academic Press, New York, 1980
T. Harju, J. Karhumäki: Morphisms
in: Rozenberg/Salomaa: Handbook of Formal Languages, Springer, 1997
L. Kari, G. Rozenberg, A. Salomaa: L Systems
in: Rozenberg/Salomaa: Handbook of Formal Languages, Springer, 1997
M. Lothaire: Combinatorics on Words
Cambridge University Press, 1997
M. Lothaire: Algebraic Combinatorics on Words
http://www-igm.univ-mlv.fr/~berstel/Lothaire/
P. Prusinkiewicz, A. Lindenmayer: The Algorithmic Beauty of Plants
Springer, 1990

best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de