Critical factorisation in square-free words

DOI10.1051/ITA/2022003zbMATH Open1493.68282arXiv2107.09421OpenAlexW4212984554MaRDI QIDQ5066974FDOQ5066974

Authors: Tero Harju 

Publication date: 31 March 2022

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

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.

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

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

zbMATH Keywords

critical pointsquare-free wordsternary wordscritical factorisation theorem

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Two-way string-matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abelian complexity of fixed point of morphism \(0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1\)
• Periodes et repetitions des mots du monoide libre
• Density of Critical Factorizations

Cited In (4)

• Queer supercrystal structure for increasing factorizations of fixed-point-free involution words
• Partial words and the critical factorization theorem revisited
• Characteristic Sturmian words are extremal for the critical factorization theorem
• Title not available (Why is that?)

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)