Wenxi Li, Yiyang Hou, Yajie Ye, Li Liang, Weiwei Sun. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

A key problem in processing graph-based meaning representations is graph parsing, i.e. computing all possible derivations of a given graph according to a (competence) grammar.We demonstrate, for the first time, that exact graph parsing can be efficient for large graphs and with large Hyperedge Replacement Grammars (HRGs).The advance is achieved by exploiting locality as terminal edge-adjacency in HRG rules.In particular, we highlight the importance of 1) a terminal edge-first parsing strategy, 2) a categorization of a subclass of HRG, i.e. what we call Weakly Regular Graph Grammar, and 3) distributing argumentstructures to both lexical and phrasal rules.

A DAG automaton is a formal device for manipulating graphs.By augmenting a DAG automaton with transduction rules, a DAG transducer has potential applications in fundamental NLP tasks.In this paper, we propose a novel DAG transducer to perform graph-to-program transformation.The target structure of our transducer is a program licensed by a declarative programming language rather than linguistic structures.By executing such a program, we can easily get a surface string.Our transducer is designed especially for natural language generation (NLG) from type-logical semantic graphs.Taking Elementary Dependency Structures, a format of English Resource Semantics, as input, our NLG system achieves a BLEU-4 score of 68.07.This remarkable result demonstrates the feasibility of applying a DAG transducer to resolve NLG, as well as the effectiveness of our design.