Grammars built on feature unification are common in linguistic theory and in classical text generation. In these grammars, words and phrases carry bundles of attributes such as number, case and tense, and building a sentence means merging compatible bundles. Such grammars fail in two ways that have so far been studied separately. The first failure is computational. Graeme Ritchie showed that deciding whether a Functional Unification (FU) grammar can derive a sentence from a given input description is NP-hard, because the grammar's alternatives and shared features can encode Boolean satisfiability (The computational complexity of sentence derivation in functional unification grammar). The second failure is statistical, in the old sense of learning theory. A learner who sees only grammatical sentences cannot identify a grammar class that contains a limit point: an infinite chain of nested languages whose union is also in the class. On such a class, the learner either overgeneralizes and never sees a counterexample, or keeps changing its mind forever. This construction has been used to prove unlearnability for Lambek-style categorial grammars (Rigid Lambek Grammars Are Not Learnable from Strings, k-Valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings), but it has never been applied to FU grammars.
This note proposes that both failures come from the same mechanism: stacks of disjunctions ("either this feature assignment or that one") that are free to interact through shared features. It asks whether one measurable quantity, the disjunction width of a derivation, controls both. We aim to prove three things. First, FU string languages contain limit points built from Ritchie's gadgets. Second, when the learner sees each sentence paired with the semantic input it was generated from, as in the surface-realization setting of computational linguistics, the limit point disappears. Third, for grammars whose width is bounded, each learning update becomes tractable, with exponential cost only in the width. The payoff is a condition much weaker than the "no ambiguity at all" restriction that is currently the only known route to both learnability and tractability. We would also test empirically whether real wide-coverage generation grammars satisfy it.
Core Claim
Define a realization presentation as an infinite sequence of pairs $(\varphi, s)$. Here $\varphi$ is an input functional description, meaning the feature structure a generator starts from, and $s$ is a string that the target grammar $G^*$ derives from $\varphi$. A learner realizes in the limit if its hypotheses eventually stabilize on a grammar with the same input-to-string relation as $G^*$.
For a derivation, the disjunction width is the largest number of unresolved grammar alternatives that are linked by shared features at any point in the unification. For a grammar $G$, the width $w(G)$ is the maximum of this quantity over derivations from well-formed inputs. We call a grammar anchored if every disjunct is triggered by some feature present in the input description. This is the FU analogue of lexicalization.
The claim has three parts. First, the class of anchored FU grammars has limit points over string-only presentations, and the witnessing chain can be built so that $w$ grows along it. Second, over realization presentations, anchored FU grammars with $w(G) \le k$ have finite elasticity, a standard sufficient condition for identification in the limit from positive data. Third, each consistency check the learner makes then costs time polynomial in the input size times $2^{O(k)}$, whereas without the width bound it is NP-hard by Ritchie's reduction. That reduction necessarily needs width that grows with the number of propositional variables. If all three parts hold, width is a single dial: turning it up yields both the hardness result and the unlearnability result, and bounding it removes both.
Three parts of this are conjecture. We expect the string-level limit point to be straightforward. The finite-elasticity result is the risky part, and we state below what would falsify it.
Relation to Prior Work
The closest work is Søgaard's model-theoretic analysis of feature grammars (Logical investigations on the adequacy of certain feature-based theories of natural language). That paper proves universal recognition for HPSG- and UCG-style grammars is NP-complete. It then shows that strong monotonicity, which requires every string to have a unique derivation, brings recognition down to polynomial time and makes the class learnable from positive data. Søgaard himself calls the condition "very strong and somewhat unnatural." Our width bound deliberately allows ambiguity: it permits many derivations as long as the alternatives do not form long chains through shared features. His analysis also does not address generation from semantic input, which is where Ritchie's hardness lives.
Two recent lines supply methods. Language Identification in the Limit with Computational Trace shows that pairing strings with the accepting machine's execution trace makes even Turing-recognizable languages identifiable. It covers only linear automaton traces. We treat the semantic input $\varphi$ as a partial, structured trace. It is weaker than a full derivation, so the trace result does not transfer for free. That gap is exactly why the width condition is needed. Language Generation in the Limit shows that producing new valid strings is possible for any countable class even when identification fails. Language Generation in the Limit: Complexity Barriers and Implications for Learning shows that the number of samples needed is non-computable for context-free languages and double-exponential for regular languages. Both works study unconditioned string generation over Chomsky-hierarchy classes. Neither studies generation conditioned on a semantic input, and neither studies unification grammars.
On the complexity side, other hardness proofs share Ritchie's shape. Berwick's 3-SAT reduction for Lexical Functional Grammar (Computational Complexity and Lexical Functional Grammar) uses lexical ambiguity plus agreement. Koller and Striegnitz's NP-completeness result for realization from flat semantics (Generation as Dependency Parsing) comes from the many possible orderings of constituents. These results constrain our design: they show that width alone cannot be the whole story when the input is flat and unordered. We therefore restrict the tractability claim to hierarchically structured inputs and treat flat semantics as a separate open case. Kaplan and Wedekind's result that LFG generation yields context-free languages (LFG Generation Produces Context-free Languages) motivates the claim that fixing the input sharply limits what the grammar can do. Berwick's acquisition model (Computational Analogues of Constraints on Grammars: A Model of Syntactic Acquisition MIT Artificial Intelligence) is the historical precedent for a single structural restriction serving both parsing and learning. It works in a deterministic, non-unification architecture.
Research Program
The theoretical work has three stages.
The first stage builds the string-level limit point. We start from Ritchie's gadget, which assigns clause and variable truth values through disjunctive feature choices. We then define a family $G_n$ in which the $n$-th grammar admits one more independent disjunct, and prove that the string languages nest strictly. The final step is to exhibit a single finite FU grammar whose language is the union. This is possible because FU grammars allow recursive descriptions: the union grammar uses recursion to permit unboundedly many disjuncts. Its width is therefore unbounded, which is the predicted signature.
The second stage proves finite elasticity for bounded-width anchored grammars over realization presentations. The intuition is that an anchored disjunct can only matter for strings produced from inputs containing its anchor feature. With width at most $k$, the number of distinguishable disjunct combinations per anchor is bounded. An infinite elastic chain would therefore need infinitely many distinct anchor configurations inside a finitely describable grammar.
A counterexample would falsify this stage: a bounded-width anchored family that still has an infinite chain of realization relations whose union is in the family. We will actively search for one, for example by building chains that vary word order rather than disjunctions. If we find one, we will report it and add an ordering constraint to the condition.
The third stage makes the learner concrete. We use a consistent, conservative learner that enumerates grammars. For each candidate it checks all observed pairs, using a width-parameterized unification algorithm that processes the shared-feature graph of alternatives in tree-decomposition style. This gives the $2^{O(k)}$ cost per check.
Baselines
The naive reference point is a string-only conservative learner run on the same grammar families with the semantic inputs removed. Theory predicts that it changes its mind without bound on the limit-point chain. Its mind-change curve is the floor that every other method must beat.
The strongest principled competitor is a learner restricted to strongly monotonic grammars, following Logical investigations on the adequacy of certain feature-based theories of natural language. It has the only existing guarantee of both tractability and learnability, so it is the fair bar. It receives the same realization presentations, the same enumeration order and the same compute limit. We beat it if our bounded-width learner converges on target grammars that have ambiguity, which the monotonic learner cannot represent, while matching its convergence speed on unambiguous targets.
The strongest practical competitor for the generation side is chart-based realization with packing: RTGen from RTG based surface realisation for TAG. On the SEMXTAG MODIFIERS benchmark it reports an average unpacked chart size of 918.31, against 2,018 for the GENI realizer. On the COMPLEXITY benchmark we found no reported runtime on Lacuna. For timing context, Generation as Dependency Parsing reports 470 ms and 170 ms on two XTAG sentences, and Integrated sentence generation using charts reports 13 ms against 50 ms for CRISP in complex GIVE scenes.
These systems do not learn anything, so the comparison is about realization cost only. We beat RTGen if our width-parameterized realizer's chart size tracks measured width and matches or undercuts 918.31 on MODIFIERS. The more important use of these benchmarks is diagnostic: we measure the width of the derivations these realizers actually construct.
The key ablation removes the width bound but keeps the semantic inputs. It isolates whether the semantic pairing alone removes the limit point, as the trace results would suggest, or whether width is also needed.
Why not just…?
Why not just enforce strong monotonicity, which already gives both guarantees? It removes the very ambiguity our target phenomena need. Generation as Dependency Parsing reports single words mapping to over 100 TAG trees in XTAG, and a uniqueness condition cannot represent that grammar at all. The baseline comparison above measures how many target grammars each condition admits. If bounded width turns out to admit essentially no more natural grammars than strong monotonicity, that result is negative for us, and we will report it as such.
Why not just run Kleinberg and Mullainathan's generation algorithm on the countable class of FU grammars? For unconditioned string generation this is a real threat. The algorithm applies to any countable class. It does, however, need membership tests, and FU derivation is NP-hard at best. It also produces some valid string, not a realization of a given meaning. The Arenas et al. barriers suggest its sample needs would be at least as bad as for context-free languages. We concede the unconditioned case to that line of work and claim only the semantics-conditioned setting. We will also run the critical-language procedure on our synthetic families as a secondary baseline.
Why not just provide negative evidence? (Im)possibility of Automated Hallucination Detection in Large Language Models shows that labeled negatives make the problem easy for countable classes. It therefore cannot tell us what structure makes learning possible without them. Semantic inputs, by contrast, are routinely available in generation corpora such as GIVE-2 (The GIVE-2 Corpus of Giving Instructions in Virtual Environments).
Why not just rely on heuristic pruning in practice? Pruning gives up completeness and says nothing about learning. The empirical question it raises is whether real grammars already live at low width, which would explain why pruning works. That is our decisive check below.
Proposed Experiments
Synthetic grammar families will instantiate the limit-point chain, Ritchie-style hard instances, and bounded-width anchored grammars at $k$ from 1 to 6. On each family we record mind changes until convergence, time per update, and exact realization accuracy on held-out inputs, for the string-only learner, the monotonic learner, our learner, and the ablation. The theory predicts that time per update grows exponentially in $k$ but only polynomially in input size, and that the ablation fails to converge on at least one family.
The decisive empirical check comes from natural grammars. We instrument chart realization on the SEMXTAG MODIFIERS and COMPLEXITY benchmarks and on the XTAG test sentences, and record the disjunction width of every derivation. If width stays small and roughly constant as inputs grow, while chart size grows, bounded width is a credible naturalness condition. If width grows with modifier stacking, the tractability half of the claim fails for natural language. We would then report that honestly, even if the learnability half survives.
References
- The computational complexity of sentence derivation in functional unification grammar
- Rigid Lambek Grammars Are Not Learnable from Strings
- k-Valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings
- Logical investigations on the adequacy of certain feature-based theories of natural language
- Language Identification in the Limit with Computational Trace
- Language Generation in the Limit
- Language Generation in the Limit: Complexity Barriers and Implications for Learning
- Computational Complexity and Lexical Functional Grammar
- Generation as Dependency Parsing
- LFG Generation Produces Context-free Languages
- Computational Analogues of Constraints on Grammars: A Model of Syntactic Acquisition MIT Artificial Intelligence
- RTG based surface realisation for TAG
- Integrated sentence generation using charts
- (Im)possibility of Automated Hallucination Detection in Large Language Models
- The GIVE-2 Corpus of Giving Instructions in Virtual Environments