Algorithmische Probleme kontextfreier Grammatiken
Masterseminar ,,Algorithmen zu kontextfreien Grammatiken I b''
WiSe 2015/16

Prof. Martin Hofmann, Informatik
Dr. Hans Leiß, CIS (WPCom 6)

Termin

Mi, 12-14 Uhr, Raum 165, Oettingenstr.67, Beginn: 14.10.2015
Inhalt und Ziel der Veranstaltung Kontextfreie Grammatiken spielen eine wichtige Rolle in der Compilierung, der Dokumentenverarbeitung, der maschinellen Übersetzung und vielen anderen Bereichen. Im Seminar sollen grundlegende und neuere Algorithmen zu Parsing und Lernen kontextfreier Grammatiken (und neuerer Varianten davon) behandelt werden, sowie einige andere algorithmische Fragestellungen.
Das Seminar ist für Masterstudierende in Computerlinguistik oder Informatik gedacht. Bachelorstudierende, die bereits das Modul ,,Formale Sprachen und Komplexität'' erfolgreich abgelegt haben, können auch teilnehmen und das Seminar als Bachelorseminar mit entsprechend geringerem Arbeitspensum verwenden.
Plan: Im ersten Drittel soll die algorithmische Äquivalenz zwischen Parsen mit kontextfreien Grammatiken und der Berechnung der transitiven Hülle einer Relation durch Matrixmultiplikation behandelt werden, was nach neueren Arbeiten nicht nur theoretisch die beste bekannte Lösung des Parseproblems ist. Es soll aber von den klassischen Parsern bzw. Erkennern ausgegangen werden.
Im zweiten Drittel geht es um kontextfreie Grammatiken als Fixpunkte von monotonen Funktionen in Unterhalbringen von P(S*), die Interpretation kontextfreier Grammatiken in anderen Halbringen und die Lösung von algorithmischen Problemen als Fixpunktberechnungen (Eigenschaften von CF-Sprachen, Graphen- und Optimierungsprobleme, Grammatiktransformationen).
Im letzten Drittel soll es um das Lernbarkeit von Grammatiken (Limesidentifizierbarkeit) gehen; einerseits um die Unmöglichkeit, Grammatiken allein aus positiven Beispielen der Sprache zu erlernen, und andererseits darum, daß man mit zusätzlicher Information doch Grammatiken für gewisse kontextfreie (auch kontextsensitive) Sprachen lernen kann.
Vorläufiger Plan (etwas zu den einzelnen Themen auf den Folien)
Folien zu den Themen
Auf Grund der Teilnehmerzahl lassen wir die Axiomatisierungsfragen und beginnen im November.
Aktualisierter Zeitplan
Woche Termin Wer Thema
0 14.10. L/H Themenvergabe
1 11.11. Leiß Einführung CFG Folien zu CFGs
2 18.11. Iljazi CYK-Erkenner/2-Normalform Folien
3 25.11. MestaniEarley-Erkenner / Gepackte Parsewälder Folien
4 2.12. Uvarov CFG-Erkennen mittels BMM Folien
5 9.12. Schmid Erkenner für datenabh.Grammatiken (Folien) (Beispiel)
6 16.12. Kleber Unlernbarkeitssätze von Gold und Kracht
7 13.01. Leiss Effiziente Fixpunktberechnung in einer Relationenalgebra (Folien)
8 20.01. Groth Lernen von Kategorialgrammatiken (Folien)
7 27.01. Meyer Lernen von CFLs mit synt.Konzepten
Bei einigen der Themen ist die Literatur auf den Folien zur Einführung angeben und teilweise hier gesammelt:
Archiv mit einigen der behandelten Arbeiten
Bei den Themen, wo die Literatur nicht genannt ist, bitte Rücksprache bzw. Kopie bei H.Leiß holen.


File translated from TEX by TTH, version 3.67.
On 16 Dec 2015, 11:11.