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 条
  • [1] Standard Sturmian morphisms
    deLuca, A
    THEORETICAL COMPUTER SCIENCE, 1997, 178 (1-2) : 205 - 224
  • [2] Words and morphisms with Sturmian erasures
    Durand, F
    Guerziz, A
    Koskas, M
    BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2004, 11 (04) : 575 - 588
  • [3] Permutation complexity of images of Sturmian words by marked morphisms
    Borchert, Adam
    Rampersad, Narad
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2018, 20 (01):
  • [4] Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words
    Richomme, G.
    THEORETICAL COMPUTER SCIENCE, 2007, 380 (03) : 393 - 400
  • [5] Quasiperiodic Sturmian words and morphisms
    Leve, F.
    Richomme, G.
    THEORETICAL COMPUTER SCIENCE, 2007, 372 (01) : 15 - 25
  • [6] FIBONACCI MORPHISMS AND STURMIAN WORDS
    SEEBOLD, P
    THEORETICAL COMPUTER SCIENCE, 1991, 88 (02) : 365 - 384
  • [7] On an involution of Christoffel words and Sturmian morphisms
    Berthe, Valerie
    de Luca, Aldo
    Reutenauer, Christophe
    EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (02) : 535 - 553
  • [8] Test-words for Sturmian morphisms
    Richomme, G
    BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 1999, 6 (04) : 481 - 489
  • [9] Fixed points of Sturmian morphisms and their derivated words
    Klouda, Karel
    Medkova, Katerina
    Pelantova, Edita
    Starosta, Stepan
    THEORETICAL COMPUTER SCIENCE, 2018, 743 : 23 - 37
  • [10] STANDARD FACTORS OF STURMIAN WORDS
    Richomme, Gwenael
    Saari, Kalle
    Zamboni, Luca Q.
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2010, 44 (01): : 159 - 174