PaperlayerView exact revision on arXiv

Source-linked AI summary

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation

Takayuki Kuriyama

arXiv:2609.03643v1cs.FLcs.LG

TL;DR

The paper asks how exact factorization and canonical presentation behave under fixed finite-monoid observation. It separates unique factorization from finite direct presentation, introduces finite-state compression and PTLD, and shows that finite-state presentation strictly extends finite direct presentation. The paper also gives canonical structural-learning results, with limits on what can be claimed for general reconstruction.

  • Problem

    The paper studies when relative syntactic classes admit exact prime factorization and finite canonical grammar presentation, since unique factorization and finite direct presentation can come apart.

    Source: §1 · p. 2

  • Method

    It develops exact relative prime factorization, finite-state residual controllers for valid-rule languages, and prime-target left-division determinism.

    Source: §7 · p. 9, §10.3 · p. 22, §18 · p. 44

  • Results

    The wrapped nonregular context-free language has an infinite relative quotient and finite prime spectrum despite the failure of FRP, while the 36-element witness has unique exact factorization but infinitely many valid prime returns.

    Source: §1 · p. 2, §18 · p. 44

  • Takeaways & Limitations

    FRP is strictly contained in FSRP, distinguishing finite direct rule lists from finite-state presentation of canonical valid-rule families.

    Source: §18 · p. 44

    The CFG-valued FSRP reconstruction is a computable limit result, not a polynomial-time claim, and its target-controller state bound is not assumed known.

    Source: §15.10 · p. 42

Abstract

from arXiv · show

Let $L\subseteq\Sigma^*$ and fix a morphism $h:\Sigma^*\to M$ into a finite monoid. We study exact factorization and canonical presentation in the relative syntactic congruence $\theta_{L,h}:=\equiv_L\cap\ker h$. We separate unique factorization from finite direct presentation. An exhaustively computer-checked $36$-element quotient has a unique exact prime factorization for every live non-unit class, yet its valid prime-return rules contain an infinite family, so unique factorization does not imply the finite relative presentation property (FRP), even for a finite quotient. We lift the same defect to a nonregular context-free language with an infinite relative quotient and finite prime spectrum. To isolate the obstruction, we introduce the finite-state relative presentation property (FSRP), in which canonical valid right-hand-side languages are represented by finite residual controllers, and prove $\mathrm{FRP}\subsetneq\mathrm{FSRP}$. We then introduce prime-target left-division determinism (PTLD), which implies unique exact factorization, tail exactness, tail determinism, and a quadratic bound on valid rules. A nonregular deterministic context-free example with a finite group observer satisfies PTLD while lying outside every fixed $(k,\ell)$-substitutable class. Finally, for fixed $h$ we give a strong positive-data learner for the canonical PTLD presentation with polynomial-time hypothesis updates and a finite characteristic sample, together with a limit reconstruction of the canonical FSRP controller from weakly behaviorally correct CFG-valued learners.

1 Introduction

The paper asks how fixed finite-monoid observation changes exact factorization and canonical presentation in the relative syntactic congruence. It separates unique factorization from finite direct presentation, showing that under-saturated valid rules can require finite-state compression.

1 Introduction

  • A 36-element quotient has unique exact prime factorization for all 35 live non-unit classes yet infinitely many valid rules; a wrapped nonregular context-free language extends the separation to an infinite quotient.The paper establishes FRP ⊊ FSRP, so finite-state presentation can retain valid-rule families that lack a finite direct list.Source: §1 · pp. 2–3
  • Under-saturated tails in one semantic residual class account for failures of finite direct presentation, while finite residual controllers represent the resulting infinite rule families.The framework distinguishes exact prime factorization, quotient-level valid returns, and finite-state presentability.Source: §1 · pp. 2–3
  • PTLD implies unique factorization, valid-tail exactness and determinism, and a quadratic direct-rule bound, yet a PTLD language can lie outside every finite k, ℓ-substitutable class.The paper also gives an example showing PTLD is not necessary for unique factorization.Source: §1 · p. 3, §2 · p. 4
  • The fixed-h PTLD branch supports strong reconstruction with polynomial-time updates and finite characteristic data; FSRP supports computable limit reconstruction from weakly behaviorally correct CFG-valued learners.Polynomial characteristic data are established on the lexically anchored PTLD subbranch; arbitrary compact CFG size does not polynomially control canonical thickness.Source: §1 · p. 3

2 Related work and positioning

  • The paper’s claimed novelty is relative factorization, PTLD, the FRP/FSRP hierarchy, and under-saturation theory—not fixed-h substitutability or residual automata themselves.FSRP applies canonical residual controllers to structurally determined valid right-hand-side languages.Source: §2 · pp. 4–5

3 Relative syntactic classes

  • For h-substitutable languages, same-type words sharing an accepting context have equal full syntactic distributions; the relative congruence additionally requires equal h-values.The fixed finite-monoid observation compares words only when their observer types agree.Source: §1 · p. 2, §3 · p. 5

3.1 Setwise product versus quotient product

  • Exact setwise products contain concatenations of representatives, while quotient products return a relative class; relative primality uses the former and correct productions use the latter.These products need not be equal.Source: §3.1 · p. 6

4 Relative primes and exact decomposition

Every live non-unit relative class admits an exact prime decomposition, with shortest-word length constraining its possible decompositions. The paper then defines canonical valid rules and relates their finiteness to finite grammar presentation.

4 Relative primes and exact decomposition

  • Every live non-unit relative class is an exact setwise product of primes; shortest-word geometry bounds factorization length and yields finitely many prime-labelled cut candidates.For a class with shortest-word length ℓ(X), the cited finite-candidate principle gives at most 2ℓ(X)−1 cut candidates.Source: §4 · p. 6

5 Correct, pleonastic, and valid productions

  • A correct production returns to its prime class in the quotient, while validity excludes right-hand sides containing a proper prime-valued contiguous block.Correct productions reduce to valid ones, without requiring unique prime factorization.Source: §5 · p. 7

5.1 Structural minimality of valid rules

  • The set of all valid productions is the least structurally complete correct system, and the global valid right-hand-side language is factor-free.A valid right-hand side cannot be a proper contiguous factor of another valid right-hand side.Source: §5.1 · p. 7

6 Canonical generation from a finite direct basis

  • FRP requires finitely many primes and valid rules; under FRP, the canonical prime grammar generates each prime class and its start rules generate exactly L.The finite-presentation criterion is equivalent to bounded validity radius when the prime set is finite.Source: §6 · p. 8

6.1 The role of fixed-h substitutability

  • For h-substitutable L, each nonempty observer fiber L_m is one relative class, so the number of accepting relative classes is at most |M|.In the fixed-h theorem, substitutability supplies the finite bound on accepting classes.Source: §6.1 · p. 8

7 Semantic residuals, prime-target division, and Clark rigidity

The section replaces cancellation-based rigidity with semantic residuals and prime-target left-division determinism. Under h-substitutability and unit separation, PTLD yields unique exact prime factorization and stronger control of valid prime rules.

Semantic residuals

  • Each observer-type slice of a semantic residual is empty or one relative class, so the residual set has at most |M| classes.For a = h(A) and p = h(P), the sharper bound is the number of live observer types m satisfying am = p.Source: §7 · p. 9

Prime quotient rigidity

  • PTLD collapses remainders inside a prime and makes every nonempty prime left quotient a single relative class, yielding prime prefix-freeness.The quotient is the unit class exactly when the dividing word itself belongs to the prime.Source: §7 · p. 10

Clark rigidity

  • Any prime-irreducible prime sequence contained in a class with an exact prime factorization must equal that factorization term by term.Consequently, exact prime factorizations are irreducible, and every live non-unit class has a unique one under the stated assumptions.Source: §7 · pp. 11–12

Prime-target division and consequences

  • PTLD gives every live non-unit relative class a unique exact factorization into relative primes, and with finite prime spectrum bounds valid rules by q^2.PTLD requires unique right division when the observer target is a relative prime; it is weaker than factor-left-cancellation.Source: §7 · pp. 9, 12

Valid-tail control

  • Under PTLD, valid production tails are exact, and a finite prime spectrum makes each left-hand-prime/first-right-prime pair determine at most one valid rule.With q relative primes, the number of valid rules is at most q^2.Source: §7 · p. 12

Path and grammar consequences

  • In the prime-interval DAG for a word, every minimum-edge path reads the class's unique exact prime factorization.The direct valid-rule grammar also derives every contained prime sequence from that exact factorization.Source: §7 · pp. 12–13

8 Bounded-defect localization

Bounded concatenation defect localizes unbounded variation in a class's prime factorization: under the stated neutrality-or-positivity condition, exactly one factor carries it.

Single-carrier localization

  • A class with minimum defect 1 and unbounded defect spectrum has exactly one positive prime in every exact factorization, and that prime has unbounded spectrum.The result assumes every relative prime is neutral or positive and the statistic has bounded concatenation defect.Source: §8 · p. 13

Bounded-defect statistic

  • Counting occurrences of a fixed word z gives a bounded-defect statistic with defect at most |z|−1.For z = ba, the bound is 1.Source: §8 · p. 13

9 The nonregular example L0 = {anbn : n ≥0}∗

The nonregular language L0 provides an analytic example with a finite observer: its relative classes have explicit normal forms and seven primes, and every live non-unit class has unique exact factorization without cancellation. Its direct grammar has 34 valid productions, yet valid-rule determinism fails.

9 The nonregular example L0 = {anbn : n ≥0}∗

  • The finite first/last/ba morphism makes L0 h-substitutable and unit-separated, and the section proves its claims analytically rather than by finite computation.L0 is defined as {a^n b^n : n ≥ 0}*; its word characterization uses nonnegative prefix balance, total balance zero, and ba events at height zero.Source: §9 · pp. 13–14

9.1 Complete normal forms for live relative classes

  • Live relative classes are classified by four families for factors containing ba, alongside pure powers and mixed a^i b^j classes indexed by balance.For the ba-containing families, the internal ba events share a relative height and total balance provides a class parameter.Source: §9.1 · p. 15

9.2 Seven primes and exact fringe identities

  • The live relative prime spectrum of L0 is exactly {A, B, C, D, E, F, G}.A, B, and C are neutral; D, E, F, and G have positive unbounded ba-count spectra.Source: §9.2 · p. 16, §9.3 · p. 16

9.3 Unique factorization without cancellation

  • Every live non-unit relative class of L0 has a unique exact prime factorization, although its observer monoid is not factor-cancellative.The first/last/ba observation assigns the same type to a and aa, showing cancellation fails while unique factorization holds.Source: §9.3 · p. 17

9.4 The thirty-four valid productions

  • L0 has seven relative primes and 34 valid productions, with maximum right-hand-side length 3; all valid productions are tail-saturated, but VTD fails.The rules D → BA and D → BF share the same left-hand prime and first right-hand prime but have different tails.Source: §9.4 · pp. 18–19

10 Finite-state relative presentation

FSRP allows each canonical valid-rule language to be regular even when its rules are infinite, so FRP is strictly stronger. For finite relative quotients, prime-avoidance automata decide FRP, while residual languages provide canonical finite-state controllers that compile into CFGs.

10.1 Definition and finite-quotient regularity

  • FSRP requires a finite prime spectrum and regular valid right-hand-side languages; FRP implies FSRP, but the converse fails.A finite relative quotient always gives FSRP; the paper’s 36-element example separates it from FRP.Source: §10.1 · p. 19
  • Under context-free, h-substitutable, finite-prime hypotheses, correct-return and pleonastic languages are context-free, but regularity of their factor-minimal differences remains unresolved.The proposition alone gives no regularity conclusion because context-free languages are not closed under difference.Source: §10.1 · p. 20

10.2 Prime-avoidance automata for finite quotients

  • For a finite quotient, a prime-avoidance automaton recognizes valid right-hand sides by tracking quotient products and rejecting prime-valued proper intervals.A prime word is valid when its internal symbols follow safe transitions and its last symbol follows a final edge.Source: §10.2 · p. 21
  • FRP holds exactly when the productive safe-transition graph is acyclic; with a multiplication table and prime classes, this makes FRP decidable and the validity radius computable.A productive cycle yields arbitrarily long valid words and a pumping certificate uv^n w.Source: §10.2 · p. 21

10.3 Canonical residual controller

  • The nonempty left quotients of the valid languages form the canonical minimal deterministic partial multi-start controller, with residual languages themselves as states.Adding one dead state gives the complete controller; presentation-state complexity counts the nonempty residuals.Source: §10.3 · pp. 21–22

10.4 Compilation to an ordinary finite CFG

  • Under unit separation, finitely many accepting classes, finite prime spectrum, and FSRP, the residual-controller construction yields a finite CFG for the canonical presentation.Each controller chain expands a direct valid production uniquely, and contracting such chains bijects controller parse trees with direct prime-skeleton parse trees.Source: §10.4 · p. 22
  • The controller is a finite-state subdivision of the same intrinsic prime branching structure, not merely a compression of the generated language.This preserves the direct grammar’s prime-skeleton parse structure.Source: §10.4 · p. 22

11 Tail saturation and presentation-defect complexity

Valid rules split into saturated tails, which have a finite bound, and under-saturated tails, which capture the remaining presentation defect. Under finite-prime hypotheses, FRP failure localizes to an unbounded family associated with one residual class.

Tail saturation and presentation-defect complexity

  • A valid rule P → Aα is tail-saturated when α equals its relative class, and under-saturated otherwise; VTE1 holds exactly when every UnsatP is empty.Every binary valid rule is automatically saturated.Source: §11 · p. 23
  • With h-substitutability and q finite primes, saturated valid rules are finite, with |Vsat| ≤ q^2 rres(L, h) mex(L, h).The bound counts residual classes for each prime pair and exact decompositions of each residual class.Source: §11 · p. 23
  • The presentation defect separates into under-saturation radius and defect residual complexity, and finite under-saturation radius is equivalent to finite boundary radius.Over a finite prime alphabet, finiteness is equivalent to bounded word length.Source: §11 · p. 23
  • With finite prime spectrum and h-substitutability, FRP failure yields infinitely many distinct valid rules P → Aαn for fixed P, A, and residual class R, with αn ⊊ R and unbounded lengths along a subsequence.This localizes the failure to under-saturated tails.Source: §11 · pp. 23–24
  • When FSRP holds but FRP fails, some UnsatP is an infinite regular language, giving a pumped family uv^n w; finite quotients refine this to an automaton-lasso certificate.Under PTLD and finite prime spectrum, the cited profile coordinates rres and mex are at most one, while ρ∂ and κ∂ are zero.Source: §11 · p. 24

12 Unique factorization without finite direct presentation: a 36-element quotient witness

The 36-element relative quotient has unique exact prime factorization for every live non-unit class, yet an infinite family of valid rules prevents FRP. The witness isolates the presentation defect in the finite observer and is quotient-minimal among its proper quotients.

12 Unique factorization without finite direct presentation: a 36-element quotient witness

  • The target language L = {a, b}+ makes all nonempty words syntactically congruent, isolating the obstruction in the finite observer quotient.The identity class has no nonempty preimage, and the 35 nonidentity classes are the live non-unit relative classes.Source: §12 · p. 24
  • For the 36-element witness, the relative prime spectrum has fifteen elements, and each of the thirty-five live non-unit relative classes has a unique exact relative prime factorization.Exhaustive regular-language equality testing leaves exactly one candidate for each of those classes, and a reproducible verifier checks the remaining finite counts and quotient-minimality assertions.Source: §12 · pp. 24–25
  • For four prime classes, αβ = t, αqβ = t, and αq^2β = t, so αq^mβ = t for every m ≥ 0.The proper intervals have quotient values from only three forms, all exact composites, making every rule in the family non-pleonastic.Source: §12 · p. 25
  • The infinite valid family proves that unique exact factorization does not imply FRP, even with a finite relative quotient and finite prime spectrum.In the same witness, the valid tails under-saturate their class at every m ≥ 1, while exact-factor ambiguity is zero.Source: §12 · pp. 25–26
  • Every proper congruence quotient of M36 has FRP, so this 36-element witness is quotient-minimal, not proven absolutely minimal among finite monoids.The exhaustive audit finds twenty monoid congruences in total.Source: §12 · p. 26

13 A coupled nonregular FSRP–FRP separation

The wrapped context-free language has an infinite relative quotient and 52 primes, while retaining global exact unique factorization and FSRP but not FRP. Its wrapper structure couples to the defective finite middle subsystem, preserving the infinite valid-rule family.

13 A coupled nonregular FSRP–FRP separation

  • Lwrap = {c^nwd^n : n ≥ 0, w ∈ {a, b}+} is context-free and has an infinite relative quotient.Its live relative classes are distinguished by wrapper counts, middle type, or the difference between left and right wrapper exponents.Source: §13 · pp. 26, 27, 29
  • On nonempty middle words, the relative congruence is exactly equality under h36, preserving the finite witness’s middle primes and valid prime sequences.The middle subsystem therefore retains the defective valid-rule family from the finite quotient witness.Source: §13 · p. 27
  • The wrapped pair has exactly 52 relative primes and every live non-unit class has a unique exact prime factorization.The prime spectrum consists of C, D, middle primes, and wrapped classes Ws.Source: §13 · pp. 27–28
  • The wrapped pair satisfies FSRP but not FRP, despite its infinite quotient, finite prime spectrum, and global exact unique factorization.Its middle-prime valid-return languages match those of the 36-element witness; valid rules also retain strict under-saturation.Source: §13 · p. 29
  • For each nonidentity s, the valid language for Ws consists of CαD sequences with α drawn from a regular middle language, so all valid languages are regular.The middle language excludes strings containing a prime-valued correct middle interval.Source: §13 · pp. 28–29
  • The construction couples the wrapper primes to finite-state middle irreducibles, rather than treating the nonregular wrapper and defective middle system as disjoint components.The new wrapped primes Ws use middle valid sequences between C and D.Source: §13 · p. 29

14 Disjoint-alphabet sums as an ambient comparison

For fixed-observation pairs over disjoint alphabets, the sum preserves componentwise substitutability and unit separation, with live classes, primes, and presentation properties inherited from the components. The construction also gives an ambient nonregular example separating UF, FSRP, and FRP, while a wrapped example couples the defect in one system.

14 Disjoint-alphabet sums as an ambient comparison

  • The disjoint-alphabet sum preserves h-substitutability and unit separation, and its live relative classes and primes are the unions of those of its components.Mixed-alphabet words are dead, and the relative congruence on each component alphabet remains unchanged.Source: §14 · p. 30
  • UF, FRP, and FSRP hold for the sum exactly when they hold for both components.Exact factorization and valid prime-return languages separate componentwise.Source: §14 · p. 30
  • The disjoint sum of L0 and the finite witness is a nonregular context-free UF+FSRP but not FRP example, with nonregularity and the presentation defect in separate components.The wrapped example instead places its infinite quotient and defective return dynamics in one coupled relative-prime system.Source: §14 · p. 30

15 Strong structural reconstruction from positive data

The section studies strong structural reconstruction from positive data for two targets: a canonical direct relative-prime grammar under PTLD and a finite-state residual controller under FSRP. For fixed h, it gives a positive-data learner with polynomial-time hypothesis updates for the PTLD subclass and a limit-canonicalization result for FSRP from a weakly behaviorally correct CFG learner; it also identifies a polynomial-data PTLD branch and a nonregular example beyond every finite k, ℓ-substitutable class.

15.1 The canonical PTLD target

  • Under h-substitutability, unit separation, finite prime spectrum, and PTLD, the canonical grammar is trim, has |V| ≤ q^2, and each prime has a live context of length at most qτ.Source: §15.1 · p. 31

15.2 An h-guarded substring learner

  • The h-guarded substring grammar is sound: it generates only words in L, so it may undergenerate before characteristic data arrive but never overgenerates.Source: §15.2 · p. 32

15.3 Finite signatures and exact observed relative classes

  • Equal finite signatures never merge distinct relative classes, and once the weak grammar generates L, signatures exactly recover the relative partition on observed substrings.Source: §15.3 · p. 32

15.4 Finite certificates for relative primality

  • Finite prime cut-separation witnesses certify the true primes when the observed relative partition is exact, and PTLD identifies the cut-separation radius with prime-prefix escape.Source: §15.4 · p. 33

15.5 Polynomial recovery of exact factors and valid rules

  • Once the observed partition and prime set are correct, the triple procedure recovers all and only sample-witnessed valid productions, and recovers every valid rule when its canonical witness is sampled.Source: §15.5 · p. 34

15.6 Characteristic sample

  • A finite characteristic sample makes the guarded weak grammar complete, and for fixed h and alphabet its total data size is polynomial in q, τ, and ηcut(L, h).Source: §15.6 · pp. 34–35

15.7 Relative-ASGOLD

  • Relative-ASGOLD strongly identifies the canonical direct relative-prime grammar from positive strings, with polynomial-time hypothesis updates and an explicit finite characteristic sample.The sample has cardinality at most q^2 + qτ + |Σ| + |M|.Source: §15.7 · p. 36
  • Each Relative-ASGOLD hypothesis update takes polynomial time in N, using polynomially many CFG-membership tests, interval tests, class tests, and rule checks.The rule stage examines at most O(N^6) triples, and the characteristic-sample bounds are established separately.Source: §15.7 · p. 36

15.8 A polynomial-data PTLD subbranch and the thickness obstruction

  • On the unit-separated, h-substitutable, lexically anchored PTLD branch with finite prime spectrum, Relative-ASGOLD has polynomial update time and polynomial characteristic data in canonical grammar size.Every prime contains a terminal letter, eliminating nontrivial cuts of canonical prime words.Source: §15.8 · p. 37
  • Canonical PTLD thickness can be 2^n despite an O(n)-size CFG, so no polynomial bound transfers canonical thickness from arbitrary compact generating CFGs.The family has q = 1 and ηcut = 0; the obstruction limits polynomial-data guarantees stated in terms of canonical grammar size.Source: §15.8 · p. 37

15.9 A PTLD language beyond every finite k, ℓ-substitutable class

  • For every finite k, ℓ, the nonregular deterministic context-free PTLD example L⋆ is not k, ℓ-substitutable, yet has a finite relative prime spectrum of size five.Its C2 × C2 group observer ensures PTLD, and its five primes are lexically anchored, placing it in the branch with polynomial update time and polynomial characteristic data in canonical grammar size.Source: §15.9 · pp. 38–40

15.10 Finite-state strong reconstruction beyond FRP

  • Under unit separation, finite relative prime spectrum, and FSRP, a weakly behaviorally correct CFG learner can be lifted to strong Gold identification of the canonical finite-state relative-prime presentation.The reconstruction stabilizes prime hypotheses, validity controllers, lexical and start components, and the fixed canonical CFG compilation; it is a computable limit result, not a polynomial-time claim.Source: §15.10 · pp. 40, 42

16 Current hierarchy and separations

The hierarchy distinguishes exact factorization, finite direct presentation, and finite-state presentation, with assumptions attached to the stated implications. Its examples establish that UF and FRP are incomparable, while PTLD and FSRP support different strong-reconstruction results.

Current hierarchy and separations

  • UF and FRP are incomparable: a finite quotient has UF without FRP, while a separate finite witness has FRP without UF.The diagram’s implications involving FRP and the quadratic rule bound additionally assume a finite relative prime spectrum.Source: §16 · p. 42
  • PTLD is sufficient but not necessary for direct presentation: L0 lacks PTLD yet has FRP, while L⋆ satisfies PTLD and FRP.A separate PTLD example is a nonregular deterministic context-free language outside every finite k, ℓ-substitutable class.Source: §16 · p. 42
  • The profile separates prime spectrum, residual splitting, exact-factor multiplicity, and under-saturation complexity, including the sharp combination of unique exact factorization with unbounded under-saturation complexity.The latter is stated as mex = 1 with ρ∂ = ∞.Source: §16 · p. 43
  • The PTLD branch supports canonical strong reconstruction with polynomial-time updates and an explicit finite characteristic sample; the broader FSRP branch supports computable controller reconstruction from weakly behaviorally correct CFG learners.The PTLD reconstruction’s remaining quantitative parameter is prime-prefix escape; the broader controller reconstruction is not stated as polynomial-time.Source: §16 · p. 43

17 Open problems and next steps

The open problems ask how far the UF–FRP separation can be minimized, whether context-free finite-prime examples can fail FSRP, and what conditions enable efficient learning beyond PTLD. They also identify representation-size and multidimensional extensions as unresolved directions.

17 Open problems and next steps

  • The 36-element witness is quotient-minimal within its monoid, but whether any smaller finite monoid admits a unit-separated h-substitutable UF/non-FRP pair remains open.The computation establishes no absolute lower bound.Source: §17 · p. 43
  • It remains open whether a context-free fixed-h pair with finite relative prime spectrum can fail FSRP, or whether FSRP holds automatically under those hypotheses.A further question asks whether such a counterexample could have context-free but nonregular valid right-hand-side languages; correct-return languages are already context-free, leaving factor-minimalization as the difficulty.Source: §17 · p. 43
  • For FSRP beyond PTLD, the paper asks which weaker semantic conditions could yield an a priori bound or polynomial procedure for recovering the minimal controller.Candidate conditions include bounded residual splitting, bounded exact-factor multiplicity, and a bounded defect-state parameter.Source: §17 · p. 43
  • Whether PTLD prime-prefix escape is polynomially bounded in canonical parameters remains open, although the lexically anchored branch has escape radius zero.The question is equivalent to whether the finitely many false prefix classes exposed by cuts of canonical prime words have polynomial-length escape witnesses.Source: §17 · p. 43
  • The paper asks which restricted CFG subclasses permit polynomial bounds on q, τ, and ηcut in the generating-grammar size, since arbitrary compact CFGs do not.A positive result for a natural linear fixed-h subclass could connect weak polynomial reconstruction bounds to polynomial strong structural learning.Source: §17 · pp. 43–44
  • A multidimensional extension would need analogues of exact relative prime factorization, semantic residual splitting, and under-saturation controllers for multidimensional congruence and bounded-fan-out MCFGs.The paper identifies tuple congruence and non-permuting linear regular functions as a natural compositional substrate.Source: §17 · p. 44

18 Conclusion

The paper separates unique exact factorization from finite direct presentation, with finite and context-free witnesses showing that these are distinct structural axes. It then presents PTLD as a rigid branch with structural and learning consequences, while identifying unresolved boundaries.

18 Conclusion

  • The 36-element witness has globally unique exact factorization but infinitely many valid prime returns, and Lwrap lifts the defect to a nonregular context-free language with infinite relative quotient and finite prime spectrum.Together, the examples distinguish exact-factor ambiguity, quotient infinitude, and direct-rule infinitude; FSRP captures finite-state presentation when a finite direct rule list fails.Source: §18 · p. 44
  • PTLD implies unique exact factorization, valid-tail exactness and determinism, and a quadratic bound on valid rules.The five-prime language L⋆ satisfies PTLD yet lies beyond every finite k, ℓ-substitutable class.Source: §18 · p. 44
  • Relative-ASGOLD reconstructs the canonical direct relative-prime grammar with polynomial-time updates and a finite characteristic sample; the general data-length parameter is prime-prefix escape radius.That radius vanishes on the lexically anchored branch containing L⋆, while the unary doubling family shows arbitrary compact CFGs may hide exponential canonical thickness.Source: §18 · p. 44
  • Open boundaries include context-free fixed-h finite-prime examples with nonregular valid-return languages, polynomial bounds on PTLD prime-prefix escape, and multidimensional or bounded-fan-out extensions.The authors report no known example of the first kind; the broader extensions remain to be developed.Source: §18 · p. 44

Code and data availability

The paper provides a fixed repository snapshot with a verifier and deterministic certificate for the 36-element witness.

Code and data availability

  • The fixed GitHub snapshot contains the theorem-facing verifier verify 36.py and the corresponding deterministic machine-readable certificate certificate 36.json.The verifier uses only the standard library.Source: Code and data availability · p. 44

A Reproducible verification of the 36-element UF–FRP witness

The witness verification is packaged as a deterministic certificate and standard-library-only verifier that reconstructs the finite quotient and checks its theorem-facing properties. The checks cover quotient structure, relative primes and factorizations, the infinite-rule witness, and proper quotients.

A Reproducible verification of the 36-element UF–FRP witness

  • The fixed snapshot supplies a standard-library-only verifier and deterministic certificate for the theorem-facing finite claims in Section 12.The certificate can be regenerated and compared byte-for-byte with the committed file after verification completes.Source: A Reproducible verification of the… · pp. 44–45
  • The verifier reconstructs a 64-element transformation monoid, generates the least monoid congruence, and then independently checks the quotient and witness claims.The generated certificate is compared with the committed certificate using cmp certificate_36.generated.json certificate_36.json.Source: A Reproducible verification of the… · p. 45
  • The quotient has 36 elements, its identity fiber contains only the identity transformation, and all 35 nonidentity classes are reachable by nonempty words.Every quotient element has a shortest representative of length at most eight.Source: A Reproducible verification of the… · p. 45
  • Exact binary fiber-product equality identifies precisely the fifteen relative primes by comparing the target positive fiber with concatenated positive factor fibers.A mismatch state witnesses membership in their symmetric difference.Source: A Reproducible verification of the… · p. 45
  • Each of the 35 live non-unit classes has exactly one surviving prime-labeled exact factorization after the checker rejects 187 of 222 candidates.Lemma 4.2 reduces exact factorization to cuts of shortest representatives; each rejected candidate has a stored shortest counterexample.Source: A Reproducible verification of the… · p. 45
  • The quotient multiplication checks the identities q2 = q3, αq = αq2, qβ = q2β, and αβ = αqβ = αq2β = h(ab).Here q = h(baaa), α = h(a), and β = h(b).Source: A Reproducible verification of the… · p. 45
  • The prime set includes [abaaa], [baaab], and [baaabaaa], and the verifier checks three exact composite identities for them.The verifier also records that H = [baaab] has unique factorization [b][aaab], while P^m q Pb is a strict subset of H for every m ≥ 1.Source: A Reproducible verification of the… · p. 45
  • A productive lasso in the prime-avoidance automaton witnesses infinitely many prime returns, while exhaustive congruence closure checks that every proper quotient has FRP.The audit covers exactly twenty monoid congruences on M36; the verifier keeps the syntactic unit separate from the positive identity fiber when needed.Source: A Reproducible verification of the… · p. 45
Loading 2609.03643v1…