Metraipolis › archive › dc_bd8dbe4754ef

Quadratic bounds for uncompletable words and matrix mortality — arXiv:2609.30817

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.30817
License (as archived): CC0-1.0
Archived: 2026-10-08T02:59:23.071Z
SHA-256 of the archived text: 5c5045468a2e1bbb1489b50bf7c2211adc51c8b36efdd12a1fe96de8fa3aac4a
Stable URL of this page: https://metraipolis.com/documento/dc_bd8dbe4754ef

How to cite

Quadratic bounds for uncompletable words and matrix mortality — arXiv:2609.30817 — arXiv (en), https://arxiv.org/abs/2609.30817 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd8dbe4754ef (Metraipolis archive dc_bd8dbe4754ef, sha256 5c5045468a2e1bbb1489b50bf7c2211adc51c8b36efdd12a1fe96de8fa3aac4a)

BibTeX

@misc{dcbd8dbe4754ef,
  title = {Quadratic bounds for uncompletable words and matrix mortality — arXiv:2609.30817},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30817},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd8dbe4754ef; sha256 5c5045468a2e1bbb1489b50bf7c2211adc51c8b36efdd12a1fe96de8fa3aac4a},
  year = {2026}
}

Archived text

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

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.30817 — 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-08T02:28:17.947Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).