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 ...