2024/12/04 by Luchinin, Sergey, Puzynina, Svetlana, Rao, Michaël
#68R15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.03289
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.