Metraipolis › archive › dc_c8fdad39f076

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation — arXiv:2609.03643

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.03643
License (as archived)
CC0-1.0
Archived
2026-10-17T02:08:41.284Z
SHA-256 of the archived text
c89fa377ed6ceb4e095f3128b3d850b98b5897f0dfa62d5b61b5e796f318f66a
Stable URL of this page
https://metraipolis.com/documento/dc_c8fdad39f076

How to cite

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation — arXiv:2609.03643 — arXiv (en), https://arxiv.org/abs/2609.03643 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c8fdad39f076 (Metraipolis archive dc_c8fdad39f076, sha256 c89fa377ed6ceb4e095f3128b3d850b98b5897f0dfa62d5b61b5e796f318f66a)
BibTeX
@misc{dcc8fdad39f076,
  title = {Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation — arXiv:2609.03643},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03643},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c8fdad39f076; sha256 c89fa377ed6ceb4e095f3128b3d850b98b5897f0dfa62d5b61b5e796f318f66a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03643. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-04 in cs.LG).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.03643 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T01:47:25.628Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).