2019/04/19 by Day, Joel D., Fleischmann, Pamela, Manea, Florin +1
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1904.09125
A word u is a scattered factor of w if u can be obtained from w by deleting some of its letters. That is, there exist the (potentially empty) words u1,u2,..., un, and v0,v1,..,vn such that u = u1u2...un and w = v0u1v1u2v2...unvn. We consider the set of length-k scattered factors of a given word w, called here k-spectrum and denoted \ScatFactk(w). We prove a series of properties of the sets \ScatFactk(w) for binary strictly balanced and, respectively, c-balanced words w, i.e., words over a two-letter alphabet where the number of occurrences of each letter is the same, or, respectively, one letter has c-more occurrences than the other. In particular, we consider the question which cardinalities n= |\ScatFactk(w)| are obtainable, for a positive integer k, when w is either a strictly balanced binary word of length 2k, or a c-balanced binary word of length 2k-c. We also consider the problem of reconstructing words from their k-spectra.