Critical factorisation in square-free words

Tero Harju

A position $p$ in a word $w$ is critical if the minimal local period at $p$ is equal to the global period of $w$. According to the Critical Factorisation Theorem all words of length at least two have a critical point. We study the number $\eta(w)$ of critical points of square-free ternary words $w$, i.e., words over a three letter alphabet. We show that the sufficiently long square-free words $w$ satisfy $\eta(w) \le |w|-5$ where $|w|$ denotes the length of $w$. Moreover, the bound $|w|-5$ is reached by infinitely many words. On the other hand, every square-free word $w$ has at least $|w|/4$ critical points, and there is a sequence of these words closing to this bound.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment