On ternary Dejean words avoiding 010

Pascal Ochem
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 29, 2023, Number 3, Pages 545–548
DOI: 10.7546/nntdm.2023.29.3.545-548
Full paper (PDF, 187 Kb)

Details

Authors and affiliations

Pascal Ochem
LIRMM, Université de Montpellier, CNRS
Montpellier, France

Abstract

Thue has shown the existence of three types of infinite square-free words over \left\{\texttt{0},\texttt{1},\texttt{2}\right\} avoiding the factor \texttt{010}. They respectively avoid \left\{\texttt{010}, \texttt{212}\right\}, \left\{\texttt{010},\texttt{101}\right\}, and \left\{\texttt{010},\texttt{020}\right\}. Also Dejean constructed an infinite \left(\tfrac74^+\right)-free ternary word. A word is d-directed if it does not contain both a factor of length d and its mirror image. We show that there exist exponentially many \left(\tfrac74^+\right)-free 180-directed ternary words avoiding \texttt{010}. Moreover, there does not exist an infinite \left(\tfrac74^+\right)-free 179-directed ternary word avoiding \texttt{010}.

Keywords

  • Word
  • Repetitions

2020 Mathematics Subject Classification

  • 68R15

References

  1. Badkobeh, G., Harju, T., Ochem, P., & Rosenfeld, M. (2022). Avoiding square-free words on free groups. Theoretical Computer Science, 922, 206–217.
  2. Badkobeh, G., & Ochem, P. (2015). Characterization of some binary words with few squares. Theoretical Computer Science, 588, 73–80.
  3. Dejean, F. (1972). Sur un théorème de Thue. Journal of Combinatorial Theory, Series A, 13, 90–99.
  4. Ochem, P. (2006). A generator of morphisms for infinite words. RAIRO – Theoretical Informatics and Applications, 40, 427–441.
  5. Ochem, P., Rao, M., & Rosenfeld, M. (2018). Avoiding or limiting regularities in words. Sequences, Groups, and Number Theory (Trends in Mathematics), 177–212.
  6. Rampersad, N., & Shallit, J. (2012). Repetitions in words. Combinatorics, Words and Symbolic Dynamics (Encyclopedia of Mathematics and its Applications), 101–150.
  7. Thue, A. (1912). Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse, 1, 1–67. Reprinted in: Nagell, T. (Ed.). Selected Mathematical Papers of Axel Thue. Universitetsforlaget, Oslo, 1977, 413–478.

Manuscript history

  • Received: 3 March 2023
  • Revised: 17 July 2023
  • Accepted: 25 July 2023
  • Online First: 27 July 2023

Copyright information

Ⓒ 2023 by the Author.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

Related papers

Cite this paper

Ochem, P. (2023). On ternary Dejean words avoiding 010. Notes on Number Theory and Discrete Mathematics, 29(3), 545-548, DOI: 10.7546/nntdm.2023.29.3.545-548.

Comments are closed.