Finite resources limit exact learning in structured grammar and scheduling models
Observer--Fragmentation--Exposure Tradeoffs: From Rectangular CFG Exposure to Ordered MCFG Scheduling
Formal Languages and Automata Theory
Summary
Some computer programs try to learn precise rules from limited observations, but doing this exactly is tricky because resources like observation size and scheduling matter. The authors study how these resources trade off when learning from certain kinds of grammar models, showing exact costs and conflicts that arise. They find distinct limitations related to data fragmentation, observation ordering, and scheduling, explaining when exact reconstruction is possible. These insights clarify how different constraints affect learning and help map the complex tradeoffs in structured data reconstruction.
What this means in practice
- •For language processing developers: Improve algorithms for learning precise grammar rules from limited linguistic data by understanding exact observation and scheduling resource tradeoffs.
- •For compiler engineers: Design more efficient parsers by applying exact characterization of necessary data samples and scheduling constraints in grammar-based code analysis.
A theory result. No direct application yet.
Authors
Takayuki Kuriyama
Abstract
We study finite resources governing exact positive reconstruction in fixed-observation CFG and MCFG learning. For an explicit rigid CFG family we compute safe observation size, internal residual fragmentation, and characteristic-data cost exactly. The result is a two-point Pareto frontier: after compulsory rigidity witnesses are fixed, exact reconstruction reduces to connectivity inside observer fibers, and the variable part of every minimum characteristic sample is a spanning forest of complete bipartite fiber graphs. For bounded-fan-out MCFG reconstruction, pure transition fragmentation multiplies across children. An explicit fan-out-two family X_{k,r} therefore has exact characteristic-data costs 2r[1+r(k-1)] and 2rk^r under two comparable observers. An integral lattice invariant yields an affine-span lower bound and a unimodularity test. In the binary-index subfamily, unimodularity suffices for minimum-cardinality samples through ranks two and three but not rank four. Two distinct obstructions then appear: an order-independent laminar support conflict, and an order-sensitive occurrence-scheduling conflict. For disjoint child requirements, the exact scheduling threshold is the largest monochromatic run count in the doubled reduced slot-colour word; in the two-colour case this is an alternation threshold. Horn nonlocking and Cartesian locking certificates make these constraints explicit. Hierarchical reuse can trade parent-root exposure for local fan-out: for the natural critical-module library of the mixed rank-four shapes, the exact width--anchor frontiers are {(2,1)}, {(2,2),(3,1)}, and {(4,1)} for separated, nested, and crossing orders. Thus observation, fragmentation, exposure, arithmetic span, laminar compatibility, ordered scheduling, and hierarchical reuse are genuinely distinct finite resources.