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 条
[31]   USEFULNESS OF DIRECTED ACYCLIC SUBWORD GRAPHS IN PROBLEMS RELATED TO STANDARD STURMIAN WORDS [J].
Baturo, Pawel ;
Piatkowski, Marcin ;
Rytter, Wojciech .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2009, 20 (06) :1005-1023
[32]   Sturmian words and a criterium by Michaux-Villernaire [J].
Araújo, IM ;
Bruyère, W .
THEORETICAL COMPUTER SCIENCE, 2005, 339 (01) :88-102
[33]   Column Representation of Sturmian Words in Cellular Automata [J].
Dolce, Francesco ;
Tahay, Pierre-Adrien .
DEVELOPMENTS IN LANGUAGE THEORY (DLT 2022), 2022, 13257 :127-138
[34]   Burrows-Wheeler transform and Sturmian words [J].
Mantaci, S ;
Restivo, A ;
Sciortino, M .
INFORMATION PROCESSING LETTERS, 2003, 86 (05) :241-246
[35]   Circular sturmian words and Hopcroft's algorithm [J].
Castiglione, G. ;
Restivo, A. ;
Sciortino, M. .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (43) :4372-4381
[36]   Morse and Hedlund’s Skew Sturmian Words Revisited [J].
Giuseppe Pirillo .
Annals of Combinatorics, 2008, 12 :115-121
[37]   Characteristic Sturmian words are extremal for the Critical Factorization Theorem [J].
Mignosi, Filippo ;
Restivo, Antonio .
THEORETICAL COMPUTER SCIENCE, 2012, 454 :199-205
[38]   Morse and Hedlund's skew Sturmian words revisited [J].
Pirillo, Giuseppe .
ANNALS OF COMBINATORICS, 2008, 12 (01) :115-121
[39]   Some Recent Results of Fibonacci Numbers, Fibonacci Words and Sturmian Words [J].
Pirillo, G. .
SOUTHEAST ASIAN BULLETIN OF MATHEMATICS, 2019, 43 (02) :273-286
[40]   On substitution invariant sturmian words:: An application of rauzy fractals [J].
Berthe, Valerie ;
Ei, Hiromi ;
Ito, Shunji ;
Rao, Hui .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2007, 41 (03) :329-349