Reconstruction of sequences
Every sequence of length \(n\) determines \(n\choose k\) subsequences of length \(k\). The authors investigate the relationship between such subsequences and the original sequence. In particular they consider the problem of reconstructing an \(n\)-sequence from its subsequences of length \(k\) --- an interesting problem apparently first raised by \textit{L. I. Kalashnik} [The reconstruction of a word from fragments, Numerical mathematics and computer technology, Akad. Nauk Ukrain. SSR, Inst. Mat., Preprint IV, 56-57 (1973)]. Among other results, the paper under review contains a proof that for \(n>7\) and \(k\geq[n/2]\) the subsequences uniquely determine the original sequence, and for \(k<\log_ 2 n\) they do not.
- On highly palindromic words
- On a reconstruction problem for sequences
- Reconstructing sequences
- Reconstruction from subsequences.
- Order of weak \(M\)-relation and Parikh matrices
- Optimal mean-based algorithms for trace reconstruction
- On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length
- Phase transition in sequence unique reconstruction
- Independence of certain quantities indicating subword occurrences
- Separability of M-equivalent words by morphisms
- Reconstruction of matrices from submatrices
- scientific article; zbMATH DE number 4174378 (Why is no real title available?)
- Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction
- scientific article; zbMATH DE number 1189007 (Why is no real title available?)
- scientific article; zbMATH DE number 1156634 (Why is no real title available?)
- scientific article; zbMATH DE number 6900644 (Why is no real title available?)
- Reconstruction of Sequences Over Non-Identical Channels
- Reconstructing words from right-bounded-block words
- Sequence Reconstruction for Limited-Magnitude Errors
- Parikh-friendly permutations and uniformly Parikh-friendly words
- Freeness problem for matrix semigroups of Parikh matrices
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- 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
- Counting subwords in circular words and their Parikh matrices
- Characterizations of families of morphisms and words via binomial complexities
- Reconstruction of hypermatrices from subhypermatrices
- A word reconstruction problem for polynomial regular languages
- On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words
- Binomial coefficients of multidimensional arrays
- Introducing q-deformed binomial coefficients of words
- Recovery of cyclic words by their subwords
- Weak 2-reconstruction in hyper-connected topological spaces
- Reconstruction of a word from a multiset of its factors
- Finite automata for testing composition-based reconstructibility of sequences
This page was built for publication: Reconstruction of sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1182969)
