DLT2019.pdf (313.45 kB)

k-spectra of weakly-c-balanced words

Download (313.45 kB)
conference contribution
posted on 21.07.2021, 13:40 by Joel 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.

History

School

  • Science

Department

  • Computer Science

Published in

Developments in Language Theory

Pages

265 - 277

Source

International Conference on Developments in Language Theory (DLT 2019)

Publisher

Springer

Version

AM (Accepted Manuscript)

Rights holder

© Springer Nature Switzerland AG

Publisher statement

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-24886-4_20.

Publication date

2019-07-10

Copyright date

2019

ISBN

9783030248857; 9783030248864

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science; 11647

Language

en

Editor(s)

Piotrek Hofman; Michał Skrzypczak

Location

Warsaw, Poland

Event dates

5th August 2019 - 9th August 2019

Depositor

Dr Joel Day. Deposit date: 21 July 2021

Usage metrics

Read the paper on the publisher website

Loughborough Publications

Categories

Exports