Abstract
Linear Context-Free Rewriting Systems (LCFRS) are powerful grammatical formalisms capable of modeling non-local dependencies in natural languages. However, their high parsing complexity, typically $O(n^{3f})$ where $f$ is the fan-out, limits their practical application. This paper presents a novel algorithm that generalizes Valiant’s approach for context-free grammars to LCFRS. By reducing the parsing problem to Boolean matrix multiplication, the authors achieve significant asymptotic speedups, reducing the complexity for formalisms like Tree-Adjoining Grammars (TAG) from $O(n^6)$ to $O(n^{4.76})$.
Introduction
In computational linguistics, the ability to recognize and parse complex sentence structures is crucial. While Context-Free Grammars (CFGs) are efficient, they struggle with "mildly context-sensitive" phenomena like cross-serial dependencies or discontinuous structures. LCFRS provides a solution by allowing nonterminals to cover multiple discontinuous spans, but this flexibility comes at a high computational cost.
The primary challenge is that standard chart parsing for LCFRS scales exponentially with the fan-out $f$. This work aims to bridge the gap between theoretical expressivity and algorithmic efficiency by leveraging fast matrix multiplication techniques.
Methodology
The proposed algorithm generalizes Valiant’s 1975 method, which reduced CFG recognition to Boolean matrix multiplication (BMM). The authors introduce several key innovations to handle the multi-span nature of LCFRS:
- Contact Rank ($d$): A new parameter measuring the maximal number of points where spans meet or combine. This often provides a tighter bound on complexity than fan-out.
- Over-complete Matrix Indexing: Matrices are indexed to track multiple endpoints of discontinuous spans simultaneously, allowing rows and columns to represent various span combinations.
- Copy Operations: To manage the over-complete indexing, special operations (using symbols like $\boxplus, \boxminus$) ensure logical states are propagated correctly across equivalent matrix cells.
- Reduction to BMM: The authors prove that their specialized, non-associative matrix multiplication operator can be decomposed into standard BMM steps, inheriting the complexity of $O(n^\omega)$ where $\omega \approx 2.37$.
Key Insights: TAG and Beyond
A significant contribution is the unified treatment of various "mildly context-sensitive" grammars. Formalisms such as Tree-Adjoining Grammars (TAG), Combinatory Categorial Grammars (CCG), and Head Grammars can all be viewed as specific instances of LCFRS.
The distinction between "balanced" and "unbalanced" grammars is also critical. Unbalanced grammars can be parsed in $O(n^{\omega d})$, while balanced ones (like Inversion Transduction Grammars) require an additional factor of $n$, resulting in $O(n^{\omega d+1})$.
Results
The algorithm yields improved upper bounds for several major formalisms:
- TAG, CCG, and Head Grammars: Complexity is reduced from $O(n^6)$ to $O(n^{4.76})$.
- Inversion Transduction Grammars (ITG): Reduced from $O(n^6)$ to $O(n^{5.76})$.
- General LCFRS: Complexity shifts from $O(n^{3f})$ to approximately $O(n^{2.38d})$. Since $d$ is typically smaller than $f$, this represents a massive theoretical speedup.
Conclusion and Future Work
While the asymptotic improvements are substantial, practical implementation remains a challenge due to the high constant factors associated with fast matrix multiplication algorithms like Strassen’s. Future research directions include extending this framework to Probabilistic LCFRS for finding the most likely parse and optimizing the binarization process to minimize the contact rank $d$.
Summary updated