This work proposes a new approach towards solving an over 20 years old conjecture regarding the maximum number of distinct squares that a word can contain. To this end we look at clusters of repetition roots, that is, the set of positions where the root u of a repetition uℓ occurs. We lay the foundation of this theory by proving basic properties of these clusters and establishing upper bounds on the number of distinct squares when their roots form a chain with respect to the prefix order.
Funding
JSPS KAKENHI Grant Number JP19K11815
History
School
Science
Department
Computer Science
Published in
SOFSEM 2021: Theory and Practice of Computer Science
Pages
400 - 409
Source
47th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2021)