题目：Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis

报告人：孙薇薇（剑桥大学）

时间：10 月 22 日（周四） 14：00

地点：哲学系106

摘要：Language production, though as important as language understanding, has received very limited theoretical and empirical research attention. A fundamental problem in modeling language production is parsing meaning representations, i.e. computing all possible analyses of a given meaning representation (MR) according to a (competence) grammar. In theory, the worst-case complexities of existing algorithms are exponential or high-degree polynomial w.r.t. grammar size and input length. In practice, there are few systems that can parse large but frequent MRs with a realistic, wide-coverage grammar in a reasonable time.
In this talk, I will introduce an exact yet efficient method to parse MRs in the framework of graph-based semantic representations and context-free graph rewriting. The advance in efficiency is from exploiting locality of phrase-structure rules from the rarely discussed perspective of language production, a reversed direction to language understanding. I will discuss locality in a sense of terminal edge-adjacency and develop a locality-centric complexity analysis of the de facto algorithm introduced by Chiang et al. (2013). The analysis motivates a computational support in the constructivist hypothesis in theoretical linguistics.