Algorithmische Probleme kontextfreier Grammatiken
Hauptseminar SS 2006

Hans Leiß

Termine

Do, 10-12 Uhr, Raum 1.15, Oettingenstr.67, Beginn: 27.4.2006
Inhalt und Ziel der Veranstaltung
Im Seminar soll hauptsächlich der Zusammenhang zwischen dem Parsen mit kontextfreien Grammatiken und der Multiplikation Boole'scher Matrizen studiert werden, der theoretisch besten bekannten Lösung des Parseproblems. Daneben werden Interpretationen kontextfreier Grammatiken in Matrizenringen behandelt, die zu effizienten Berechnungen von Eigenschaften kontextfreier Sprachen, von Graphenproblemen und von Grammatiktransformationen führen. Ziel ist, diese mehr "mathematischen" Interpretationen von Grammatiken zu verstehen und herauszufinden, weshalb und ab welcher Grammatikgröße die theoretisch besten Verfahren den üblicheren überlegen sind.
Bei Interesse können auch Implementierungen der einfacheren Verfahren behandelt und auf Beispielgrammatiken angewendet werden.
Literatur:
  1. L. Lee: Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication. Proceedings 35th ACL/8th EACL, pp 9-15, 1997.
  2. L. G. Valiant: General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308-315, 1975.
  3. R. Backhouse: Regular algebra applied to language problems. Journal of Logic and Algebraic Programming, vol. 66/2, 2005.
    http://www.cs.nott.ac.uk/~rcb/MPC/RegAlgLangProblems.ps.gz
  4. M. Harrison: Introduction to Formal Languages. Addison-Wesley (1978), 442-470
  5. W. Rytter: Context-free recognition via shortest paths computation: A version of Valiant's algorithm. Theoretical Computer Science, vol. 143/2 (1995), pp. 343-352 http://citeseer.ist.psu.edu/208339.html
  6. O. de Moor, St. Drape, D. Lacey, G. Sittampalam: Incremental Program Analysis via Language Factors. (2004)
    http://web.comlab.ox.ac.uk/oucl/work/oege.de.moor/opubs.html
Voraussetzungen: Proseminar über Formale Sprachen und Automaten
Vorläufiger Plan (Genaueres in der Vorbesprechung am ersten Termin)
Teil I: Schnelle Algorithmen zur Multiplikation Boolescher Matrizen liefern schnelle Erkennungsalgorithmen für CFG's
  1. Erinnerung: Cocke-Younger-Kasami Erkenner für CFG in binärer Normalform
    Lit.: Harrison, Kap. 12.4, S.430-442
  2. Komplexität der Matrixmultiplikation über einem Ring und Reduktion auf die Matrixmultiplikation über dem Halbring ({0,1}, +,0,·,1)
    Lit.: Harrison, Kap. 12.3
  3. Warshalls Algorithmus zur Berechnung der transitiven Hülle M+ einer Relation M
    Lit.: u.a. Harrsion, Kap 12.3
  4. Valiants Algorithmus I: Berechnung von M+ für obere Dreiecksmatrix M
    Lit.: Algorithmus 12.5.1, Algorithmus 12.5.2, Theorem 12.5.2 in Harrison
  5. Valiants Algorithmus II: Berechnung von M+ in Zeit O(BM) der Boole'sche Matrixmultiplikation BM
    1. Valiants Algorithmus III: Akzeptable binäre Bäume und nicht-assoziative Multiplikation
      Lit.: Harrison, 12.5.1-12.5.5
    2. Valiants Algorithmus IV: Zentrales-Submatrix-Theorem (12.5.3) und Valiants Lemma (12.5.5)
      Harrison, 455-460
    3. Valiants Algorithmus V: Komplexitätsabschätzungen, Harrison 461-470
  6. Rytter: Ersetzung von Valiants Lemma durch Berechnung kürzester Wege in speziellen Graphen.
Teil II: Schnelle Erkennungsalgorithmen liefern schnelle Algorithmen zur BMM
  1. Lit.: L. Lee, EACL 1997
Teil III: Eigenschaften kontextfreier Sprachen und Grammatiktransformationen
  1. Reguläre Algebren: Definition durch nicht-kommutative Halbringe mit Divisionen, vollständiger Ordnung, sup-stetigen Operationen. Einfache Beispiele
    Lit.: Backhouse
  2. Konstruktion regulärer Algebren (Vektoralgebra, Matrixalgebra) und Anwendungen
  3. Fusionssatz und Interpretation kontextfreier Grammatiken in Matrizenringen
  4. Anwendungen auf Eigenschaften von CFL's, Such- und Optimierungsprobleme
    Lit.: Backhouse
  5. Das Problem der regulären Schranke: L(G) Í L(FA)?
    Lit.: de Moor u.a. (inkrementelle Analyse imperativer Programme)
Zeitplan:
Datum Thema
27.4. Vorbesprechung, Themenvergabe
4.5. Ringe, Matrizen, Reduktion von MM(Ring) auf MM(Bool)
H.Leiß
11.5. Transitive Hülle einer Relation und Matrixmultiplikation (Warshall)
A.Hauser
18.5. Korrektheit des Warshall-Algorithmus und Implementierung von Mat(n,Ring)
H.Leiß
25.5. - (Chr.Himmelfahrt)
1.6. CYK-Algorithmus und Parsetabelle als transitive Matrix
H.Leiß
8.6. Reduktion von CFG-Erkennung auf MM(Boole) nach Rytter II
E.Torres
15.6. - (Fronleichnam - gesetzlicher Feiertag in Bayern??)
22.6. Reduktion von CFG-Erkennung auf MM(Boole) nach Rytter II
H.Leiß
29.6. Reduktion von MM(Boole) auf CFG-Erkennung I
Jue Wang, Pei Zhao
6.7. Das Problem der regulären oberen Schranke einer CF-Sprache
Chr. Bartl
13.7. Das Problem der regulären oberen Schranke einer CF-Sprache (Teil 2)
Chr. Bartl
20.7. Das Problem der regulären oberen Schranke einer CF-Sprache (Teil 3)
T.Hanauer
27.7. Implementierungsfragen (ggf.früher)
Seminarskript (H.L.) und SML-Programme


File translated from TEX by TTH, version 3.70.
On 3 Aug 2006, 19:10.