k-spectra of weakly-c-balanced words

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Joel Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka
Format: Conference Proceeding
Language:English
Subjects:
Artificial Intelligence & Image Processing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.