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

arXiv:2609.03643v1 Announce Type: cross Abstract: Let LsubseteqSigma^* and fix a morphism h:Sigma^*o M into a finite monoid. We study exact factorization and canonical presentation in the relative syntactic congruence heta_{L,h}:=equiv_Lapker 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 FRPsubsetneqFSRP. 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.

Related

• Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
• Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

Source: arXiv cs.LG | 2026-09-04