Sturmian images of non Sturmian words and standard morphisms

被引:2
作者
Seebold, Patrice [1 ,2 ]
机构
[1] Univ Paul Valery Montpellier 3, Route Mende, F-34199 Montpellier 5, France
[2] CNRS, Lab Informat Robot & Microelect Montpellier, UMR 5506, 161 Rue Ada, F-34392 Montpellier, France
关键词
Sturmian words; Sturmian morphisms; Standard morphisms; DOL systems; HDOL systems; Fibonacci word; ITERATED MORPHISMS; CONJUGATION;
D O I
10.1016/j.tcs.2017.11.011
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We prove that if a Sturmian word is the image by a morphism of a word which is a fixed point of another morphism, then this latter word is mostly a Sturmian word, and the involved morphisms are Sturmian. This gives a characterization of Sturmian words that are generated by HDOL systems. We also characterize the non Sturmian words which can be sent on Sturmian words by morphism, and the involved morphisms. We prove that the same Sturmian images can be obtained by using the standard morphisms of which the above morphisms are the conjugates, and we show how to obtain these Sturmian morphisms from their standard representatives. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码:92 / 104
页数:13
相关论文
共 50 条
[41]   Rauzy substitutions and multi-dimensional Sturmian words [J].
Tijdeman, R .
THEORETICAL COMPUTER SCIENCE, 2005, 346 (2-3) :469-489
[42]   Some Characterizations of Sturmian Words in Terms of the Lexicographic Order [J].
Bucci, Michelangelo ;
De Luca, Alessandro ;
Zamboni, Luca Q. .
FUNDAMENTA INFORMATICAE, 2012, 116 (1-4) :25-33
[43]   On Sturmian graphs [J].
Epifanio, Chiara ;
Mignosi, Filippo ;
Shallit, Jeffrey ;
Venturin, Ilaria .
DISCRETE APPLIED MATHEMATICS, 2007, 155 (08) :1014-1030
[44]   THUE-MORSE-STURMIAN WORDS AND CRITICAL BASES FOR TERNARY ALPHABETS [J].
Steiner, Wolfgang .
BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 2020, 148 (04) :597-611
[45]   Fine and Wilf's theorem for three periods and a generalization of Sturmian words [J].
Castelli, MG ;
Mignosi, F ;
Restivo, A .
THEORETICAL COMPUTER SCIENCE, 1999, 218 (01) :83-94
[46]   Relation between powers of factors and the recurrence function characterizing Sturmian words [J].
Masakova, Z. ;
Pelantova, E. .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) :3589-3596
[47]   On the conjugation of standard morphisms [J].
Seebold, P .
THEORETICAL COMPUTER SCIENCE, 1998, 195 (01) :91-109
[48]   On Palindromic Length of Sturmian Sequences [J].
Ambroz, Petr ;
Pelantova, Edita .
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2019, 2019, 11647 :244-250
[49]   Fractal networks with Sturmian structure [J].
Zeng, Cheng ;
Xue, Yumei ;
Huang, Yuke .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2021, 574
[50]   STURMIAN JUNGLE (OR GARDEN?) ON MULTILITERAL ALPHABETS [J].
Balkova, L'ubomira ;
Pelantova, Edita ;
Starosta, Stepan .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2010, 44 (04) :443-470