On a reconstruction problem for sequences
Given a word \(X\) of length \(n\) with terms from an alphabet \(\Sigma\), consider the multiset \(D_k(X)\) of all \(k\)-subwords of \(X\). When is it possible to reconstruct the word \(X\) from the multiset \(D_k(X)\)? The authors prove that any word of length \(n\) is ``\(k\)-reconstructible if \(k\geq\lfloor \frac {16} {7}\sqrt n\rfloor +5\). This improves the known bound \(\lfloor n/2\rfloor\), which is due to \textit{B. Manvel et al.} [Discrete Math. 94, No. 3, 209-219 (1991; Zbl 0746.05045)]. Quite interestingly, the authors prove their improvement by relating the problem to a classical problem of Diophantine analysis, usually referred to as the Prouhet-Tarry-Escott problem, which is about finding two distinct solutions for a certain system of linear Diophantine equations. The improved bound then follows immediately from a bound for the latter problem, recently found by \textit{P. Borwein} and \textit{C. Ingalls} [Enseign. Math. II. Sér. 40, No. 1-2, 3-27 (1994; Zbl 0810.11016)].
- On highly palindromic words
- Combinatorial reconstruction problems
- Reconstructing subsets of \(\mathbb{Z}_n\)
- On a reconstruction problem
- Reconstruction from subsequences.
- Optimal mean-based algorithms for trace reconstruction
- Reconstructing words from subwords in linear time
- Reconstructing trees from traces
- On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length
- Efficient Reconstruction of RC-Equivalent Strings
- Reconstruction of matrices from submatrices
- On Prouhet's solution to the equal powers problem
- A linear algorithm for string reconstruction in the reverse complement equivalence model
- Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words
- On Levenshtein’s Reconstruction Problem Under Insertions, Deletions, and Substitutions
- Reconstructing words from right-bounded-block words
- Relations on words
- Trace reconstruction: generalized and parameterized
- Sequence Reconstruction for Limited-Magnitude Errors
- On the possibility of a periodic word reconstruction from the subwords of fixed length
- Solutions to the multi-dimensional Prouhet-Tarry-Escott problem resulting from composition of balanced morphisms
- Polynomials with multiple roots at 1
- Processes, Terms and Cycles: Steps on the Road to Infinity
- Efficient reconstruction of sequences from their subsequences of supersequences
- On the number of distinct \(k\)-decks: enumeration and bounds
- Reconstructing Words from Right-Bounded-Block Words
- Reconstruction of hypermatrices from subhypermatrices
- A word reconstruction problem for polynomial regular languages
- Improvements on permutation reconstruction from minors
- Reconstructing under group actions.
- Reconstruction of a word from a multiset of its factors
This page was built for publication: On a reconstruction problem for sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1352885)
