Recovery of cyclic words by their subwords

Abstract

A problem of reconstructing words from their subwords involves determining the minimum amount of information needed, such as multisets of scattered subwords of a specific length or the frequency of scattered subwords from a given set, in order to uniquely identify a word. In this paper we show that a cyclic word on a binary alphabet can be reconstructed by its scattered subwords of length $\frac{3}{4}n+4$, and for each $n$ one can find two cyclic words of length $n$ which have the same set of scattered subwords of length $\frac{3}{4}n-\frac{3}{2}$.