Abstract
Recently researchers working in the LFG framework have proposed algorithms for taking advantage of the implicit context-free components of a unification grammar [Maxwell and Kaplan, 1996]. This paper clarifies the mathematical foundations of these techniques, provides a uniform framework in which they can be formally studied and eliminates the need for special purpose runtime datastructures recording ambiguity. The paper posits the identity: Ambiguous Feature Structures = Grammars, which states that (finitely) ambiguous representations are best seen as unification grammars of a certain type, here called "interactionfree" grammars, which generate in a backtrackfree way each of the feature structures subsumed by the ambiguous representation. This work extends a line of research [Billot and Lang, 1989; Lang, 1994] which stresses the connection between charts and grammars: a chart can be seen as a specialization of the reference grammar for a given input string. We show how this specialization grammar can be transformed into an interaction-free form which has the same practicality as a listing of the individual solutions, but is produced in less time and space.
Introduction
In natural language processing, a single sentence often yields dozens or even thousands of possible structural interpretations. While standard Context-Free Grammars (CFGs) handle this ambiguity efficiently using a "chart"—a data structure that stores possibilities in a compact, shared format—modern linguistic theories often rely on more powerful "unification grammars" (such as Lexical Functional Grammar or Definite Clause Grammars).
These unification grammars use feature structures to handle complex linguistic phenomena like subject-verb agreement. However, these features introduce a significant computational challenge: checking if a specific parse is valid becomes an NP-complete problem. This often leads to an "exponential explosion," where the system spends an impractical amount of time resolving conflicting features across different parts of a sentence. This paper addresses the need for a mathematical framework that maintains the efficiency of context-free charts while supporting the expressive power of unification.
The Core Proposal: Interaction-Free Grammars
The central innovation of this work is the concept of Interaction-Free (IF) Grammars. The author, Marc Dymetman, proposes a conceptual shift: instead of viewing the output of a parser as a static list of results or a complex data structure, we should treat it as a specialized grammar generated specifically for that input sentence.
An IF grammar is a unification grammar where the rules are structured so that expanding one part of a derivation can never conflict with another part. In practical terms, this means that if a system begins building a sentence from the top down using an IF grammar, it is guaranteed to reach a valid solution without ever hitting a "dead end." This eliminates the need for backtracking, which is the primary source of inefficiency in standard unification parsers.
The Identity Principle
The paper’s most striking theoretical claim is the identity: Ambiguous Feature Structures = Grammars. This suggests that finitely ambiguous representations are best understood as unification grammars of the IF type. By adopting this view, researchers can move away from specialized, ad-hoc data structures for ambiguity and instead use the formal tools of grammar theory to manage multiple interpretations.
Methodology and Transformation
The paper outlines a formal process for transforming a standard, potentially conflicting chart into an interaction-free form through several steps:
- Grammar Specialization: The chart is viewed as a specialization of the general reference grammar for a specific input string.
- Standardization of Rules: Feature constraints are formalized so that interactions between different sentence components are explicitly visible.
- Partial Evaluation: The transformation algorithm uses "partial evaluation" to pre-calculate the complex feature logic. By resolving these interactions upfront, the algorithm ensures that all remaining choices within the grammar are "safe."
- Factorization: The IF grammar naturally factors out commonalities. If multiple parses share a sub-structure, that structure is represented only once, maintaining the compactness of the original chart.
Theoretical Results and Efficiency
Dymetman demonstrates that any "offline-parsable" unification grammar—one that does not loop infinitely—can be converted into an IF form. While the transformation process itself is subject to the inherent NP-completeness of unification, the paper argues that for real-world natural language, this approach is highly efficient.
The resulting IF grammar allows for backtrack-free enumeration. A computer can "read out" every possible valid parse in linear time relative to the size of the parse tree. This provides a significant space and time advantage over simply listing individual solutions, as it exploits the "mostly context-free" nature of human language to keep the representation compact.
Conclusion and Limitations
This work provides a solid mathematical foundation for previous techniques, such as "disjunctive lazy copy links," by showing they are specific instances of a broader grammatical transformation. However, the author acknowledges certain limitations:
- Worst-Case Complexity: Because unification is NP-complete, there are theoretical edge cases where the IF grammar could still grow exponentially, though these appear rare in linguistic data.
- Acyclic Constraints: The current algorithm is designed for acyclic charts; infinite recursion that is not tied to input length remains a challenge.
- Empirical Scaling: While theoretically robust, the paper focuses on hand-crafted examples (e.g., "john read here"). Further research is required to evaluate performance against large-scale benchmarks like the Penn Treebank or within production-grade LFG parsers.
Summary updated