A1 Refereed original research article in a scientific journal

A regularity lemma and twins in words



Authors: M Axenovich, Yu Person, S Puzynina

Publisher: elsevier

Publication year: 2013

Journal: Journal of Combinatorial Theory, Series A

Number in series: 4

Volume: 120

Issue: 4

First page : 733

Last page: 743

Number of pages: 11

ISSN: 0097-3165

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


Abstract

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