Metraipolis › archive › dc_413beaf27185
Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41110
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:18:28.450Z
- SHA-256 of the archived text
ced656909d91f76084a68dac6bc42afe3fbf05d46147cd2e4b30adff4404d450- Stable URL of this page
https://metraipolis.com/documento/dc_413beaf27185
How to cite
Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110 — arXiv (en), https://arxiv.org/abs/2610.41110 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_413beaf27185 (Metraipolis archive dc_413beaf27185, sha256 ced656909d91f76084a68dac6bc42afe3fbf05d46147cd2e4b30adff4404d450)
BibTeX
@misc{dc413beaf27185,
title = {Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41110},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_413beaf27185; sha256 ced656909d91f76084a68dac6bc42afe3fbf05d46147cd2e4b30adff4404d450},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41110. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a binary word $x\in \{0,1\}^+$, the $k$-deck of $x$ is the multiset of all length-$k$ subsequences counted with multiplicity. The deck reconstruction problem asks for the minimum $k$ such that every word of a fixed length is uniquely determined by its $k$-deck. In this paper, we study deck reconstruction for several restricted classes of binary words, including words with exactly $s$ ones, words with at most $\ell$ runs of ones, and words where the indices of ones are given by a monotone polynomial of degree $d$. We prove that for these classes of words, their reconstruction thresholds are bounded by a function of the structural complexity of the class. We also study weak deck reconstruction, in which subwords may contain "wildcard" symbols that map to either 0 or 1. By generalizing a "template lemma" of Dudík and Schulman, we improve the upper bound in an open question about weak reconstruction from Dudík and Schulman. Finally, for the class of periodic words with period $d$, we prove that its in-class reconstruction threshold is equal to the general reconstruction threshold for words of length $d$, and give a general template construction producing further classes with the same threshold-preservation phenomenon.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41110 — 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-11-03T08:05:23.769Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).