A regularity lemma and twins in words




M Axenovich, Yu Person, S Puzynina

Publisherelsevier

2013

Journal of Combinatorial Theory, Series A

4

120

4

733

743

11

0097-3165

DOIhttps://doi.org/10.1016/j.jcta.2013.01.001




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




Last updated on 2024-26-11 at 19:38