Deck Reconstruction for Restricted Word Classes
Abstract
For a binary word x∈ {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 ℓ 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.
Related
- Analysis of pairs in a generalized deck of playing cards
- Bayesian Deck-of-cards-based Ordinal Regression with Sequential Preference Elicitation
- The first savings in word-representations of hypercubes
- On the word and period growth of some groups of tree automorphisms
- Exact curve counting of given word length on the once-punctured torus
BibTeX
@misc{angal2026deck,
title = {{Deck Reconstruction for Restricted Word Classes}},
author = {Krishna Angal and Ruben Ascoli and Simon X. He and Xiaoyu He and Logan Post and Arker Oke Soe and Olga Zhukova},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41110},
eprint = {2610.41110},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41110},
}
RIS
TY - UNPB
TI - Deck Reconstruction for Restricted Word Classes
AU - Krishna Angal
AU - Ruben Ascoli
AU - Simon X. He
AU - Xiaoyu He
AU - Logan Post
AU - Arker Oke Soe
AU - Olga Zhukova
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41110
UR - https://arxiv.org/abs/2610.41110
AB - For a binary word x∈ {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 ℓ 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.
ER -