Abstract
A theory of natural language must be evaluated on both extensional and intensional grounds. This paper investigates the intensional parameters of feature-based grammar formalisms, specifically focusing on computational complexity, learnability, and monotonicity. We establish that while the universal recognition problem for model-theoretic feature-based grammars is NP-complete due to the polysize model property, the introduction of "strong monotonicity" reduces this complexity to deterministic polynomial time. Furthermore, we demonstrate that strongly monotonic unification categorial grammars (UCG) are learnable in the limit from positive data, identifying a potential "sweet spot" for computationally tractable and learnable linguistic formalisms.
Introduction
Linguists frequently employ feature-based grammars, such as Head-driven Phrase Structure Grammar (HPSG) and Unification Categorial Grammar (UCG), to model the intricate, nested structures of natural language. However, the theoretical elegance of these frameworks often clashes with the practical constraints of computational implementation. A linguistic theory faces an adequacy crisis if it describes a language that is either impossible for a computer to parse efficiently or impossible for a system to learn from examples. This research seeks to bridge the gap between high-level linguistic theory and the rigorous constraints of computational logic.
The Problem of Computational Adequacy
The investigation centers on two primary questions regarding the adequacy of feature-based theories:
- Complexity: What is the computational cost of deciding whether a specific string of words belongs to a given feature-based grammar?
- Learnability: Can these grammars be induced or "learned" from a finite set of positive examples, satisfying the criteria for language acquisition?
By treating grammars as sets of logical axioms rather than mere rewrite rules, we can apply the tools of model theory and modal logic to determine the inherent bounds of these linguistic frameworks.
Methodology: A Model-Theoretic Approach
The author adopts a model-theoretic perspective where feature structures are viewed as Kripke frames—a standard construct in modal logic—where "features" function as relations between "nodes." This allows for several key technical maneuvers:
- Hybrid Grammars: The framework combines generative core rules with model-theoretic constraints, allowing for a flexible yet rigorous logical description.
- Polysize Model Property: The research proves that if a string is valid within a grammar, there exists a "small" (polynomial-sized) model to verify it. This property is essential for establishing that the recognition problem resides within the NP complexity class.
- Strong Monotonicity: This constraint is introduced to ensure that each string in a language corresponds to a unique, unambiguous derivation, effectively streamlining the logical search space.
Key Insights and Results
The Complexity of Recognition
The paper establishes that the universal recognition problem for standard HPSG and UCG formalisms is NP-complete. While this means that parsing can be computationally expensive in the worst-case scenario, the discovery of the polysize model property ensures that a proposed solution can at least be verified in polynomial time. This result holds even when considering linearization-based extensions, which are used to handle languages with freer word orders.
The Power of Strong Monotonicity
The most significant breakthrough involves the application of "strong monotonicity." By enforcing this constraint—essentially removing the ambiguity that allows multiple derivations for a single string—the complexity of the universal recognition problem drops from NP-complete to Deterministic Polynomial Time (P). The unification process in these grammars is shown to be highly efficient, governed by the inverse Ackermann function $\omega(\delta)$, making it nearly linear and highly suitable for practical applications.
Learnability in the Limit
Beyond complexity, the paper addresses the "Gold standard" of learnability. It proves that strongly monotonic UCGs are learnable in the limit from positive data. This provides a theoretical foundation for automated grammar induction, suggesting that the very constraints that make a grammar easy to parse also make it easier to acquire.
Discussion and Limitations
The primary challenge to these findings is the Strong Monotonicity Hypothesis itself. Natural languages are inherently ambiguous, and most linguistic theories are designed to account for multiple interpretations of a single string. A grammar that permits only one unique derivation per string is, as the author notes, "very strong and somewhat unnatural" for the full breadth of human speech.
However, these results identify a critical boundary. Future work should focus on "relativizing" strong monotonicity—finding a middle ground that permits necessary linguistic ambiguity without sacrificing the computational benefits of tractability and learnability. By identifying the class of modal languages that define common feature-based formalisms, this research provides the roadmap for developing the next generation of efficient, learnable linguistic theories.
Summary updated