1. Recovery of cyclic words by their subwords
- Author
-
Luchinin, Sergey, Puzynina, Svetlana, and Rao, Michaël
- Subjects
Computer Science - Discrete Mathematics ,Mathematics - Combinatorics ,68R15 - 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 $\frac34n+4$, and for each $n$ one can find two cyclic words of length $n$ which have the same set of scattered subwords of length $\frac34n-\frac32$.
- Published
- 2024