Lindenmayer-Systeme

Lindenmayer-Systeme, kurz L-Systeme, sind parallele Ersetzungssysteme, die ursprünglich eingeführt worden sind um die Entwicklung von Organismen zu modellieren. Da bei Organismen die Entwicklung gleichzeitig in jeder Zelle stattfindet, ist Parallelität ein integraler Bestandteil der L-Systeme. Dies führt dazu, dass in jedem Ersetzungsschritt jedes einzelne Element (jeder Buchstabe) der aktuellen Satzform umgeschrieben wird. Dies steht im Gegensatz zu dem sequentiellen Mechanismus, mit dem Ersetzungsschritte in Phrasenstrukturgrammatiken durchgeführt werden.

Die den L-Systemen zugrundeliegenden Ideen führten zu einer Vielzahl von sprachtheoretischen Problemen, die sowohl mathematisch anspruchsvoll als auch für diverse Anwendungen interessant sind. Die resultierenden Sprachfamilien, insbesondere die Familien D0L, 0L, DT0L, E0L und ET0L, stehen inzwischen gleichbedeutend neben der Chomsky-Hierarchie, wenn es darum geht, neue Konzepte (etwa Grammatiken, Automaten, usw.) und neue Phänomene in der Theorie der Formalen Sprachen zu untersuchen und einzuordnen.

In dieser Vorlesung wird es darum gehen, die grundlegenden Klassen von L-Systemen un die von ihnen erzeugten Sprachfamilien einzuführen und ihre wesentlichen Eigenschaften herzuleiten.

Literatur

G. Rozenberg, A. Salomaa:
The Mathematical Theory of L Systems
Academic Press, 1980.
G. Rozenberg, A. Salomaa:
The Book of L
Springer, Berlin, 1986.
G. Rozenberg, A. Salomaa:
Lindenmayer Systems. Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology
Springer, Berlin, 1992.

Voraussetzungen:

Diese Vorlesung richtet sich an Studenten mittlerer und höherer Semester, die über Grundkenntnisse in der Theorie der Formalen Sprachen, mindestens im Umfang der Vorlesung "Theoretische Informatik I" verfügen.

Leistungsnachweis:

Durch regelmäßige Teilnahme an den Übungen und Bearbeitung der wöchentlichen Aufgaben sowie das Bestehen einer Abschlussprüfung (Klausur oder Kolloquium) kann ein Leistungsnachweis (Schein) erworben werden.