Metraipolis › archive › dc_52747bf01019

Width-Bounded Equational Derivations for Finite Graph Expressions — arXiv:2609.08325

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08325
License (as archived)
CC0-1.0
Archived
2026-10-16T15:39:59.432Z
SHA-256 of the archived text
3883c404f72acb86b9a82ac9cf2efdb69b3dbc51fc5af468e4473dba1bd75eb1
Stable URL of this page
https://metraipolis.com/documento/dc_52747bf01019

How to cite

Width-Bounded Equational Derivations for Finite Graph Expressions — arXiv:2609.08325 — arXiv (en), https://arxiv.org/abs/2609.08325 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_52747bf01019 (Metraipolis archive dc_52747bf01019, sha256 3883c404f72acb86b9a82ac9cf2efdb69b3dbc51fc5af468e4473dba1bd75eb1)
BibTeX
@misc{dc52747bf01019,
  title = {Width-Bounded Equational Derivations for Finite Graph Expressions — arXiv:2609.08325},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08325},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_52747bf01019; sha256 3883c404f72acb86b9a82ac9cf2efdb69b3dbc51fc5af468e4473dba1bd75eb1},
  year = {2026}
}

Archived text

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

Completeness of an equational presentation guarantees an equality path but need not control the resources used along it. For finite graph expressions we measure derivational space by the largest input-output interface of an intermediate raw term. For every finite doubly ranked edge alphabet $\Sigma$, we prove that equal closed expressions of pattern width at most $k$ are joined by a derivation in which every step applies an equation in either direction and every intermediate width is at most a computable $B_\Sigma(k)$, independently of graph size. The derivation uses only the structural magmoid laws and the fifteen finite-graphoid schemes. The construction compiles each expression through protected cores and finite routing windows to an encoding-canonical representative $\operatorname{NF}_k$ of width at most $4k+4$. We call this property bounded equational coherence. We also prove $\operatorname{bw}(F)\le\operatorname{patw}(F)\le4(\operatorname{tw}(F)+1)$ whenever the underlying simple graph has at least two edges, separate layered linear from branching expressions on cliques, and provide machine-checkable witnesses and finite invariants for the first five nontrivial clique values.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LO).
Categorie arXiv: Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.08325 — 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-16T15:30:57.136Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).