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

zusätzliche Literaturempfehlungen

Aufgaben

Buecker_Einfuehrung.pdf

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.1Aufgabenpaket 2 (siehe oben
15.6.2011 reguläre Baumausdrücke; Kodierung rangloser Bäume Tata 2.2Aufgabenpaket 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)

Sonstiges