Which Parsing Steps Must a Learner See to Escape Gold's Trap?

A learner that only ever sees valid sentences, and never an example of an invalid one, can be stuck forever. Gold's classic argument shows this happens whenever a grammar family contains a limit point: an infinite chain of languages, each strictly containing the last, whose union is also in the family. Rigid and $k$-valued Lambek categorial grammars have this property, so they cannot be learned from strings (Rigid Lambek Grammars Are Not Learnable from Strings, k-Valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings). In the other direction, Language Identification in the Limit with Computational Trace shows that once each string comes with the full run of a deterministic machine that accepts it, every computable language becomes learnable. The space between these two results is unexplored, and it is where real parsers operate. A deductive parser treats parsing as logical proof: grammar rules are axioms, partial parses are derived "items," and a parse is a theorem (Parsing as Deduction). These proofs are not deterministic machine runs. One sentence usually has many equivalent proofs, and annotators or treebanks typically expose only some of the items, such as bracketed spans.

This note proposes to grade supervision by how much of a deduction the learner sees. The scale runs from strings alone, to unlabeled spans (passive items without categories), to labeled passive items, to full deductions whose form the presenter may choose, to full deductions in a canonical normal form. The goal is to determine, for categorial grammars and binary discontinuous grammars, which rung is the first to remove the limit point. The central bet is that the danger is not missing structure as such but presenter freedom. If the presenter can pick any of the many equivalent derivations of a sentence, that choice can rebuild an inclusion chain over traces. Requiring proofs in a normal form, in the sense of Parsing and Derivational Equivalence, removes that freedom. We test the same graded question empirically by giving an unsupervised discontinuous grammar inducer different partial item supervision and measuring whether it over-generalizes.

Core Claim

Peng, Saberi and Velegkas prove learnability from traces, but their traces are unique by construction: a deterministic automaton has exactly one accepting run. Their noise analysis covers corrupted traces, under which DFAs tolerate constant corruption, DPDAs need vanishing corruption, and Turing machines allow only finitely many errors. It does not cover valid but non-unique traces. We claim that this second regime behaves differently and is the one that matters for deductive parsing. Concretely, we conjecture three things. First, for rigid Lambek grammars, labeled-item traces chosen adversarially among equivalent derivations still admit a limit point when the deductive system has unbounded spurious ambiguity. Second, the same class becomes identifiable when the presenter is restricted to normal-form derivations obtained by Hepple's contraction rules. Third, unlabeled span information alone does not remove the limit point of the $k$-valued construction of Béchet et al., because their nested chain can be realized with identical bracketings.

If these hold, they give a precise answer to the question the Lambek unlearnability papers leave open, namely whether "structured data" suffices. Some structured data does and some does not, and canonicity, not structure, is the dividing line. If the conjectures fail, the failures are just as informative. For example, if adversarial traces already suffice, then derivational ambiguity is harmless for learnability. That would be a clean negative answer to Gap 1 in the file.

Research Program

The theoretical part has three steps. We first formalize a deduction presentation: an infinite enumeration of pairs (string, set of items) in which the item set is a sound subset of some proof of the string under a fixed parsing schema. The schemas are Earley-style deduction for categorial grammars and the span rules of Span-based discontinuous constituency parsing for discontinuous structure. A presentation level is defined by which item types are revealed and by whether the proof is presenter-chosen or canonical.

We then revisit the explicit limit-point constructions. Foret et al. build chains of rigid grammars converging to $c\{a,b\}^*$. Béchet et al. do the same for $k$-valued non-associative grammars. For each construction we ask whether it lifts to the trace level, meaning whether there is a chain of grammars whose sets of traces are strictly nested and whose union is the trace set of a member of the class. A lift proves non-learnability at that level. A failure to lift, together with a learner that reconstructs types from the revealed items, proves learnability. For the canonical-proof case, the learner unifies lexical types read off normal-form derivations, which is the natural extension of the type-unification idea behind the original learnability question. Strong normalization of Hepple's contractions ensures that every derivation has a normal form, so the canonical presenter is always well defined.

Finally, we carry the analysis to binary linear context-free rewriting systems with fan-out 2 (LCFRS-2). These grammars allow constituents made of two separated pieces, which is what the TN-LCFRS inducer of Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars searches over. The aim is a statement of the form "fan-out-2 span items, without labels, are sufficient or insufficient." Its empirical counterpart is the experiment below.

Baselines

The naive reference point is string-only learning. In theory this is Gold's learner, which is known to fail on these classes. In practice it is TN-LCFRS trained on raw NEGRA and LASSY sentences, which reports 46.1 overall F1 and 8.0 discontinuous F1 (DF1) on NEGRA and 8.9 DF1 on LASSY (Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars). A neural probabilistic context-free grammar scores 40.8 F1 and, by construction, 0 DF1. This is the strongest unsupervised competitor because it searches exactly the grammar family we analyze, using the same chart deduction. We rerun it with its released configuration at 4,500 nonterminals and keep architecture, initialization seeds, optimizer, and training steps fixed. The only change is an added log-likelihood term for revealed items, so any gain comes from supervision level and not from tuning.

The supervised ceiling is a fully supervised discontinuous parser. Neural Discontinuous Constituency Parsing reports 83.29 F1 on NEGRA and 50.7% DF1 with its lazier oracle, and 81.64 F1 on TigerSPMRL. We cite these numbers as an upper bound and do not try to beat them. Our learners see a fraction of the items those parsers see.

The key ablation holds the number of revealed items fixed and varies only their canonicity. In one arm, items come from the treebank's derivation. In a second arm, items come from a randomly chosen equivalent derivation under spurious-ambiguity rewrites. In a third arm, items come from a normal-form derivation. Equal item counts rule out "more information" as an explanation. A second control gives string-only training extra raw sentences whose total size in bits matches the bits of the revealed items.

Beating the baseline means two things. DF1 must rise significantly above 8.0 on NEGRA and 8.9 on LASSY at a supervision budget of at most 10% of sentences. The over-generalization probe defined below must also fall. A DF1 gain without a probe gain would not support the learnability story.

Why not just…?

Why not just give the learner full derivation trees and cite Peng et al.? Peng et al.'s proof relies on a unique accepting run of a deterministic machine. A categorial or LCFRS derivation is not unique, and treebank derivations reflect annotator choices. Whether trace uniqueness is load-bearing is exactly what the canonical versus adversarial ablation and the theoretical lift construction decide. If adversarial traces turn out to suffice, the alternative is right and we report that.

Why not just add negative examples? Negative evidence does defeat Gold's argument, and (Im)possibility of Automated Hallucination Detection in Large Language Models shows that detection without it is impossible. However, treebanks and parsers produce proofs, not lists of ungrammatical sentences, and labeled ungrammatical data for German or Dutch discontinuity is not available in our file's resources. We include a scrambled-sentence negative-sampling arm with matched budget. If it matches normal-form item supervision on DF1 and on the probe, the practical case for item supervision weakens to a cost argument, and we would say so.

Why not just bracketed strings? Unlabeled spans are the cheapest structure and the most likely real threat. They are our lowest structured rung, and the conjecture that they fail for the Béchet et al. chain is falsifiable both on paper and in the synthetic experiment. If spans suffice, the proposal collapses to "spans are enough," which is a worthwhile result in itself.

Why not just scale nonterminals or tune initialization? Yang et al. already go from 45 to 4,500 nonterminals, and they still fail on English, where discontinuity is rare (about 1.8%). The probe will tell us whether larger grammars over-generalize more, which classical theory would predict. Scale is held fixed across our arms.

Proposed Experiments

The first experiment is synthetic and serves as a decisive check of the theory. We sample target grammars from the explicit Foret and Béchet chains, including the limit grammar for $c\{a,b\}^*$. We then generate presentations at each rung, including an adversarial presenter that picks derivations to maximize learner confusion, and run the corresponding learners for increasing presentation lengths. The measured quantity is whether, and when, the learner's hypothesis stabilizes on the correct grammar. The theory predicts non-convergence for string-only, span-only, and adversarial-labeled presentations, and convergence for normal-form presentations.

The second experiment uses real treebanks: NEGRA and TIGER for German and LASSY Small for Dutch, with an English sparse-discontinuity condition taken from the TN-LCFRS setup. We train TN-LCFRS with 0%, 1%, 5%, and 10% of sentences carrying item supervision at each rung. Metrics are overall F1 and DF1. We also add an over-generalization probe: the fraction of locally scrambled sentences, built with word swaps that break attested discontinuous patterns, to which the learned grammar assigns higher probability than to the original sentence. Item extraction uses Corro's $O(n^3)$ span schema, which covers 98% of NEGRA and TIGER structures and parses 5,000 TIGER sentences in under 3 seconds. This keeps the supervision pipeline cheap.

The decisive comparison is the canonicity ablation. Suppose normal-form items reduce the scramble-preference rate and raise DF1, while equally many adversarial items do not. That is direct empirical evidence that presenter freedom, the ambiguity Hepple's normal forms remove, is what preserves the limit-point trap in practical grammar induction.