Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems

Carlos Gómez-Rodríguez, Marco Kuhlmann, Giorgio SattaNAACL 2010

TL;DR

This paper introduces a new, efficient parsing algorithm for a specific type of grammar called "well-nested Linear Context-Free Rewriting Systems" (LCFRS). By developing a novel "normal form" for these grammars, the authors achieve a parsing time complexity that is asymptotically better than previous methods, making it more practical for analyzing complex linguistic structures.

What Problem Does This Paper Address?

Computational linguistics has long sought formal grammars to model natural language syntax. While context-free grammars are a foundational tool, they struggle with phenomena like discontinuous constituents (e.g., "Who did you see that?") or relatively free word order. Mildly context-sensitive grammars, like Tree Adjoining Grammars (TAGs) and Linear Context-Free Rewriting Systems (LCFRS), offer more expressive power. LCFRS, in particular, can handle discontinuous phrases by allowing nonterminals to generate tuples of strings.

However, LCFRS have a high computational complexity for parsing, making them less practical. Furthermore, they lack convenient "normal forms" that simplify parsing, unlike TAGs. This paper focuses on a subset of LCFRS called "well-nested LCFRS," which are known to be more constrained and better suited for modeling certain linguistic phenomena found in real-world treebanks. The challenge is to develop an efficient parsing algorithm specifically for this well-nested subset, improving upon the general LCFRS parsing complexity.

Methods

The core of the paper's contribution lies in developing a new "normal form" for well-nested LCFRS and then leveraging this form to create an efficient parsing algorithm.

  1. Normal Form Construction: The authors transform a well-nested LCFRS into a specific normal form where all productions have a rank (number of nonterminals on the right-hand side) of at most 2. Crucially, the rank-2 productions are restricted to two types: "concatenation" and "wrapping" operations. This transformation is achieved through a systematic process of factorizing complex composition operations into simpler ones, effectively breaking down complex derivations into a series of binary steps. This process is shown to be efficient and preserves the well-nested property.
  2. Efficient Parsing Algorithm: Based on this normal form, the authors propose a chart-based parsing algorithm. This algorithm utilizes a set of "items" that represent partial derivations. The key insight is that by restricting the grammar to the normal form (rank at most 2, with only concatenation and wrapping), the number of possible "indexes" (representing string positions) in the parsing items is significantly reduced. This leads to a more efficient deduction process within the chart.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects of grammar formalisms and parsing algorithms rather than empirical evaluation on specific linguistic datasets.

Key Insights and Ideas

  • Well-nestedness as a Key Constraint: The paper highlights that the "well-nestedness" condition, which prevents certain types of crossing dependencies, is crucial. It allows for a more efficient transformation into a normal form that is not possible for general LCFRS.
  • Binary Normal Form: The ability to transform any well-nested LCFRS into an equivalent grammar where all productions have a rank of at most 2 (specifically, concatenation or wrapping) is a significant theoretical result. This simplifies the parsing problem considerably.
  • Complexity Collapse: For well-nested LCFRS, the parsing complexity, which for general LCFRS depends on both rank and fan-out, collapses to depend primarily on the fan-out. This makes them more tractable.
  • Practical Algorithm: The proposed chart-based parser is described as simple to implement, which is a practical advantage over more complex parsing schemes.

Key Results

The paper presents a parsing algorithm for well-nested LCFRS with a fan-out $\phi$ that runs in time $O(\phi \cdot |G| \cdot |w|^{2\phi+2})$, where $|G|$ is the size of the grammar and $|w|$ is the length of the input string.

  • This complexity is an asymptotic improvement over existing parsing algorithms for general LCFRS or equivalent formalisms.
  • For the specific case of $\phi=2$, the complexity reduces to $O(|G| \cdot |w|^6)$, which matches the known upper bound for Tree Adjoining Grammars (TAGs), demonstrating the efficiency of their approach for this important subclass.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on algorithmic complexity and formal transformations. Empirical evaluation on real-world linguistic data is not presented.
  • Fan-out Dependency: While the complexity is improved, it still depends exponentially on the fan-out ($\phi$). For grammars with very high fan-out, the algorithm might still be computationally expensive.
  • Future Work: The authors suggest that their parser can be applied to general LCFRS, not just well-nested ones, though the complexity benefits might be less pronounced. Further exploration of the practical performance of their algorithm and its application to linguistic data would be valuable.

Summary updated

BibTeX
@inproceedings{gomezrodriguez2010efficient,
  author = {Carlos Gómez-Rodríguez and Marco Kuhlmann and Giorgio Satta},
  title = {{Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure