Putting Some Weakly Context-Free Formalisms in Order

David Chiang2002 · OpenReview

TL;DR

This paper investigates how different formalisms, like Tree Adjoining Grammars (TAGs) and Context-Free Grammars (CFGs), compare in their expressive power beyond just the strings they generate. By examining formalisms under various interpretations (phrase structures, indexed strings, and linking systems), the authors reveal that their relative strengths and weaknesses shift, offering a more nuanced understanding of linguistic formalism design.

What Problem Does This Paper Address?

The paper tackles the question of how to precisely compare the "strong generative capacity" (SGC) of different formal grammars, particularly those related to Tree Adjoining Grammars (TAGs). While weak generative capacity (WGC) simply measures the set of strings a grammar can produce, SGC aims to capture richer aspects of linguistic structure. However, SGC itself can be interpreted in various ways (e.g., based on phrase structures, dependency structures, or how derivations are linked). The authors highlight that it's not always clear how formalisms like CFGs, Tree Insertion Grammars (TIGs), Regular-Form TAGs (RF-TAGs), and Component-Local Scattered Context Grammars (CL-SCGs) stack up against each other when considering these different, richer notions of generative power. They aim to provide a more formal and precise comparison across these diverse interpretations.

Methods

The authors analyze four formalisms: Context-Free Grammars (CFGs), Tree Insertion Grammars (TIGs), Regular-Form TAGs (RF-TAGs), and Component-Local Scattered Context Grammars (CL-SCGs). They compare these formalisms under four different interpretations of generative capacity:

  • String Sets: The standard WGC, looking at the set of terminal strings generated.
  • Tree Sets (modulo projection): Considering the set of tree structures generated, ignoring specific label details.
  • Indexed String Sets: Examining strings along with equivalence relations on their positions, capturing more structured relationships.
  • Linking Systems (Derivational Generative Capacity - DGC): Focusing on how derivations themselves are constrained and how they relate to the generated indexed strings.

They also introduce and utilize concepts like "indexed strings" and "indexed string tuples" to formalize the analysis of indexed string sets. For synchronous systems, they analyze "string relations" where derivations are isomorphic.

Datasets

Not discussed in the paper. The paper focuses on theoretical comparisons of formalisms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Orthogonal Notions of Power: The paper demonstrates that different measures of "strong generative capacity" can lead to different rankings of formalisms. For instance, TIG is more powerful than CFG in terms of tree sets but not necessarily in terms of indexed string sets. This suggests that measures like phrase structure SGC and derivational generative capacity (DGC) are orthogonal.
  • Shifting Power Dynamics: The relative power of formalisms changes depending on the interpretation. While TIG is more powerful than CFG in some senses, RF-TAG and CL-SCG are not strictly more powerful than CFG in terms of phrase structures. However, RF-TAG and CL-SCG have greater DGC than CFG and TIG.
  • Incommensurability: RF-TAG and CL-SCG are shown to be incommensurate with respect to DGC, meaning each can generate certain indexed string sets that the other cannot. This highlights that even within a specific interpretation of SGC, different formalisms can offer distinct expressive capabilities.
  • Formalizing Richer Structures: The paper introduces and uses "indexed strings" and "linking systems" to formally capture and compare the structural richness of derivations beyond just the final string output.

Key Results

  • Weak Equivalence: CFG, TIG, RF-TAG, and CL-SCG are weakly equivalent (generate the same set of strings).
  • Phrase Structure Power: TIG generates more tree sets than CFG, RF-TAG, and CL-SCG. RF-TAG and CL-SCG are no more powerful than CFG in this regard, modulo projection of labels.
  • Derivational Generative Capacity (DGC):
    • CFG and TIG are derivationally equivalent.
  • RF-TAG and CL-SCG have greater DGC than CFG and TIG.
  • RF-TAG can generate an indexed string set (L₁) that CL-SCG cannot.
  • CL-SCG can generate an indexed string set (L₂) that RF-TAG (and even TAG) cannot.
  • Synchronous Systems: Similar relationships are observed for synchronous versions of these formalisms, with RF-TAG and CL-SCG being incommensurate in terms of synchronous string relations.

Limitations and Future Work

  • Future Research: The authors explicitly state that characterizing the different ways in which strong generative power can be both measured and squeezed is a task for future research. They suggest that understanding these nuances is crucial for designing formal grammars for specific applications.
  • Scope: The paper focuses on a specific set of formalisms and interpretations. Further work could explore other formalisms or different interpretations of generative capacity.
  • Practical Implications: While the paper provides theoretical insights, the direct practical implications for grammar engineering or parsing algorithms are not deeply explored, which could be a direction for future work.

Summary updated

BibTeX
@inproceedings{chiang2002putting,
  author = {David Chiang},
  title = {{Putting Some Weakly Context-Free Formalisms in Order}},
  booktitle = {TAG+},
  year = {2002},
  url = {https://openreview.net/forum?id=_A4-bhWuXbp},
}
Figure