Graph Grammars for Natural Language Processing

Daniel Bauer

Graph Grammars for Natural Language Processing Grammar formalisms that describe languages of strings or trees (CFG, Regular Tree Grammar, Tree Adjoining Grammar, etc.) are well established in Natural Language Processing. Formalisms that operate on graphs are discussed less frequently, even though graphs offer an intuitive representation for natural language syntax and semantics. This course offers an introduction to graph grammars and their use in NLP. We start by examining graph-based representations in NLP, such as Abstract Meaning Representation (AMR). We then discuss context-free graph grammars, focusing on Hyperedge Replacement Grammars (HRG), and synchronous HRG. The course discusses theoretical properties of graph grammars, including their relationship to other formalisms in NLP. It also covers practical applications of graph grammars to natural language semantics. The course puts emphasis on synchronous grammars for string-to-graph translation, which we use for language understanding. It present algorithms for learning grammars from annotated corpora (graphbanks), and for statistical semantic parsing.