Skip to Main content Skip to Navigation
Journal articles

Repetition avoidance in products of factors

Pamela Fleischmann Pascal Ochem 1 Kamellia Reshadi
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let $\texttt{pexp}_i(w)$ be the supremum of the exponent over the products of $i$ factors of the word $w$. The repetition threshold $\texttt{RT}_i(k)$ is then the infimum of $\texttt{pexp}_i(w)$ over all words $w\in\Sigma^\omega_k$. Moussavi and Shallit obtained that $\texttt{RT}_i(2)=2i$ and $\texttt{RT}_2(3)=\tfrac{13}4$. We show that $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac14$ if $i$ is even and $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac16$ if $i$ is odd and $i\ge3$.
Document type :
Journal articles
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02500480
Contributor : Pascal Ochem <>
Submitted on : Friday, March 6, 2020 - 12:32:49 AM
Last modification on : Tuesday, March 10, 2020 - 1:36:20 AM
Document(s) archivé(s) le : Sunday, June 7, 2020 - 12:40:42 PM

Identifiers

Collections

Citation

Pamela Fleischmann, Pascal Ochem, Kamellia Reshadi. Repetition avoidance in products of factors. Theoretical Computer Science, Elsevier, 2019, 791, pp.123-126. ⟨10.1016/j.tcs.2019.04.013⟩. ⟨lirmm-02500480⟩

Share

Metrics

Record views

73

Files downloads

144