Saarland University
Computer Science
Programming Systems
Teaching
Formal Grammars
Main page
Literature
This page lists some of the papers that we will discuss in this seminar.
The Handbook of Formal Languages contains introductory articles to many grammar formalisms discussed in this seminar. It is available in the Computer Science library.
Grzegorz Rozenberg, Arto Salomaa,
Handbook of Formal Languages, 3 volumes,
Springer-Verlag, 1997.
Chapter 2 in Khoussainov's and Nerode's book contains a discussion of finite automata, and shows how the languages that they recognize (regular string languages) can equivalently be characterized in terms of Monadic Second Order Logic.
Bakhadyr Khoussainov and Anil Nerode,
Automata Theory and its Applications,
Volume 21 of Progress in Computer Science and Applied Logic,
Birkhäuser, 2001.
In Computer Science, the discussion of parsing algorithms for context-free languages is often restricted to the linear-time parseable fragments of CFG. In this seminar, we will also discuss the (cubic) parsing algorithms for general CFG. The tutorial notes by Nederhof and Satta develop the framework of tabular context-free parsing. They show how tabulation can be added to push-down automata in a completely orthogonal way. The paper by Lee gives a lower bound for context-free parsing, by encoding it as a form of matrix multiplication.
Mark-Jan Nederhof and Giorgio Satta,
Introduction to Parsing Algorithms for NLP,
Lecture Notes, ESSLLI 2004.
[PDF]
Lillian Lee,
Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication,
Journal of the ACM 49:1, 1-15, 2002.
Multiple Context-Free Grammars, Context-Free Hypergraph Grammars and Linear Context-Free Rewriting Systems all provide infinite hierarchies of grammar formalisms that are more expressive than CFG, but still can be parsed in polynomial time.
Hiroyuki Seki and Takashi Matsumura and Mamoru Fujii and Tadao Kasami,
On Multiple Context-Free Grammars,
Theoretical Computer Science 88, 191-229, 1991.
K. Vijay-Shanker and David J. Weir,
The Equivalence of Four Extensions of Context-Free Grammars,
Mathematical Systems Theory 27, 511-545, 1994.
David J. Weir,
Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers,
30th Annual Meeting of the Association for Computational Linguistics (ACL), pages 136-143,
Newark, Delaware, USA, 1992.
Tree Adjoining Grammars can be seen as an instance of Linear Context-Free Rewiting Systems, where the objects being manipulated are trees rather than strings. TAGs have important applications in computational linguistics.
Aravind K. Joshi and Leon S. Levy and Masako Takahashi,
Tree Adjunct Grammars,
Journal of Computer and System Sciences 10, 136-163, 1975.
Aravind K. Joshi,
Tree Adjoining Grammars: How Much Context-Sensitivity is Required to Provide Reasonable Structural Descriptions?,
pages 206-250 in Natural Language Parsing,
Cambridge University Press, 1985.
K. Vijay-Shanker and Aravind K. Joshi,
Some Computational Propertes of Tree Adjoining Grammars,
23rd Annual Meeting of the ACM, pages 82-93,
Chicago, Illinois, USA, 1985.
Aravind K. Joshi and Yves Schabes,
Tree-Adjoining Grammars,
pages 69-123 in Handbook of Formal Languages, volume 3,
Springer-Verlag, 1997.
Parsing algorithms can be specified as inference systems. This provides a very high-level view on the algorithms, which abstracts away from the concrete implementation. Nevertheless, one can analyze many properties of the algorithms on that level, such as correctness and complexity.
David McAllester,
On the Complexity Analysis of Static Analyses,
Journal of the ACM 49:4, 512-537, 2002.
Stuart M. Shieber and Yves Schabes and Fernando C. N. Pereira,
Principles and Implementation of Deductive Parsing,
Journal of Logic Programming 24:1+2, 3-36, 1995.
Parsing schemata develop the view on parsing as deduction. Parsing algorithms specified as parsing schemata can be modified to obtain desirable properties in a systematic way, and correctness proofs become simpler.
Klaas Sikkel,
Parsing Schemata: A Framework for Specification and Analysis of Parsing Algorithms,
Springer-Verlag, 1997.
Klaas Sikkel,
Parsing Schemata and Correctness of Parsing Algorithms,
Theoretical Computer Science 199, 87-103, 1998.
One can also characterize languages by their computational properties. The following paper develops the class of P-time languages.
William C. Rounds,
LFP: A Logic for Linguistic Descriptions and an Analysis of its Complexity,
Computational Linguistics 14:4, 1-9, 1988.