Reconstruction of sequences (Q1182969)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reconstruction of sequences |
scientific article |
Statements
Reconstruction of sequences (English)
0 references
28 June 1992
0 references
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.
0 references
reconstruction of sequences
0 references