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

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\in f\text{-}\mathrm{MCFL}:L\text{ is }(f,h)\text{-tuple-substitutable}\}$. Under a fixed branching cap, hypothesis cons...

<iframe src="https://silytics.si/embed/item/fff665c4-19c2-4f3d-9ea3-eca7f84f6588" width="420" height="190" style="border:0" loading="lazy" title="Silytics entry"></iframe>

Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.