English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We describe a matrix multiplication recognition algorithm for a subset ofbinary linear context-free rewriting systems (LCFRS) with running time$O(n^{\omega d})$ where $M(m) = O(m^{\omega})$ is the running time for $m\times m$ matrix multiplication and $d$ is the "contact rank" of the LCFRS --the maximal number of combination and non-combination points that appear in thegrammar rules. We also show that this algorithm can be used as a subroutine toget a recognition algorithm for general binary LCFRS with running time$O(n^{\omega d + 1})$. The currently best known $\omega$ is smaller than$2.38$. Our result provides another proof for the best known result for parsingmildly context sensitive formalisms such as combinatory categorial grammars,head grammars, linear indexed grammars, and tree adjoining grammars, which canbe parsed in time $O(n^{4.76})$. It also shows that inversion transductiongrammars can be parsed in time $O(n^{5.76})$. In addition, binary LCFRSsubsumes many other formalisms and types of grammars, for some of which we alsoimprove the asymptotic complexity of parsing.

Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication