2020/01/30 by Fleischmann, Pamela, Lejeune, Marie, Manea, Florin +2 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2001.11218
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 ∈ \a, b\* can be reconstructed from the number of occurrences of at most min(|w|a, |w|b)+ 1 scattered factors of the form ai b. Moreover, we generalize the result to alphabets of the form \1,…,q\ by showing that at most ∑q-1i=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.