Reconstructing Words from Right-Bounded-Block Words

Abstract

A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word $w\in \{a,b{\}}^{\ast }$ can be reconstructed from the number of occurrences of at most $\min (|w{|}_a,|w{|}_b)+1$ scattered factors of the form $a^{i}b$. Moreover, we generalize the result to alphabets of the form $\{1,\dots ,q\}$ by showing that at most ${\sum }_{i=1}^{q-1}|w{|}_i(q-i+1)$ scattered factors suffices to reconstruct $w$. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.