Baumautomaten
SoSe 11 (Ankündigung)
Organisatorisches
Dozentin: Wiebke Petersen
Sitzungen: Mi. 10:30-12:00 Uhr in Raum 22.01.HS 2B
Sprechstunde: Mo. 16:30-18:00 in Raum 23.21.04.45
Telefon: 81-15295
Lektüre
- Comon et.al. (2007): Tree Automata Techniques and Applications. Online verfügbar
zusätzliche Literaturempfehlungen
- J. E. Hopcroft; R. Motwani; J. D. Ullman (2. Aufl., 2002): Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman Verlag.
- Haruo Hosoya (2011): Foundations of XML Processing - The Tree-Automata Approach. Cambridge University Press (Vorabversion)
- R. Klabunde (1998): Formale Grundlagen der Linguistik. Narr Verlag.
- B. H. Partee et al. (1990): Mathematical Methods in Linguistics. Kluwer Acad. Publ.
- U. Schöning (5. Aufl., 2008): Theoretische Informatik - kurzgefasst. Spektrum.
- Neu: Einführungskapitel aus einer Hausarbeit von Peter Bücker
Aufgaben
- wöchentliche Aufgabe: bereiten Sie eine kurze mündliche Zusammenfassung der letzten Sitzung vor (ca. 3-5 Minuten)
- Aufgabenpaket 1
- Aufgabenpaket 2 (jetzt mit Musterlösung)
- Aufgabenpaket 3
Sitzungen
| Datum | Thema | Literatur | Aufgaben |
|---|---|---|---|
| 6.4.2011 | Vorbesprechung | ||
| 13.4.2011 | Rangalphabete und Terme | ||
| 20.4.2011 | Bäume | ||
| 27.4.2011 | nichtdeterministische endliche Baumautomaten | Aufgabenpaket 1 (siehe oben) | |
| 4.5.2011 | Beispielautomaten; Vollständigkeit (Algorithmus: vollständig machen); Erreichbarkeit; Baumautomaten mit epsilon-Übergängen (Algorithmus: eps.-Übergänge entfernen) | ||
| 11.5.2011 | Reduzieren von Baumautomaten;Umwandlung NFTA in DFTA | Wdh.: Umwandlung NFSA in DFSA (Folie aus der Einführung, stud. Gruppenarbeit 1, stud. Gruppenarbeit 2) | |
| 18.5.2011 | Pumpinglemma für reguläre Baumsprachen, Abschlußeigenschaften regulärer Baumsprachen | Tata (bis einschließlich 1.3). Wdh.: Pumpinglemma für reguläre Wortsprachen (Folie aus der Einführung, Hinweise zum Pumpinglemma für reguläre Wortsprachen); Abschlußeigenschaften regulärer Wortsprachen (Folie aus der Einführung) | |
| 25.5.2011 | Baumhomomorphismen, minimale Baumautomaten, top-down Baumautomaten | Tata (bis einschließlich 1.6) | Aufgabenpaket 2 (siehe oben) |
| 1.6.2011 | Wiederholung; Entscheidbarkeitsprobleme | Tata (bis einschließlich 1.7) | |
| 8.6.2011 | Zusammenhang regulärer Baumsprachen und kontextfreier Wortgrammatiken; reguläre Baumgrammatiken (Normalform) | Tata 2.4, 2.1 | Aufgabenpaket 2 (siehe oben |
| 15.6.2011 | reguläre Baumausdrücke; Kodierung rangloser Bäume | Tata 2.2 | Aufgabenpaket 3 (siehe oben) |
| 22.6.2011 | fällt aus (Sport Dies) [freiwillig: extra Sprechstunde für diejenigen, die eine AP machen wollen] | ||
| 29.6.2011 | XML; Problem rangloser Baumsprachen | Tata 8.1, 8.3 | |
| 6.7.2011 | XML, Hedge-Automaten | Tata 8.2, 8.7 | |
| 13.7.2011 | Wiederholung und XML Schema languages | Haruo Hosoya(2011) |