Recursive Matrix Systems

Diplomarbeit von Dominik Heckmann, angefertigt am Deutschen Forschungszentrum für Künstliche Intelligenz GmbH und am Fachbereich 14, Informatik, Universität des Saarlandes, Lehrstuhl Prof. Dr. Dr. h.c. Wolfgang Wahlster

Saarbrücken 1999

• Contents
• List of Figures
• Introduction
  • Introduction
  • First Examples
  • Parsing: a short Preview
  • Overview
  • Tools
• Preliminaries
  • Word and Language
  • Phrase-Structure Grammars
• Recursive Matrix Systems
  • Recursive Matrices
    • Representations of Recursive Matrices
    • The Set of Recursive Matrices
    • Operations on Recursive Matrices
    • Sentential Forms of Recursive Matrices
  • Recursive Matrix Systems (RMS)
    • The Definition of RMS
    • Explaining the Definition
    • Restrictions and Parameters
  • Examples
• Parsing
  • Parsing of Context-Free Languages
    • Introductory Example
    • Parsing System and Parsing Schema
    • Correctness of Parsing Schemata
  • Parsing of Recursive Matrix Systems
    • CYK Parsing Schemata
    • Bottom-up Parsing Schemata
    • Earley Parsing Schemata
    • Parsing Schemata in Vector Notation
  • Parsing of Restricted Grammars
    • Parsing of Regular and Linear Grammars
    • Parsing of Restricted RMS
  • Time Complexity
• Some Formal Aspects of RMS
  • Comparison with other Formalisms
    • Regular, Linear and Context-Free Grammars
    • Tree Adjoining Grammars (TAG)
    • Multicomponent TAGs
    • Coupled Context-Free Grammars (CCFG)
    • Linear Context-free Rewriting Systems (LCFRS)
    • Context-Sensitive Grammars
    • The Parallel Structure
  • Language Family Hierarchies
  • Pumping Lemma
  • The Mix language
  • Linear Structure Grammars (LSG)
    • Motivation for a third Alphabet
    • Defining Linear Structure Grammars
    • Comparison of LSG and LCFRS
• Implementation
  • Direct Implementation
  • Chart-based Deductive Parsing in Prolog
    • Chart and Agenda
    • Inference Engine
    • Inference Rules
  • Program Architecture and User Interface
    • Program Architecture
    • CGI-Script
    • User Interface
• Conclusion and Further Work
  • Conclusion
  • Further work
• References
• About this document ...

Danksagung

Mein ganz besonderer Dank gilt Herrn Prof. Dr. Dr. h.c. Wolfgang Wahlster, der mich bereits vor 10 Jahren durch einen Vortrag am Max-Planck Gymnasium Saarlouis für die Informatik und insbesondere die Künstliche Intelligenz begeistert hat. Ich danke ihm für die Vergabe des Themas und sein Interesse an dieser Arbeit.

Herrn Prof. Dr. Dr. h.c. mult. Günter Hotz danke ich für die Übernahme der Zweitkorrektur und für verschiedene Literaturangaben.

Dr. Tilman Becker danke ich ganz herzlich für die angenehme Zusammen-arbeit bei der Entwicklung der Rekursiven Matrix Systeme. Ich danke ihm für die hervorragende Betreuung bei der Anfertigung dieser Diplomarbeit sowie für die beiden Veröffentlichungen, die wir zusammen geschrieben haben. Ausserdem danke ich ihm für die Vorlesung ``Verarbeitung natürlicher Sprache mit schwach kontext-sensitiven Formalismen'' und das Proseminar ``Effizientes Parsing und Generieren mit Baumadjunktionsgrammatiken''.

Von ganzem Herzen danke ich meinen Eltern, Geschwistern und Freunden, die mich während meines gesamten Studiums unterstützt und gefördert haben.

Mein weiterer Dank gilt Prof. PhD Stuart Shieber, Prof. PhD Aravind Joshi, Dr. Mark-Jan Nederhof, Dr. Dorothée Heckmann, Fiona McKenzie, Prof. PhD Alan Bundy, Dr. Chris Mellish, Jochen Müller, Dr. Dietmar Dengler, Wilken Schütz, Volker Röcker, Arthur McRant, Thomas Martin, Torsten Weller, Marc Fontaine, Christian Pietsch, Christof Brinker, Stephan Baldes, Dr. habil. Hans Peter Lenhof, Jan Gärtner, Suat Dilik, Katja Kurisjärvi, Claudia Marburger, Silke Hüttig und Sinéad Higgins.