  We describe a matrix multiplication recognition algorithm for a subset of
binary 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 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^{\omega d + 1})$. The currently best known $\omega$ 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.
