Reconstruction of sequences (Q1182969): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192069 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph reconstruction—a survey / rank | |||
Normal rank |
Revision as of 15:35, 15 May 2024
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