Skript zur Vorlesung Baumautomaten SS99

• Inhaltsverzeichnis
• Einleitung Formale Sprachen. Maschinen, auch endliche. Bäume. Endlich gleich einfach?. Erweiterte Sternhöhe. Baumgleichungen.
• Voraussetzungen Mengen, Relationen, Funktionen. Wörter. Bäume. Algebren. Ordnungen.
• Baum-Automaten Baum-Automaten. Varianten von Automaten. Eigenschaften von Automaten. Operationen mit Automaten.
• Reguläre Baum-Sprachen Kongruenzen. Morphismen zwischen Automaten. Minimale Automaten.
• Set Constraints Motivation. Definition. Beispiele für Set Constraints. Lösen von Constraint-Systemen. Klassen von Set Constraints.
• Baumsprachen und Logik Motivation. Inhalt.
• Reguläre Ausdrücke Motivation. Reguläre Baum-Ausdrücke. Sternfreie Baumsprachen. Unäre reguläre Ausdrücke. Definite Sprachen.
• Reguläre Relationen Motivation. Einfache Reguläre Relationen. Ground Tree Transducer.