Saarland University
Computer Science
Programming Systems
Teaching
Formal Grammars


Main page
Literature

Formal Grammars

Seminar, 9 credit points
(may also be credited as Proseminar)

Winter term 2006/2007

Prof. Gert Smolka, Ralph Debusmann, Marco Kuhlmann, Mathias Möhl, Guido Tack
Programming Systems Lab, Department of Computer Science, Saarland University

Abstract

Formal grammars are finite devices used to specify infinite sets of mathematical structures, such as strings, trees, or hypergraphs (one of the most familiar grammar formalisms is context-free grammar). Formal grammars are widely applied both in computer science and computational linguistics.

This seminar has three goals:

• first, to give an overview over a broad range of grammar formalisms, both from theoretical computer science and computational linguistics;

• second, to sensitize the participants to the dichotomy between the formal expressivity and computational complexity of a grammar formalism; and

• finally, to familiarize the participants with the standard terminology and the most important theoretical tools and concepts related to formal grammars.

The exact syllabus of the seminar will depend on the specific interests of the participants. Possible topics include:

• context-free grammars and push-down automata;
• regular tree grammars and tree automata;
• context-free hypergraph grammars;
• languages definable in monadic second-order logic;
• grammar formalisms used in computational linguistics;
• parsing schemata and chart parsing.

Some of the literature that we will discuss

Organization

The seminar will be split into two parts:

• a reading group, to be held on four occasions during lecture time; and

• a series of talks on chapters of books, original research papers or journal articles, to be held after the term (March 22–23).

Here are the topics for the talks.

The seminar schedule, including the slides, is now available.

Assessment

To obtain the credit points assigned to this course, you have to meet the following requirements:

• presence in the reading group and at all talks
• talk (25 minutes, plus discussion)
• extended abstract (10–15 pages, electronically submitted)

Registration

To register for the seminar, please come to the kick-off meeting (see above). If for any reason you cannot make it to that meeting, but are interested in attending the seminar, please send a mail to Marco Kuhlmann to explain your situation.