PaperlayerView exact revision on arXiv

Source-linked AI summary

Observer--Fragmentation--Exposure Tradeoffs: From Rectangular CFG Exposure to Ordered MCFG Scheduling

Takayuki Kuriyama

arXiv:2609.34560v1cs.FL

TL;DR

Exact positive reconstruction in fixed-observation CFG and MCFG learning depends on several distinct finite resources. The paper analyzes explicit test families using connectivity, arithmetic, laminar, and ordered-scheduling criteria. It derives exact observer-sensitive costs and scheduling thresholds, while showing that arithmetic unimodularity alone is insufficient at rank four.

  • Problem

    The paper asks which finite resources are required for exact positive reconstruction under fixed-observation CFG and MCFG learning.

    Source: §1 · p. 1

  • Method

    The paper analyzes explicit CFG and MCFG families through observer-fiber connectivity, integral lattice invariants, occurrence-trace reachability, and ordered support scheduling.

    Source: §5.3 · p. 23, §5.6 · p. 28, §6.2.2 · p. 34

  • Results

    In the binary-index family, a minimum-size unimodular sample first fails to lock at rank four, and disjoint child requirements need fan-out equal to the largest monochromatic run count in the doubled reduced colour word.

    Source: §8 · p. 38

  • Takeaways & Limitations

    Observation, fragmentation, exposure, arithmetic span, laminar compatibility, ordered scheduling, and hierarchical reuse are distinct finite resources in the studied reconstruction families.

    Source: §7 · p. 37, §8 · p. 38

    The results concern explicit finite test families and do not establish a non-context-free language separation.

    Source: §5.2 · p. 21

Abstract

from arXiv · show

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.

1 Introduction

The paper asks which finite resources exact positive reconstruction requires, separating observation, fragmentation, exposure, arithmetic span, scheduling, and reuse. It quantifies these resources for explicit CFG and MCFG families while limiting its claims to the stated learners and test families.

1 Introduction

  • The paper separates six resources—finite observation, semantic fragmentation, positive exposure, arithmetic span, ordered scheduling, and hierarchical reuse—that can affect reconstruction differently.Its objective is resource analysis inside fixed-observation positive reconstruction, not a new general CFG or MCFG learnability theorem.Source: §1 · p. 1, Relation to prior work and scope · p. 2
  • For the rigid CFG family, the observer–fragmentation–exposure tradeoff has an exact two-point Pareto frontier.After compulsory rigidity witnesses are fixed, exposure reduces to typed rectangular closure, and minimum-sample variable parts are spanning trees in observer fibers.Source: §1 · p. 1
  • For higher-rank reconstruction, transition fragmentation multiplies across children, while arithmetic span alone does not guarantee derivational realizability.The paper separates the remaining obstruction into laminar support compatibility and, for disjoint supports, order-sensitive occurrence scheduling.Source: §1 · p. 2
  • The exact ordered-scheduling threshold is characterized by run counts, and hierarchical reuse trades additional exposed parent configurations for smaller local fan-out.These results concern explicit finite test families and do not separate MCFG language classes.Source: §1 · p. 2

Relation to prior work and scope

  • The paper builds on fixed-finite-monoid reconstruction schemes and classical combinatorial tools, while claiming novelty for their exact realization in the stated learners and resource phenomena.It does not claim that its Horn and Cartesian certificates decide arbitrary MCFG samples.Source: Relation to prior work and scope · pp. 2–3

2 Reconstruction setting and finite observation

The paper fixes finite-observation CFG and MCFG reconstruction operators and studies characteristic samples for those operators. It also specifies how observers and observed tuple occurrences shape the available reconstruction rules.

2 Reconstruction setting and finite observation

  • A safe observer separates every conflicting pair; for MCFG, tuple substitutability requires equal componentwise observer types and a shared complete context to imply equal tuple distributions.The paper uses unary residual classes in its CFG section and the stated tuple convention for its MCFG learner.Source: §2.1 · p. 3
  • A characteristic sample locks the specified reconstruction operator: every finite positive sample containing it reconstructs the target language.The definition is learner-specific, not a guarantee for arbitrary learners.Source: §2.1 · p. 3
  • The CFG operator uses observed states and rule families R1–R5, while the MCFG operator builds states from observed tuples and composition rules from qualifying occurrences.The MCFG occurrences use nonempty, disjoint intervals ordered left-to-right, and the characteristic-data claims concern this explicitly specified operator.Source: §2.1 · pp. 3–4
  • Under observer refinement, the refined-observer CFG grammar is a subgrammar, and characteristic samples transfer to the coarser observer when the target is substitutable for it.Consequently, a genuine tradeoff between larger observers and smaller fragmentation or characteristic data must use incomparable observers.Source: §2.1 · pp. 4–5

3 Exact CFG observer–fragmentation–exposure tradeoff

For the rigid length-three CFG family, safe observation size, live residual fragmentation, and characteristic-sample cost are quantified exactly. Once mandatory rigidity words are fixed, reconstruction reduces to spanning-tree choices within observer fibers, yielding a two-point Pareto tradeoff unchanged under intrinsic internal-live fragmentation.

3.1 The rigid-wrapper family

  • The rigid-wrapper family pairs main words with private rigidity witnesses, producing length-three targets whose live factors exhibit structured conflicts and residual classes.The live distributions make the p_s and a_i families, the prefixes p_s a_i, and main suffixes a_i a_j distinct conflict or residual structures; factors of different lengths do not conflict.Source: §3.2 · pp. 5–6, §3.1 · p. 5

3.2 Exact live distributions and conflicts

  • The live-factor analysis identifies pairwise conflicts among p_s, a_i, and p_s a_i, while main suffixes share one residual class and private-witness suffixes form row-specific classes.Factors of different lengths do not conflict, separating these internal conflict structures by length.Source: §3.2 · pp. 5–6

3.3 Observation complexity and forced live fragmentation

  • For every m and q ≥ 2, the family requires exactly qm observer values; at minimum observation size, its main-suffix class necessarily splits into m values.If the class has fewer than m values, every safe observer needs at least q(m + 1) image values, a bound attained with fragmentation one.Source: §3.3 · pp. 6–8

3.4 Rectangular exposure and spanning-tree structure

  • Within each observer type block, rectangular closure completes every connected bipartite component to a complete rectangle; minimum full exposure is a spanning tree per block.These minimum exposures are bases of the direct sum of the corresponding graphic matroids.Source: §3.4 · pp. 8–9

3.5 Exact characteristic-data cost

  • For every safe observer h, the minimum characteristic sample has qm + m^2 + κ_h(q − 1) examples: qm rigidity witnesses plus spanning trees connecting rows and suffixes within each fiber.Each target word has length three, so encoded size is four times the sample cardinality.Source: §3.5 · p. 11
  • After the compulsory qm rigidity words are fixed, each fiber’s variable minimum sample is a spanning tree of K_q,nt, and the fiber choices are independent.Equivalently, the variable sample is a basis of the direct sum of the fibers’ graphic matroids.Source: §3.5 · pp. 11–12
  • For the main block of R_m,q, the fixed-h learner generates exactly the typed rectangular closure of the sample’s row–suffix incidence relation using the h-fiber partition.This identifies the exact characteristic-data result as a specialization of the rectangular-closure theorem.Source: §3.5 · p. 12

3.6 The exact three-resource Pareto frontier

  • The global Pareto frontier over safe finite-monoid observers of R_m,q consists of exactly two points; no third Pareto-minimal point exists.The proof shows that observers with κ_h ≥ m are dominated by one frontier point, while those with κ_h < m are dominated by the other.Source: §3.6 · p. 12
  • For q = 2, the frontier points are (2m, m, 4m(m + 3)) and (2m + 2, 1, 4(m + 1)^2).Adding two observation values eliminates m − 1 copies of the critical live residual state and saves 4(m − 1) units of encoded positive characteristic data.Source: §3.6 · p. 13
  • The same two points form the global Pareto frontier when κ_h is replaced by language-level internal-live fragmentation ifrag_h(R_m,q).For arbitrary observers, the proof bounds internal-live fragmentation below by κ_h and uses the same two dominating profiles.Source: §3.6 · p. 13

4 Higher-rank fragmentation and exponential exposure

Higher-rank operations amplify observation fragmentation because child type fibers combine into typed rule cells. A finite fan-out-two family makes the resulting exposure gap explicit: a slot observer admits a characteristic sample, while the index observer requires the whole language.

4.1 Pure residual transitions and rank amplification

  • For a witnessed rank-r transition, typed child cells form a Cartesian product, so k type fibers per child yield k^r transition cells.The full typed expansion counts these realized typed copies; the output type is determined by the child-type tuple and template.Source: §4.1 · p. 15

4.2 Cell-isolated positive exposure

  • A cell-isolated transition needs at least one positive exposure word per typed cell, and exact cell-exposability attains that bound.Each word can expose at most one cell, and no composite simulation can replace a missing cell under the definition's isolation conditions.Source: §4.2 · p. 16

4.3 The fan-out-two family and exact observer gap

  • For X_{k,r}, the slot observer has a characteristic sample of cost 2r[1+r(k−1)], while the index observer's minimum cost is 2rk^r.The index observer forces any characteristic sample to contain all k^r words, each of length 2r; the slot observer is safe through fan-out two.Source: §4.3 · pp. 16–18

5 Arithmetic information versus derivational realizability

This section distinguishes arithmetic constraints on positive samples from whether derivation trees can realize the required changes at compatible occurrences in bounded-fan-out MCFG reconstruction. It develops additive and affine-lattice lower bounds, an exact coarse-observer cost, and a laminar trace system and hierarchical envelope for testing derivational reachability.

5.1 An abstract additive locking principle

  • The additive-locking schema applies conditionally to set-driven systems with sample-anchored starts and additive local increments, placing every generated output in the sample’s affine lattice.The schema does not claim to cover systems without this increment interpretation.Source: §5.1 · pp. 18–19

In particular

  • Characteristic samples must generate the full target difference lattice from their anchor differences, so |K| - 1 is at least its rank.Source: §5.1 · p. 19, In particular · p. 19

5.2 Affine lower bound and exact coarse-observer cost

  • 2r[1+r(k-1)] is the exact hslot characteristic-data cost, attained by Ck,r; the affine invariant confines every generated index pattern to the sample’s affine hull.Thus every characteristic sample has at least 1+r(k-1) words, and the cited construction attains that bound.Source: §5.2 · pp. 20–21

5.3 Integral strengthening: affine lattices and unimodularity

  • For a minimum-size sample, characteristic status requires |det MK|=1; the cited four-word sample has determinant absolute value 2 and is a real affine basis, but is not characteristic.Source: §5.3 · p. 23

5.4 A hierarchical obstruction beyond unimodularity

  • The hierarchical two-interval envelope over-approximates fan-out-two derivations through observed unary mobility and recursive replacements on disjoint proper child masks; failure to contain a target certifies non-locking.If a mask contains exactly one position of a slot pair, every envelope filling preserves that position’s index.Source: §5.4 · pp. 24–25
  • At (k, r) = (2, 4), a five-row unimodular sample with lattice defect one is not characteristic, exposing an occurrence-realizability obstruction beyond arithmetic span.For this sample, mandatory upward and downward supports conflict in a laminar, order-independent way, so increasing fan-out cannot make the required sibling supports disjoint.Source: §5.4 · p. 27

5.5 Graphic sufficiency and the sharp low-rank boundary

  • A connected one-slot exchange graph with every slot index observed suffices for characteristic reconstruction; at minimum size, samples are unimodular, but binary unimodularity locks at ranks 2 and 3, not 4.The first graphic implication is strict at rank three, while the arithmetic implication becomes strict at rank four.Source: §5.5 · p. 28

5.6 The exact middle layer: laminar occurrence-trace reachability

  • The exact middle layer is a laminar trace system whose reachability characterizes characteristic samples, making minimum characteristic samples exactly minimum-cardinality laminar trace locking sets.Its child supports are disjoint within a parent and recursively nested or disjoint; its composition rules retain nonpermuting and nonmerging witness guards. K3 has full laminar reachability despite a disconnected exchange graph, whereas K⋄ has full lattice span but proper laminar reachability.Source: §5.6 · pp. 29–30

6 Ordered scheduling and analytic locking certificates

This section examines how physical slot order governs rank-four characteristicness and fan-out-limited support scheduling, including exact scheduling thresholds and reusable Horn-conflict and Cartesian-cover certificates. For mixed rank-four shapes K10 and K13, ordered support conflicts and Cartesian covers provide sound dual certificates for crossing, separated, and nested orders, but not a complete decision procedure for arbitrary X2,r.

6.1 Analytic critical-matching theorem

  • For either mixed rank-four shape, characteristicness holds exactly when the critical matching is noncrossing; crossing order yields a proper Horn half-cube of reachable full words.The matching’s relation to physical slot order—separated, nested, or crossing—accounts for the mixed behavior.Source: §6.1 · p. 30
  • The eight nonlocking orderings are exactly the stabilizer of the crossing perfect matching, forming a copy of D4 inside S4.The rank-four order effect is analytic: crossing preserves a scheduling invariant, while noncrossing orders admit constructive positive saturation.Source: §6.1 · p. 30

6.2 Dual structural certificates beyond the rank-four census

  • The dual certificates separate support-conflict nonlocking from Cartesian-cover locking: mandatory up/down supports cannot occupy disjoint children, while sampled anchors and independently saturable child blocks can cover the target cube.The Cartesian-cover certificate implies characteristicness for the slot observer when its boxes cover the target.Source: §6.2 · p. 31, §6.2.2 · p. 36

6.2.1 Exact alternation characterization of support conflict

  • For disjoint slot sets U and D, the least fan-out allowing disjoint complete-slot supports is exactly alt(U, D), the number of runs in their reduced ordered two-colour word.Overlapping sets cannot have disjoint supports at any finite fan-out; the threshold can be computed by scanning the slot order.Source: §6.2.1 · pp. 32–33

6.2.2 Multiway support scheduling and the positive block-cover number

  • For disjoint child slot sets, the least common fan-out for pairwise disjoint sibling supports equals the multiway block-cover number, with each child’s component need given by its runs in the doubled colour word.At fan-out two, this is possible exactly when each child label appears in one uninterrupted block of the reduced one-half word.Source: §6.2.2 · pp. 33–34
  • For slots a < b < c < d, separated, nested, and crossing matchings require component vectors (2, 2), (3, 2), and (4, 4); only separated children fit as fan-out-two siblings.Nested order instead requires a two-anchor construction, while crossing requires four components for each child in simultaneous placement.Source: §6.2.2 · p. 34
  • A complete bipartite graph of trace-incompatible mandatory up/down supports certifies a protected Horn implication, while scheduling compatibility alone does not establish learnability.A positive locking certificate additionally needs the relevant observed child states and sufficiently large fill sets.Source: §6.2.2 · p. 35
  • In the crossing order, mandatory supports form a complete conflict graph, and Theorem 6.12 certifies the proper Horn half-cube.The dual-certificate result applies to each ordered copy of K10 and K13.Source: §6.2.2 · p. 36
  • In the separated order, one sampled full parent and two saturated adjacent critical pairs yield a single Cartesian box covering the four-cube.The two saturated pair fill sets each have size four.Source: §6.2.2 · pp. 36–37
  • In the nested order, two size-eight Cartesian boxes from opposite outer-anchor values cover all sixteen vertices of the four-cube.Each box varies the saturated inner pair and directly switchable outer collateral coordinate while fixing the unswitched outer coordinate.Source: §6.2.2 · pp. 36–37
  • The crossing/noncrossing classification uses two finite certificate schemes, but Horn-conflict and Cartesian-cover tests are not complete for arbitrary X2,r.They capture ordered support incompatibility or finitely many independent child fill sets, retaining scheduling information that affine and lattice relaxations discard.Source: §6.2.2 · pp. 36–37

7 Hierarchical reuse and width–anchor tradeoffs

Hierarchical reuse trades local fan-out against exposed parent-root branches: certificate width is the maximum local width, not a sum across depth. For the natural critical-module library, the exact width–anchor frontiers depend on whether the critical matching is separated, nested, or crossing.

7 Hierarchical reuse and width–anchor tradeoffs

  • The block-cover number measures positional width for one simultaneous sibling decomposition, whereas a derivation can reuse exposed parent configurations at different branches.The exact frontiers apply to the natural library of exposed critical-pair saturations and collateral singleton switches.Source: §7 · pp. 37–38
  • A hierarchical Cartesian certificate combines local fill sets, unary routing, and disjoint child blocks under exposed parents, with width measured by the maximum fan-out at any node.The setup treats width and the number of parent-root branches as separate resources.Source: §7 · p. 37
  • For the two mixed rank-four shapes, flat versus hierarchical fan-out thresholds are separated 2/2, nested 3/2, and crossing 4/4.Nested order therefore has a strict one-unit hierarchy dividend.Source: §7 · p. 37
  • The exact width–anchor frontiers are separated {(2,1)}, nested {(2,2),(3,1)}, and crossing {(4,1)}.In nested order, reducing local width from three to two requires one additional exposed parent branch.Source: §7 · p. 38
  • Certificate trees can reuse exposed parent configurations across branches, so composition depth does not add widths; each product node still pays its child-block cover number.At nested width two, two parent roots are necessary and sufficient because one root covers only one selector slice.Source: §7 · pp. 37–38
  • The CFG family trades observation against positive exposure, while the mixed MCFG family trades local composition width against hierarchical reuse of exposed parent configurations.The paper presents these as distinct Pareto phenomena.Source: §7 · p. 38

8 Discussion and research interpretation

The discussion separates finite resources that characteristic-sample arguments often bundle together. Across the explicit CFG and MCFG families, observer-sensitive fragmentation, arithmetic span, ordered derivability, and hierarchical reuse impose distinct constraints on exact reconstruction.

8 Discussion and research interpretation

  • The CFG family has an exact two-point Pareto frontier linking observer size, internal-live fragmentation, and characteristic-data cost, with minimum variable samples given by spanning-tree bases in observer fibers.After compulsory rigidity witnesses are fixed, exposure becomes bipartite connectivity within those fibers.Source: §8 · p. 38
  • For Xk,r, comparable observer refinement changes characteristic-data cost from 2r[1 + r(k −1)] to 2rkr, while transition fragmentation multiplies across children.The coarse learner also has an integral additive locking invariant, but a minimum-size unimodular sample first fails to lock at rank four in the binary-index family.Source: §8 · p. 38
  • For disjoint child requirements, the least common fan-out is the largest monochromatic run count in the doubled reduced child-colour word, specializing to an alternation threshold for two colours.This turns ordered occurrence geometry into an exact scalar scheduling cost.Source: §8 · p. 38
  • Crossing critical-matching order preserves a proper Horn half-cube, whereas separated and nested orders lock constructively through Horn-conflict and Cartesian-cover certificates.The two certificates use the same run geometry in negative and positive directions.Source: §8 · p. 39
  • Hierarchical reuse pays the maximum local block-cover cost rather than a sum over depth, trading local width against exposed parent-root branches in nested order.The natural library gives single Pareto points (2, 1) and (4, 1) in separated and crossing orders.Source: §8 · p. 39
  • The appendices retain weighted refinements, incidence formulations, residual-core connections, the rank-four census, witness-hypergraph machinery, and detailed low-rank and scheduling proofs.These support the main theorem packages without changing the central resource hierarchy.Source: §8 · p. 39

A Observer-fiber refinement penalties and weighted extensions

The rectangular theorem also quantifies the exact cost of splitting an observer fiber, not only the absolute exposure cost.

A Observer-fiber refinement penalties and weighted extensions

A.1 Additive-weighted rectangular exposure

Weighted rectangular exposure has an exact minimum-cost characterization through spanning trees, and splitting observer-type blocks has an exact exposure penalty. Along refinement chains exposure rises, while the paper’s two Pareto-optimal observers are algebraically incomparable.

A.1 Additive-weighted rectangular exposure

  • Each type block’s minimum sufficient exposure is a minimum spanning tree, and additive weights yield an explicit block contribution from row and column minima.The tree result follows from the weighted rectangular-exposure theorem; the additive-weight expression uses the minimum row and column weights.Source: §A.1 · p. 39
  • Splitting one type block into s nonempty blocks adds exactly (s −1)(r −1) unweighted positive incidences and has a nonnegative weighted cost penalty.The weighted penalty is expressed using the minimum spanning-tree weight; its nonnegativity is stated for the split.Source: §A.1 · pp. 39–40
  • The two Pareto-optimal observers are algebraically incomparable: the larger global observer spends states elsewhere so its partition of the critical class is coarser.Along a refinement chain, fiber partitions only split and exposure cost rises; the tradeoff instead reallocates finite algebraic information between global separation and local fragmentation.Source: §A.1 · p. 41

B Abstract transport–substitution interfaces

Transport and same-type substitution generate a rectangular closure inside each type fiber, separating the local reconstruction mechanism from grammar syntax. Under rectangular isolation, full reconstruction is equivalent to connected spanning incidence in every type fiber.

B Abstract transport–substitution interfaces

  • Transport and same-row type substitution define an occurrence graph whose components generate complete row–column rectangles within type fibers.The occurrence graph is the line graph of the corresponding bipartite incidence graph.Source: B Abstract transport–substitution… · p. 41
  • For any rectangularly isolated interface, full reconstruction of P × C is equivalent to connected spanning incidence in every type fiber.The rectangular reconstruction principle applies without reference to CFG syntax.Source: B Abstract transport–substitution… · pp. 41–42
  • In the fixed-h CFG constructor, rows are observed two-sided contexts and columns are observed nonempty factors; the unary occurrence-state rules instantiate transport and same-row type substitution.The Rm,q rigidity lemmas verify rectangular isolation for the main-suffix interface.Source: B Abstract transport–substitution… · p. 42
  • The MCFG incidence-connectivity theorem is exact for the semantic-unary layer, but positive-rank witnesses and the sample-dependent rank cap remain additional structure.The spanning-tree exposure theorem extends locally to rectangularly isolated interfaces of every arity; proving isolation from alternative composition routes remains formalism-specific.Source: B Abstract transport–substitution… · p. 42

C Positive residual cores and residual sections

Positive residual cores give a lower bound on characteristic-data cost, while equality requires a coherent residual section in the hypothesis. For the rigid-wrapper family, minimum samples built from rigidity words and fiber spanning trees admit such a section.

C Positive residual cores and residual sections

  • Every forcing witness for an L-complete positive residual diagram is characteristic, giving a lower bound on characteristic-data cost.The positive-core formalism separates this unconditional lower bound from the additional section condition needed for equality.Source: C Positive residual cores and residual… · p. 43
  • A minimum characteristic sample has the positive-core cost when an L-complete residual diagram has a residual section in its hypothesis.A residual section assigns hypothesis states to residual classes and simulates diagram transitions with the same concrete template, allowing unit-rule paths.Source: C Positive residual cores and residual… · pp. 43–44
  • For every safe observer of Rm,q, all rigidity words plus one spanning tree per h-fiber form a minimum characteristic sample admitting an Rm,q-complete residual section.The section condition yields equality between the diagram’s forcing cost and characteristic-data cost.Source: C Positive residual cores and residual… · pp. 44–45

D.1 The unary mobility quotient

  • Unary mobility components permit derivations in both directions using semantic unary rules only, making concrete representatives interchangeable within a component.The section distinguishes this graph-based unary mobility from the MCFG’s higher-rank witness layer.Source: §D.1 · p. 45, D Unary mobility quotients and witness… · p. 45

D.2 The quotient witness multihypergraph

The quotient witness multihypergraph records ordered, template-labelled composition witnesses after unary mobility is contracted, and its local realization certifies coherent generator simulation. Higher-rank reconstruction therefore combines mobility with witness obligations rather than reducing to one hypergraph spanning-tree problem.

D.2 The quotient witness multihypergraph

  • The witness multihypergraph preserves child order, child arities, and concrete template labels, so it is not an ordinary hypergraph.It is the finite generator-level shadow of the learner’s derivation multicategory after semantic-unary mobility is contracted.Source: §D.2 · p. 46
  • A local quotient-hypergraph realization lets one fix a single representative per target state and coherently simulate every target generator.Unary mobility transports the chosen representatives to witness endpoints, while the observed witness rule preserves the concrete template and yield.Source: §D.2 · p. 46

D.3 Why higher rank gives two layers rather than a hypergraph tree

  • Under disjoint sample supports and witness obligations determined by unary components, connected-witness-cover cost decomposes into mobility cost plus witness cost.For rectangular mobility blocks with additive edge weights, the mobility term is the sum of minimum-spanning-tree costs; shared samples can instead pay for both layers.Source: §D.3 · pp. 47–48

D.4 Connection with positive residual cores

  • Positive reconstruction is characterized as mobility quotient plus witness multihypergraph plus soundness; MCFG composition witnesses retain the rank and sample-bounded branching structure.For CFG rectangular interfaces, the witness layer collapses to local binary factorizations, leaving a graphic exposure problem.Source: §D.4 · p. 48

E Detailed low-rank exchange classification

The classification separates single-slot exchange locking from arithmetic and derivational tests: connected exchange paths can certify characteristicity, but unimodularity alone first fails at binary rank four. Minimum exchange-based locking samples also have a spanning-tree structure that forces unimodularity.

E Detailed low-rank exchange classification

  • A connected single-slot exchange graph with full coordinate projections certifies characteristicity by enabling independent unary moves across child positions.Exchange paths connect index values within each slot; a sampled composition witness then yields every target word.Source: E Detailed low-rank exchange… · pp. 48–49
  • Every spanning tree of a minimum exchange-locking sample has exactly k −1 edges of each slot label, making its sample-difference lattice the full root lattice.The projected edges form a spanning tree on [k] for each slot, and their root differences form a Z-basis.Source: E Detailed low-rank exchange… · p. 49

Their multisets of pairwise Hamming distances are respectively

F Detailed critical-matching analysis

This section analyzes how the critical matching in mixed rank-four shapes determines ordered locking, using occurrence-level rigidity and laminar derivations to distinguish crossing orders from separated and nested orders. It also identifies crossing-graph structure as a possible higher-rank invariant, not an established criterion.

F Detailed critical-matching analysis

  • Both mixed shapes have the same intrinsic critical perfect matching, whose stabilizer is D4; its three cosets each represent eight slot orders.The three cosets correspond to crossing, separated, and nested physical matchings.Source: F Detailed critical-matching analysis · pp. 51–52
  • Root unary rules precede composition, noncompleted slots remain rigid, and crossing completed slot pairs cannot have disjoint fan-out-two supports.These occurrence-level constraints prevent child changes from enabling ancestor unary moves and rule out a disjoint-child composition in the crossing case.Source: F Detailed critical-matching analysis · pp. 51, 54
  • The unique nonlocking order type is crossing; separated and nested matching types both lock for each mixed cube shape.The critical-matching factorization compresses the 24 slot orders to the three matching types.Source: F Detailed critical-matching analysis · p. 53

Then every full word generated by the laminar trace system satisfies

  • For crossing placements, Horn protection restricts generated words to x0 ≤ x1 or x1 ≤ x2, and collateral switches generate every word within the corresponding region.The analytic argument uses root-unary ordering and disjoint-child constraints; it applies to all eight orders in D4.Source: Then every full word generated by the… · pp. 55–56
  • For either mixed sample, every noncrossing order generates all 16 binary words through explicit laminar derivations, without exhaustive trace evaluation.Separated orders use two saturated disjoint pair traces; nested orders combine an inner pair trace with a switchable single-slot child.Source: Then every full word generated by the… · p. 57
  • Crossing placements reach exactly 12 of 16 cube vertices and are nonlocking, while both noncrossing matching types reach all 16.This makes the mixed-shape crossing/noncrossing classification analytic; the rank-four audit remains an independent census certificate.Source: Then every full word generated by the… · pp. 57–58
  • Crossing schedules preserve a protected Horn implication by induction on laminar derivations, whereas separated and nested schedules constructively generate the full cube.In the crossing case, the reachable set is exactly the corresponding Horn half-cube; noncrossing derivations remove that barrier.Source: Then every full word generated by the… · pp. 57–58
  • The proposed higher-rank crossing graph may not yield a one-bit locking test, since nested exchanges, shared endpoints, and higher-arity witnesses can create non-matroidal dependencies.Whether bounded crossing-graph structure gives tractable sufficient or exact criteria remains an open problem in the passage.Source: Then every full word generated by the… · p. 58

G Hierarchical certificate details

G.1 A fan-out–hierarchy profile for the mixed rank-four shapes

For mixed rank-four shapes, the section studies how hierarchical derivations and Cartesian certificates trade fan-out against parent anchors when assembling exposed freedoms. With the natural critical-module library fixed, it gives exact width–anchor frontiers for separated, nested, and crossing orders.

G.1 A fan-out–hierarchy profile for the mixed rank-four shapes

  • Separated, nested, and crossing orders have flat/reachability fan-outs (2, 2), (3, 2), and (4, 4), respectively; only nested gains one.The nested case reuses exposed parent configurations to achieve reachability at fan-out two despite a flat demand of three; crossing remains unreachable below fan-out four. Fan-out above two is an auxiliary scheduling relaxation, not a claim about a larger MCFG language class.Source: §G.1 · pp. 60–61

G.2 Module-relative hierarchy dividends

  • For the two critical-pair modules, the flat/hierarchical thresholds are (2, 2), (3, 2), and (4, 4) across separated, nested, and crossing orders, yielding dividends 0, 1, and 0.The designated module freedoms form the full four-coordinate cube, making the nested one-unit dividend an intrinsic module-relative result, not merely a comparison of selected derivations. Flat realization requires fan-out at least the blocks’ block-cover number, with equality when the module fillings and parent witness are available.Source: §G.2 · p. 62

G.3 Hierarchical Cartesian certificate trees

  • Cartesian certificate trees provide a sufficient witness for hierarchical assembly: a start cover of width f places its target set in reachability at fan-out f, and added depth or branches do not add local fan-out costs.Product nodes combine child freedoms under one composition witness, while the start cover allows different sampled parent anchors to cover different boxes. Each product node’s width is at least the block-cover number of its child blocks; run-hull placement attains that bound when the required local fillings are available.Source: §G.3 · p. 64
  • The reported (fhier, ctw_K(Q), fmod) widths are separated (2, 2, 2), nested (2, 2, 3), and crossing (4, 4, 4); the nested hierarchy replaces a flat width-three node with width-two branches.For K10 or K13 with Q = {0, 1}^4, the two-branch nested construction saves one unit of fan-out.Source: §G.3 · p. 65

G.4 Exact width–anchor Pareto profiles for critical-module assembly

  • The exact critical-module frontiers are separated {(2, 1)}, nested {(2, 2), (3, 1)}, and crossing {(4, 1)}.Here the coordinates are width and cover-branch count; in these mixed constructions, branches are rooted at distinct sampled full-parent configurations.Source: §G.4 · p. 67
  • For the nested order, lowering width from three to two requires a second branch: the width-two modules leave the outer selector coordinate fixed in each branch.The full cube contains both selector values, so one width-two branch cannot cover it; the exact alternatives are (3, 1) and (2, 2).Source: §G.4 · p. 67
  • The exact Pareto claim is restricted to assembly from the named critical-module library, not the unrestricted certificate language, which permits additional atomic facts.The unrestricted semantic threshold remains fhier.Source: §G.3 · p. 65, §G.4 · p. 67

H.1 Complete rank-four binary census

The complete rank-four census finds 2,096 characteristic samples among 4,368 minimum-size samples; unimodularity and learner locking are distinct, with some outcomes depending on slot order.

H.1 Complete rank-four binary census

  • 2,672 samples are unimodular and form 13 affine-shape orbits; exact determinant enumeration and trace checks audit learner behavior.Coordinate permutations classify affine shapes but need separate order checks because they may change which supports are unions of at most two intervals.Source: §H.1 · pp. 68–69
  • 4,368 minimum-size samples comprise 1,696 nonunimodular, 576 unimodular but nonlocking, and 2,096 characteristic samples.Unimodularity removes 1,696 candidates, while the ordered laminar-trace obstruction removes a further 576.Source: §H.1 · p. 68
  • Rows 10 and 13 split by dihedral slot order: row 10 has 256 locking versus 128 nonlocking labelled samples, and row 13 has 128 versus 64.For both mixed shapes, the nonlocking orders are precisely the displayed dihedral subgroup.Source: §H.1 · p. 69
  • 400 characteristic samples have connected single-slot exchange graphs; the other 1,696 lock only through higher-arity laminar trace operations.The graphic criterion certifies 25/131 of minimum locking samples, while 106/131 lie beyond it.Source: §H.1 · p. 69
  • The same unimodular cube shape can lock or fail depending on coordinate order, which the lattice invariant forgets.Independent bit flips preserve learner behavior, whereas arbitrary coordinate permutations need not.Source: §H.1 · pp. 68, 70

I.1 Minimum characteristic bases are not matroidal

In the fan-out-two rank-four family, minimum characteristic samples do not form a matroid’s bases. The failure is witnessed by two characteristic five-point samples that violate basis exchange.

I.1 Minimum characteristic bases are not matroidal

  • B2,4 is not the set of bases of a matroid: B− and B+ are characteristic, but no eligible exchange element satisfies basis exchange.Both samples have minimum cardinality five.Source: §I.1 · p. 70
  • For each candidate exchange, the sample-difference lattice has index greater than one, with determinant 2 or 3 according to the exchanged vertex’s Hamming weight.The determinant is 2 when wt(f) = 3 and 3 when wt(f) = 4; neither resulting sample is characteristic.Source: §I.1 · p. 70
  • Unlike CFG rectangular exposures, which are spanning-tree bases of a graphic matroid, rank-four MCFG locking requires the laminar trace reachability system.The failure persists for learner-relative minimum locking samples, not merely for a particular sufficient graph.Source: §I.1 · p. 71
Loading 2609.34560v1…