k-spectra of weakly-c-balanced words
conference contributionposted on 21.07.2021, 13:40 by Joel DayJoel Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka
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 weakly-0-balanced and, respectively, weakly-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 weakly-0-balanced binary word of length 2k, or a weakly-c-balanced binary word of length 2k − c. We also consider the problem of reconstructing words from their k-spectra.
- Computer Science