Artificial Intelligence · 21.08.2026, 08:17 UTC
The Value of Finite Observation in Positive-Data Learning of Multiple Context-Free Languages
| Schweregrad | info |
|---|---|
| Kategorie | Artificial Intelligence |
| Quelle | arXiv cs.LG ↗ |
| Veröffentlicht | 21.08.2026 UTC |
Sicherheitsmeldung mit Schweregrad noch nicht bewertet. Technische Details im Tab „Originaltext“; empfohlene Schritte in der Checkliste.
arXiv:2605.11644v3 Announce Type: replace-cross Abstract: 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 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 …