Vortragsankündigung, Bereichsseminar Theoretische Informatik,
Dienstag, den 29. 10. 2002, 11:00 - 12:30, Hauptgebäude Raum 3-68

Johannes Waldmann, Institut für Informatik, Universität Leipzig
gemeinsame Arbeit mit Alfons Geser (Hampton/VA) und Dieter Hofbauer (Kassel)

Nachfolgermengen in Wort-Ersetzungs-Systemen

Wir versuchen, Nachfolger-Mengen in Wort-Ersetzungs-Systeme formalsprachlich zu beschreiben.

Am liebsten benutzten wir dazu reguläre Sprachen wegen ihrer guten Abschluß- und Entscheidbarkeits-Eigenschaften.

Nun sind nicht alle Nachfolgermengen regulär, wir müssen also Kompromisse eingehen, von denen ich einige erläutern werde.

Weiter gehe ich auf die Anwendung dieser Methoden bei der Bestimmung von Forward Closures ein. Damit kann man Terminations-Eigenschaften untersuchen.

Zur Einstimmung zwei Beispiele:

Beweise, daß das Ersetzungssystem R = { ba -> ab } die Regularität bei Mehrschritt-Ersetzung nicht erhält, d. h. finde eine Sprache L in REG, für die R^*(L) nicht in REG.
Bestimme die Menge aller eindimensionalen Solitaire-Positionen, die man komplett (d. h. bis auf den letzten Stein) abräumen kann. D. h. für das System R = { 110 -> 001, 011 -> 100 } (die äußere 1 springt über die mittlere 1) ist R^-* (0^* 1 0^*) gesucht.

Gäste sind willkommen, Grundkenntnisse über Automaten und reguläre Sprachen sind zum Verständnis des Vortrags ausreichend.