Projects per year

## Abstract

We describe a matrix multiplication recognition algorithm for a subset of binary linear contextfree
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 get 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.

Original language | English |
---|---|

Pages (from-to) | 421-455 |

Number of pages | 26 |

Journal | Computational Linguistics |

Volume | 42 |

Issue number | 3 |

Early online date | 17 Jun 2016 |

DOIs | |

Publication status | Published - 21 Sep 2016 |

## Fingerprint

Dive into the research topics of 'Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication'. Together they form a unique fingerprint.## Projects

- 1 Finished