摘要：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.
