Frank Drewes

• Area: LaCo
• Level: F
• Week: 1
• Time: 09:00 – 10:30
• Room: C2.06

Abstract

Graphs are becoming a widely used fundamental data structure in practical natural language processing (NLP). Classic feature structures can be seen as rooted, directed, edge- and leaf-labeled graphs, dependency parsing produces graphs rather than trees, and recent work in deep semantic annotation organizes logical meanings into directed graph structures. Efforts currently being made will yield large amounts of linguistic data annotated with such representations, to support the development of NLP algorithms and systems based on the manipulation of graphs. Fortunately, there exists a well-developed theory of graph transformation whose subject is the manipulation of graphs.

A good understanding of the theory of graph transformation will therefore become an asset for the next generation of researchers working in NLP. This course offers an introduction to this, with emphasis on aspects that are of interest for NLP. In particular, this includes context-free graph grammars. The course will start off by a general introduction to graph transformation, being a Turing-complete model of computation which is based on local replacements in graphs. After that, most of the time will be spent on context-free graph grammars, their parsing problem, and their relation to monadic second-order logic. Finally, an introduction to term graph rewriting will be given.

Slides

Lecture 1: Graph Transformation
Lecture 2: Context-Free Graph Grammars
Lecture 3: Parsing for Context-Free Graph Grammars
Lecture 4: Let’s Get Logical
Lecture 5: Further Topics, Implementations, and Literature

Additional References

Drewes, Habel, Kreowski. Hyperedge replacement graph grammars. In Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1: Foundations, chapter 2, pages 95–162. World Scientific, 1997.