k-Spectra of weakly-c-Balanced Words

Abstract: 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

u_{1}, u_{2}, ..., u_{n}

, and

v_{0}, v_{1}, .., v_{n}

such that

u = u_{1} u_{2} ... u_{n}

and

w = v_{0} u_{1} v_{1} u_{2} v_{2} ... u_{n} v_{n}

. We consider the set of length-

k

scattered factors of a given word w, called here

k

-spectrum and denoted

S c a t F a c t_{k} (w)

. We prove a series of properties of the sets

S c a t F a c t_{k} (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 = | S c a t F a c t_{k} (w) |

are obtainable, for a positive integer

k

, when

w

is either a strictly balanced binary word of length

2 k

, or a

c

-balanced binary word of length

2 k - c

. We also consider the problem of reconstructing words from their

k

-spectra.

This page was built for publication: k-Spectra of weakly-c-Balanced Words