文章基本信息

标题：Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication
本地全文：下载
作者：Shay B. Cohen ; Daniel Gildea
期刊名称：Computational Linguistics
印刷版ISSN：0891-2017
电子版ISSN：1530-9312
出版年度：2016
卷号：42
期号：3
页码：421-455
DOI：10.1162/COLI_a_00254
语种：English
出版社：MIT Press
摘要：We describe a recognition algorithm for a subset of binary linear context-free rewriting systems (LCFRS) with running time O ( n ^ωd) where M ( m ) = O ( m ^ω) is the running time for m × m matrix multiplication and d is the “contact rank” of the LCFRS—the maximal number of combination and non-combination points that appear in the grammar rules. We also show that this algorithm can be used as a subroutine to obtain a recognition algorithm for general binary LCFRS with running time O ( n ^{ωd +1}). The currently best known ω is smaller than 2.38. Our result provides another proof for the best known result for parsing mildly context-sensitive formalisms such as combinatory categorial grammars, head grammars, linear indexed grammars, and tree-adjoining grammars, which can be parsed in time O ( n ^4.76). It also shows that inversion transduction grammars can be parsed in time O ( n ^5.76). In addition, binary LCFRS subsumes many other formalisms and types of grammars, for some of which we also improve the asymptotic complexity of parsing.