Guaranteeing Parsing Termination of Unification Grammars

Efrat Jaeger, Nissim Francez, Shuly WintnerCOLING 2002

TL;DR

This paper investigates "off-line parsability" (OLP) constraints for unification grammars, which are crucial for ensuring that parsing algorithms terminate. The authors analyze various OLP definitions, reveal their inter-relationships, and crucially, prove that three prominent OLP conditions (Finite Ambiguity, Depth-Boundedness, and Shieber's OLP) are undecidable. This work highlights the inherent complexity in guaranteeing parsing termination for these powerful grammar formalisms.

What Problem Does This Paper Address?

Unification grammars are powerful formalisms for natural language processing, capable of expressing complex linguistic phenomena. However, their expressive power makes them Turing-equivalent, meaning the problem of determining if a given word belongs to the language generated by a grammar (the recognition problem) is generally undecidable. To overcome this, researchers have proposed "off-line parsability" (OLP) constraints. Grammars satisfying OLP are guaranteed to have decidable recognition problems.

The core challenge this paper addresses is the lack of a clear understanding and comparative analysis of the various OLP constraints proposed in the literature. Specifically, it tackles the open question of whether it's decidable if a given unification grammar actually satisfies a particular OLP constraint. This is a critical issue because if checking for OLP is itself undecidable, then the benefit of OLP in ensuring decidable recognition is diminished. The paper aims to clarify the landscape of OLP definitions, their relationships, and to prove the undecidability of checking for some of these constraints.

Methods

The paper's methodology involves a two-pronged approach:

  1. Comparative Analysis of OLP Definitions: The authors meticulously define and analyze several existing OLP constraints from the literature. They then establish the inter-relations between these definitions, showing which constraints imply others. This is achieved through logical deduction and by constructing counter-example grammars that satisfy one constraint but not another.
  2. Undecidability Proofs: For key OLP definitions, the paper provides sketches of proofs demonstrating their undecidability. These proofs typically employ reductions from known undecidable problems, most notably the Turing machine halting problem and the membership problem (w ∈ L(G)). The strategy is to show that if an algorithm existed to decide a given OLP constraint, it could be used to solve one of these known undecidable problems, thus proving the OLP constraint's undecidability.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and proofs of undecidability for grammar properties, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Landscape of OLP is Complex: There isn't a single, universally agreed-upon OLP definition. The paper categorizes them and shows how they relate, revealing that some are more restrictive than others.
  • Undecidability is Pervasive: The most significant finding is the proof that checking for several seemingly useful OLP constraints (Finite Ambiguity, Depth-Boundedness, and Shieber's OLP) is itself undecidable. This means that even if a grammar is OLP according to these definitions, we cannot algorithmically determine this fact in the general case.
  • Implications for Practical Parsing: The undecidability results imply that while OLP constraints theoretically guarantee decidable recognition, practically verifying if a grammar meets these constraints is often impossible. This suggests that researchers and practitioners must rely on heuristics or specific grammar classes where these checks might be feasible.
  • Skeletal vs. General Unification Grammars: The paper distinguishes between OLP constraints applicable only to skeletal grammars (which have an explicit context-free backbone) and those applicable to general unification grammars. This distinction is important for understanding the scope and limitations of each definition.

Key Results

The paper's primary results are:

  • Inter-relations between OLP definitions: A detailed comparison and hierarchy of several OLP definitions are presented, illustrating which constraints imply others.
  • Undecidability of Finite Ambiguity (FA): The paper proves that determining if a unification grammar is finitely ambiguous is undecidable. This is shown via a reduction from the membership problem.
  • Undecidability of Depth-Boundedness (DB): The paper proves that determining if a unification grammar is depth-bounded is undecidable. This is shown via a reduction from the Turing machine halting problem.
  • Undecidability of Shieber's OLP (OLPs): The paper proves that determining if a unification grammar satisfies Shieber's OLP constraint is undecidable, by combining the undecidability proofs of FA and DB.

Limitations and Future Work

  • Focus on Undecidability: While the paper proves undecidability for several OLP conditions, it acknowledges that some OLP definitions are decidable. However, it notes that these decidable conditions might be too restrictive, excluding many grammars for which parsing termination is still guaranteed.
  • Proof Sketches: The paper provides "sketches of proofs" for the undecidability theorems. Full proofs are referenced as being available in a separate technical report (Jaeger et al., 2002).
  • Future Work: The authors mention that in their other work (Jaeger et al., 2002), they propose a novel OLP constraint that is applicable to all unification grammar formalisms, is more liberal than existing ones, and importantly, can be tested efficiently. This suggests a direction for future research: finding practical, decidable OLP constraints that capture a broad range of useful grammars.

Summary updated

BibTeX
@inproceedings{jaeger2002guaranteeing,
  author = {Efrat Jaeger and Nissim Francez and Shuly Wintner},
  title = {{Guaranteeing Parsing Termination of Unification Grammars}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}

Loading related content...

Figure