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
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de