Sturmian words and a criterium by Michaux-Villemaire
type: Item
instance of: scholarly article
title: Sturmian words and a criterium by Michaux-Villemaire
zbMATH Open document ID: 1076.68050
author: Isabel M. Araújo
author: Véronique Bruyère
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
review text: From the authors' abstract: ``Michaux and Villemaire's proof of Cobham's theorem relies on the characterization of ultimately periodic words by means of the behaviour of certain repetitions in the word. Namely, they consider the length of the smallest shift between repetitions of a given length and the first position at which that smallest shift is observed.'' Their characterization needs that two sequences \(\delta\) and \(\alpha\) admit certain syndetic subsequences (an increasing sequence of integers is called syndetic if its first difference is bounded); and they ask whether it is possible to assume that only one of these two subsequences is syndetic. The authors of the present paper study in detail \(\delta\) and \(\alpha\) for characteristic Sturmian sequences. As a consequence of their study they prove that the answer to \textit{C. Michaux} and \textit{R. Villemaire}'s question is negative [Ann. Pure Appl. Logic 77, No. 3, 251--277 (1996; Zbl 0857.03003)].
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 2184113
zbMATH Keywords: combinatorics on words
zbMATH Keywords: synthetic sequences
zbMATH Keywords: Cobham's theory
zbMATH Keywords: Sturmian sequences
zbMATH Keywords: repetitions in infinite words
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.01.010
OpenAlex ID: W1978078781
cites work: Automatic Sequences
cites work: Représentation géométrique de suites de complexité $2n+1$
cites work: Q5486010
cites work: Frequencies of factors of Sturmian sequences
cites work: On a conjecture of J. Shallit
cites work: Episturmian words and some constructions of de Luca and Rauzy
cites work: Generalized balances in Sturmian words
cites work: Q4529547
cites work: Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
cites work: A characterization of Sturmian words by return words
DOI: 10.1016/J.TCS.2005.01.010
description: scientific article; zbMATH DE number 2184113