WP6 Algorithmische und formale Aspekte II
              
Seminar im Masterstudiengang Computerlinguistik
SS 2014
Mi 14-16 Uhr, Beginn: 9.4.2014
Oe67, Raum 131
       
Verallgemeinerte Chomsky-Hierarchie, Fixpunktberechnungen,
Anwendung regulärer Algebra auf Sprachprobleme

Hans Leiß

Inhalt und Ziel der Veranstaltung
Im Seminar sollen forschungsnahe Themen aus dem Bereich der formalen Sprachen und Halbringe behandelt werden, darunter:
  1. Fragen zur Verallgemeinerung der Chomsky-Hierarchie von Sprachklassen
  2. Fragen zur Gleichungstheorie der regulären und kontextfreien Sprachen
  3. Fixpunktberechungen von Eigenschaften kontextfreier Sprachen
  4. Anwendungen der regulären Algebra auf algorithmische Probleme
  5. Die Algebra der syntaktischen Konzepte einer formalen Sprache
Man nimmt heutzutage an, daß die Klasse der natürlichen Sprachen eine Teilklasse der kontextsensitiven Sprachen ist, aber -die beliebige Iterierbarkeit gewisser Satzkonstruktionen unterstellt- keine Teilklasse der kontextfreien Sprachen ist und diese natürlich auch nicht umfaßt. In der Linguistik brauchen wir eine Theorie formaler Sprachen mit (a) Varianten der Zeichenverkettung als Grundoperation, um Lautgesetze oder Rektionsphänomene zu berücksichtigen, (b) feinere Definitionsmöglichkeiten (Grammatiken) für Sprachen, (c) schwächere Limes- und Stetigkeitseigenschaften der Operationen auf Sprachen.
Im Seminar sollen neuere Arbeiten zum algebraischen Hintergrund der Theorie formaler Sprachen gelesen und der Zusammenhang zwischen Theorie und daraus gewonnenen Algorithmen (Parsing, Grammatiklernen, Such- und Optimierungsprobleme) aufgezeigt werden.
Scheinkriterium:
Seminarvortrag mit Folien und anschließender schriftlicher Ausarbeitung (während des Semesters).
Literatur
Ho1 M.Hopkins: The Algebraic Approach I: The Algebraization of the Chomsky Hierarchy
Proceedings 10th RelMiCS/5th AKA 2008, Springer LNCS 4988, 155-172
Ho2 M.Hopkins: The Algebraic Approach II: The Algebraization of the Chomsky Hierarchy
Proceedings 10th RelMiCS/5th AKA 2008, Springer LNCS 4988, 173-190
GrHeKo N.B.Grathwohl, F.Henglein, D.Kozen: Infinitary Axiomatization
of the Equational Theory of Context-Free Languages
Proceedings FICS 2013 (fics2013.univ-mlv.fr/papers.html, proceedings)
Ba R.Backhouse: Regular Algebra Applied to Language Problems.
Journal of Logic and Algebraic Programming, vol 66,2, p.71-111, 2006
(www.cs.nott.ac.uk/~rcb/MPC/RegAlgLangProblems.ps.gz)
KM13 D.Kozen, K.Mamouras: Kleene Algebra with Equations. 2014
BeCl J.-P.Berrnardy, K.Claessen: Efficient Divide-and -Conquer Parsing
of Practical Context-Free Languages (Long Version), 2013
(www.se.chalmers.se/bernardy/PP.pdf)
Lee02 L.Lee: Context-free grammar parsing requires fast Boolean matrix multiplication.
Journal of the ACM 49, vol 1, p.1-15, 2002.
Cl13 A.Clark: The syntactic concept lattice: Another algebraic theory of the context-free languages?
Journal of Logic and Computation, vol 24(2), 2014
Die meisten Arbeiten findet man im Internet.


File translated from TEX by TTH, version 3.67.
On 4 Apr 2014, 17:59.