Sturmian words and a criterium by Michaux-Villernaire

被引：0
作者：
Araújo, IM
Bruyère, W
机构：
[1] Univ Mons, Inst Informat, B-7000 Mons, Belgium
[2] Univ Evora, Dept Matemat, P-7000671 Evora, Portugal
来源：
THEORETICAL COMPUTER SCIENCE | 2005年 / 339卷 / 01期
关键词：
combinatorics on words; Sturmian words;
D O I：
10.1016/j.tcs.2005.01.010
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. In this paper we study those properties for characteristic Sturmian words. In particular we answer a question posed by Michaux and Villemaire in that context. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：88 / 102
页数：15
相关论文
共 10 条
[1]  
Allouche J.-P., 2003, Automatic Sequences: Theory, Applications, Generalizations
[2]   GEOMETRIC REPRESENTATION OF SEQUENCES OF COMPLEXITY 2N+1 [J].
ARNOUX, P ;
RAUZY, G .
BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 1991, 119 (02) :199-215
[3]  
Berstel J., 1996, Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology, P13
[4]   Frequencies of factors of Sturmian sequences [J].
Berthe, V .
THEORETICAL COMPUTER SCIENCE, 1996, 165 (02) :295-309
[5]  
Cassaigne J, 1997, LECT NOTES COMPUT SC, V1256, P693
[6]   Episturmian words and some constructions of de Luca and Rauzy [J].
Droubay, X ;
Justin, J ;
Pirillo, G .
THEORETICAL COMPUTER SCIENCE, 2001, 255 (1-2) :539-553
[7]   Generalized balances in Sturmian words [J].
Fagnot, I ;
Vuillon, L .
DISCRETE APPLIED MATHEMATICS, 2002, 121 (1-3) :83-101
[8]  
Lothaire M., 2002, ENCY MATH ITS APPL
[9]   Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems [J].
Michaux, C ;
Villemaire, R .
ANNALS OF PURE AND APPLIED LOGIC, 1996, 77 (03) :251-277
[10]   A characterization of sturmian words by return words [J].
Vuillon, L .
EUROPEAN JOURNAL OF COMBINATORICS, 2001, 22 (02) :263-275
1