Critical factorisation in square-free words

DOI10.1051/ITA/2022003MaRDI QIDQ5066974zbMATH OpenOpenAlexFDO

Authors Tero Harju

Publication date 31 March 2022

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.09421

zbMATH Keywords

critical factorisation theoremcritical pointsquare-free wordsternary words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: 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.

Recommendations

• Density of Critical Factorizations
• Partial words and the critical factorization theorem revisited
• scientific article; zbMATH DE number 4108170
• Characteristic Sturmian words are extremal for the critical factorization theorem
• Lengths of extremal square-free ternary words

Cites work

• Abelian complexity of fixed point of morphism 0 012, 1 02, 2 1
• Density of Critical Factorizations
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3608306 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Periodes et repetitions des mots du monoide libre
• Two-way string-matching

Cited in

(4)

• Partial words and the critical factorization theorem revisited
• scientific article; zbMATH DE number 4108170 (Why is no real title available?)
• Queer supercrystal structure for increasing factorizations of fixed-point-free involution words
• Characteristic Sturmian words are extremal for the critical factorization theorem

This page was built for publication: Critical factorisation in square-free words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066974)