In computational linguistics, a central question is whether the underlying structure of a language can be inferred solely from a sequence of valid sentences. This process, known as grammar induction, is theoretically possible for some systems. For instance, the authors of Reversible demonstrated that complex linguistic structures like the English auxiliary verb system can be learned efficiently using $k$-reversible automata.
However, when we move to logic-based models like Lambek categorial grammars, the boundaries of learnability become much tighter. Recent research has shown that even when these grammars are heavily restricted, they remain fundamentally unlearnable from string data alone.
The Rigidity Constraint
To make grammar induction tractable, researchers often impose constraints on the complexity of the grammar. One of the most common constraints is rigidity. A grammar is considered "rigid" if it assigns exactly one grammatical type to each word in its vocabulary. This prevents the ambiguity of a word functioning as multiple parts of speech, which one might assume would simplify the learner's task.
Despite this simplification, Foret et al. proved that rigid Lambek grammars are not learnable from strings. This result is significant because it suggests that the difficulty of learning does not stem from lexical ambiguity, but rather from the inherent logical power of the Lambek calculus itself.
The Problem of Limit Points
The mathematical reason these grammars fail to be learnable lies in the existence of limit points. In the framework of inductive inference, a class of languages is unlearnable if it contains an infinite sequence of languages $L_1, L_2, L_3, \dots$ such that each language is a subset of the next, and their limit (the union of all languages in the sequence) is also a member of the class.
If a learner sees a finite set of strings, they cannot distinguish whether they are looking at a specific language $L_n$ or the infinite limit language $L_\infty$. As Foret et al. show, the deductive rules of the Lambek calculus—specifically how it handles implications and empty sequences—allow for the construction of these problematic limit points. Even with the "one type per word" restriction, the types themselves can be constructed to be infinitely complex, allowing the grammar to represent increasingly larger sets of strings that eventually converge.
Structural Variations and Learnability
The unlearnability of these systems is robust across different variations of the calculus:
- Non-Associative Grammars: In some models, the order of grouping words (the "bracketing") matters. Béchet et al. extended the negative results to Non-Associative Lambek Categorial Grammars ($NL$). They found that even $k$-valued grammars (where a word can have up to $k$ types) are unlearnable from strings, proving that the logical constraints of grouping are too complex for a learner to resolve without additional structural information (like parse trees).
- Associative-Commutative Grammars: Some calculi allow for free word order (commutativity). Costa Florencio demonstrated that rigid grammars in the Associative-Commutative Lambek Calculus (LP) are also unlearnable. Interestingly, the author notes that this proof relies on the presence of "product" rules in the logic, suggesting that the specific logical operators available to the grammar are what drive the complexity.
Syntax vs. Semantics
The difficulty of learning these grammars highlights a deeper distinction in algorithmic learning theory. As Gao et al. explore in the context of mathematical structures, there is often a dichotomy between semantic and syntactic learnability.
In the case of Lambek grammars, the "semantics" (the set of strings produced) might seem simple, but the "syntax" (the specific logical types and rules that generate those strings) is where the learning fails. The research across these papers suggests that for logic-based linguistics, strings alone do not provide enough signal to recover the sophisticated deductive machinery required to generate them.
Key Foundational Work
Rigid Lambek Grammars Are Not Learnable from Strings (2002) — contributed 6 concept elements to this direction.
Reversible Automata and Induction of the English Auxiliary System (1985) — contributed 1 concept elements to this direction.