# The Value of Finite Observation in Positive-Data Learning of Multiple Context-Free Languages

arXiv: https://arxiv.org/abs/2605.11644 · HTML: https://mlsanity.com/paper/2605.11644/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 33 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 1 of 1)

- [Decision problems for Clark-congruential languages](https://mlsanity.com/paper/1805.04402/) (2018)

## Abstract (arXiv)

Positive data can show that two tuple occurrences share a successful sentence context without certifying that they are safely interchangeable. We study finite compositional observations, represented by finite-monoid homomorphisms, as semantic side information for learning bounded-fan-out multiple context-free languages from positive data. For every fixed fan-out bound f and supplied finite observation h, we define observation-guarded tuple substitutability and give a canonical set-driven learner that exactly reconstructs every language in the full semantic slice L∈ f-MCFL:L is (f,h)-tuple-substitutable. Under a fixed branching cap, hypothesis construction is polynomial. More generally, polynomial exposure of a presentation implies polynomial characteristic data; binary single-spine presentations provide an explicit sufficient condition. We then vary how much observation information is available. A fixed bound on the size of an unknown observation can be compiled into a universal finite refinement, restoring identifiability slicewise, whereas the unbounded latent-observation union is not identifiable. Moreover, universal finite refinements have an unavoidable exponential dependence on the observation bound, and a separate deletion obstruction shows that no family of set-driven identifiers can have characteristic data polynomial jointly in that bound and presentation size. Intrinsic observation size alone therefore does not determine latent-slice data complexity: the quantitative behavior also depends on whether the witnessing semantic slice is supplied or must be resolved inside a larger ambient class.