Constraints on Strong Generative Power

David Chiang

Introduction

In formal linguistics, there is a classic distinction between weak generative power—the set of sentences a grammar can generate—and strong generative power—the structural descriptions, such as parse trees, it assigns to those sentences. While researchers often seek complex grammars like Tree Adjoining Grammars (TAGs) to capture linguistic nuances, they are frequently constrained by the need for computational efficiency. This paper addresses the fundamental question: "How much structural complexity can be added to a grammar without making it harder to parse than a simple Context-Free Grammar (CFG)?"

The Problem with Weak Equivalence

The author argues that "weak context-freeness" is an insufficient constraint for linguistic theory. It is mathematically possible to construct a grammar that produces a context-free string set but contains such complex internal structures that parsing requires $O(n^6)$ time or worse, rather than the standard $O(n^3)$ associated with CFGs. Simply preserving the string set (weak power) allows for "structural junk" that degrades performance.

Methods: Simulability and MMTAG

To resolve this, the paper introduces the concept of simulability. A grammar $G'$ is said to simulate $G$ if $G'$ generates the same strings as $G$ and its derivations can be mapped bijectively to the structural descriptions of $G$. This ensures that a standard parser (like a CKY parser) can reconstruct the complex grammar's derivations using standard table-filling logic.

The author proposes a new formalism called Multicomponent Multifoot Tree Adjoining Grammar (MMTAG). This system combines multicomponent TAGs (where sets of trees are added simultaneously) with "multifoot" trees (allowing multiple insertion points). To maintain efficiency, the author defines a "regular form" for MMTAGs that prevents unbounded structural growth.

Figure 3: Tree structures illustrating elementary trees (a) and auxiliary tree adjunction (b) in the MMTAG formalism.

Key Results: The Limits of Complexity

The central finding of the paper is Proposition 2, which states that a grammar from a Context-Free Rewriting System (CFRS) is simulable by a CFG if and only if it is "trivially simulable" by an MMTAG in regular form. This identifies MMTAG as the "maximal" formalism for CFGs; any structure more complex than what a regular-form MMTAG can describe cannot be efficiently simulated by a CFG.

Figure 4: Formal production rules and tree mappings defining a simulable Context-Free Rewriting System.

By identifying this bound, the author demonstrates that any grammar within the MMTAG regular-form family can be parsed in cubic time ($O(n^3)$). This provides a powerful theoretical tool for linguists who need more descriptive power than a CFG but require high performance.

Conclusion

This work establishes a rigorous mathematical limit on the strong generative power of efficient grammars. While the definitions of MMTAG and its regular form are mathematically dense, they provide a clear roadmap for developing formalisms that balance linguistic expressivity with computational tractability. Future work remains to determine the practical utility of MMTAG in describing specific natural language phenomena and to develop accessible toolkits for its implementation.

Summary updated

Abstract

We consider the question "How much strong generative power can be squeezed out of a formal system without increasing its weak generative power?" and propose some theoretical and practical constraints on this problem. We then introduce a formalism which, under these constraints, maximally squeezes strong generative power out of context-free grammar. Finally, we generalize this result to formalisms beyond CFG.
BibTeX
@inproceedings{chiang2001constraints,
  author = {David Chiang},
  title = {{Constraints on Strong Generative Power}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2001},
  doi = {10.3115/1073012.1073030},
}
Figure