MCFG path querying by matrix multiplication

[gsvgit]

• There is an parsing algorithm for linear CF rewriting systems (LCFRS) which is based on matrix multiplication: Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication. LCFRS in normal form is equivalent to MCFG in "normal form": Multiple Context-Free Grammars and Linear Context-Free Rewriting Systems. You should implement MCFG parsing algorithm based om matrix multiplication.
• CFG path querying may be expressed in terms of matrix multiplication: Context-Free Path Querying by Matrix Multiplication Try to generalize algorithm from step 1 for MCFG path querying.
• Linear Conjunctive Languages (LCL) are more expressive than CFLs and they are applicable for static code analysis: Context-sensitive data-dependence analysis via linear conjunctive language reachability It is important that MCFL is closed under intersection with regular language and emptiness of MCFL is decidable, but emptiness of LCL is undecidable. So, it is interesting to find problems which require more than CF language and try reformulate them in terms of MCFL reachability.

Some problems may be described in terms of multiple Dyck language (shuffle of some Dyck languages). A Chomsky-Schützenberger Representation for Weighted Multiple Context-free Languages, Tobias Denkinger may be a start for creation MCFG for multiple Dyck language. Another article: A Note on Multidimensional Dyck Languages