Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing

Technical Summary: Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs

Problem Statement
The paper addresses the problem of positive-data learning (learning from positive examples alone) for bounded-fan-out linear Multiple Context-Free Grammars (MCFGs) under a fixed explicit finite monoid homomorphism $h: \Sigma^* \to M$.

While Gold's theorem establishes that broad language classes are not identifiable from positive data alone, specific distributional restrictions can enable learning. For Context-Free Grammars (CFGs), Clark and Eyraud demonstrated that restricting the distributional behavior of substrings allows for reconstruction. However, extending this to MCFGs presents a fundamental obstacle: MCFG nonterminals derive tuples of strings rather than single strings. Consequently, the components of a tuple may be scattered throughout the final sentence in varying left-to-right orders. Standard componentwise information (e.g., the $h$-values of the individual tuple components) is insufficient to describe the role of a tuple occurrence because it fails to capture the permutation of components and the boundary intervals between them in the surrounding sentence.

Methodology
The paper introduces a mechanism called sentence-interface types to provide finite external control over tuple occurrences, enabling exact reconstruction.

1. Sentence-Interface Types:
   For a tuple of arity $d$, a sentence-interface type is defined as a pair $(\sigma; m_0, \dots, m_d) \in S_d \times M^{d+1}$.

   • $\sigma \in S_d$: A permutation recording the left-to-right order in which the $d$ tuple components (holes) appear in the final sentence.
   • $m_i \in M$: The $h$-values of the $d+1$ boundary intervals between and around these components.
     This structure creates a finite state space $S_d \times M^{d+1}$ for each arity $d \leq f$, where $f$ is the fixed fan-out bound.

2. Typed Refinement:
   The authors construct a typed refinement of a target grammar $G$. In this refinement, every nonterminal $A$ is split into multiple typed copies $A^\tau_p$, where:

   • $p \in M^{\mu(A)}$ is the componentwise output $h$-type.
   • $\tau \in Ih(\mu(A))$ is the sentence-interface type.
     The refinement is "trimmed" to include only reachable and productive typed copies.

3. Transport Maps:
   To propagate types from parent to child nonterminals during derivation, the paper defines transport maps ($IT^\rho_B$ and $IT^\rho_C$) induced by binary rule templates. These maps compute the interface type of a child occurrence based on:

   • The parent's interface type.
   • The sibling's componentwise output $h$-type.
   • The rule template.
     This ensures that the typed refinement remains finite and computable.

4. Distributional Assumption:
   The learning framework relies on $(f, h)$-tuple substitutability. A language $L$ satisfies this if, for any two tuples $\vec{x}, \vec{y}$ of arity $d \leq f$, if they share the same componentwise $h$-type ($h^{(d)}(\vec{x}) = h^{(d)}(\vec{y})$) and share at least one accepting sentence context, then they share all accepting sentence contexts. This is a weaker condition than Yoshinaka's untyped multidimensional substitutability but is tailored to the fixed-$h$ setting.

5. The Learner:
   A canonical learner is defined that constructs a hypothesis grammar $\hat{G}(K)$ from a finite sample $K$. The learner:

   • Identifies observed typed tuples $[\vec{x} : \tau]$ based on concrete sentence contexts found in $K$.
   • Extracts binary witnesses (concrete segmentations of sample words) to infer binary rules.
   • Adds typed substitution rules for tuples that share a concrete context and have identical $h$-types.

Key Contributions

1. Introduction of Sentence-Interface Types: The paper defines these types as the necessary finite external control objects to handle the permutation and placement of tuple components in MCFGs, a feature absent in standard CFG learning.
2. Rule-Template Transport Maps: The authors define effective maps that propagate interface types through binary rules, ensuring the typed refinement is finite.
3. Construction of Characteristic Sample: A finite characteristic sample $CS(\tilde{G})$ is constructed for the trimmed typed refinement, exposing every surviving typed state and realized typed rule.
4. Exact Reconstruction Algorithm: A canonical positive-data learner is defined that reconstructs the target language exactly once the sample contains the characteristic sample.

Results

• Identification in the Limit: For any fixed fan-out bound $f$ and fixed explicit homomorphism $h$, the class of languages $C^{mcf}_{f,h}$ (languages generated by reduced working binary linear nondeleting MCFGs satisfying $(f, h)$-tuple substitutability) is identifiable in the limit from positive data.
• Polynomial-Time Construction: The hypothesis $\hat{G}(K)$ associated with any finite sample $K$ is constructible in polynomial time with respect to the sample size $\|K\|_+$, including the output size. This holds for fixed $f$ and fixed $h$.
• Exact Reconstruction: If a sample $K$ contains the characteristic sample $CS(\tilde{G})$ and is contained within the target language $L$, the learner's hypothesis generates exactly $L$.

Significance and Scope
The paper positions itself as a fixed-parameter reconstruction result. It does not claim to infer the finite monoid $M$ or to normalize arbitrary MCFG presentations. Instead, it demonstrates that sentence-interface control is the specific finite mechanism that lifts fixed-$h$ distributional reconstruction from CFGs to bounded-fan-out linear MCFGs.

The authors explicitly distinguish their work from Yoshinaka's untyped multidimensional substitutability. While Yoshinaka's condition is stronger (implying the fixed-$h$ condition), the fixed-$h$ setting allows the learner to use the prescribed monoid as external control rather than inferring it. The paper notes that the characteristic sample size depends on the chosen witnessing presentation and the "exposure size" (the length of words needed to expose typed states), and while polynomial-time construction of the hypothesis is guaranteed, a polynomial-size characteristic sample for the entire class is not asserted without further structural constraints.

In summary, the paper establishes that by recording both the permutation of tuple components and boundary monoid values, one can achieve exact, polynomial-time learning of a significant class of mildly context-sensitive languages from positive data, provided the fan-out and the monoid typing are fixed.