A regularity lemma and twins in words - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

A regularity lemma and twins in words

Tekijät: M Axenovich, Yu Person, S Puzynina

Kustantaja: elsevier

Julkaisuvuosi: 2013

Journal: Journal of Combinatorial Theory, Series A

Numero sarjassa: 4

Vuosikerta: 120

Numero: 4

Aloitussivu: 733

Lopetussivu: 743

Sivujen määrä: 11

ISSN: 0097-3165

DOI: https://doi.org/10.1016/j.jcta.2013.01.001

Tiivistelmä

We prove that in a word of length n over an alphabet of k letters there are l disjoints identical (scattered) subwords of length n/l/o(n) for l \geq k. E.g., any binary word of length n can be split into two identical subwords (referred to as twins) and, perhaps, a remaining subword of length o(n).