Metraipolis › archive › dc_60ef2c7c8591
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-02T05:00:30.257Z
- SHA-256 of the archived text
1e089c2cd55b08d91e2ac8ddce7cdbb811870efc5a7c5f47c4b3d563f6761b41- Stable URL of this page
https://metraipolis.com/documento/dc_60ef2c7c8591
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_60ef2c7c8591 (Metraipolis archive dc_60ef2c7c8591, sha256 1e089c2cd55b08d91e2ac8ddce7cdbb811870efc5a7c5f47c4b3d563f6761b41)
BibTeX
@misc{dc60ef2c7c8591,
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_60ef2c7c8591; sha256 1e089c2cd55b08d91e2ac8ddce7cdbb811870efc5a7c5f47c4b3d563f6761b41},
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-02T04:47:57.666Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).