On a Reconstruction Problem for Sequences

✍ Scribed by I. Krasikov; Y. Roditty

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 439 KB
• Volume: 77
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2732

✦ Synopsis

It is shown that any word of length n is uniquely determined by all its ( n k ) subwords of length k, provided k w 16 7 -nx+5. This improves the bound k wnÂ2x given in B. Manvel et al. (Discrete Math. 94 (1991), 209 219).

1997 Academic Press

1. Introduction

Given a word X of length n with terms from an alphabet 7, define the k-deck of X, D k (X ), to be the multiset of all ( n k ) k-subwords of X. The following reconstruction problem is due to Kalashnik [4],

When is X uniquely determined by D k (X )?

We call X k-reconstructible when this is the case. We call words X and Y k-equivalent if D k (X )=D k (Y ) (We will only use this term for distinct words).

This question resembles the well-known vertex reconstruction problem (see Bondy [1]) but seems more tractable. The problem has been treated in [5] by Manvel et. al. They proved that any word of length n is k-reconstructible whenever k wnÂ2x. On the other hand, they gave a construction of nonreconstructible words for k log 2 n. It also has been shown in [5] that without loss of generality we can restrict the problem to words over the alphabet [0, 1], in view of the following:

All words of length n with terms from an alphabet 7 are k-reconstructible if and only if all words of the same length with terms from [0, 1] are k-reconstructible.