Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

被引：8
|
作者：
Richomme, G. [1 ]
机构：
[1] Univ Picardie, LaRIA, F-80039 Amiens 1, France
来源：
THEORETICAL COMPUTER SCIENCE | 2007年 / 380卷 / 03期
关键词：
Sturmian words; Lyndon decomposition; morphisms; conjugacy;
D O I：
10.1016/j.tcs.2007.03.028
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melancon. We characterize cases where the sequence of Lyndon words in the Lyndon factorization of a standard Sturmian word is morphic. In each possible case, the corresponding morphism is given. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：393 / 400
页数：8
相关论文
共 50 条
  • [31] The Sum of Exponents of Maximal Repetitions in Standard Sturmian Words
    Piatkowski, Marcin
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2013, 2013, : 48 - 62
  • [32] Computing the number of cubic runs in standard Sturmian words
    Piatkowski, Marcin
    Rytter, Wojciech
    DISCRETE APPLIED MATHEMATICS, 2014, 163 : 361 - 372
  • [33] Applications of standard Sturmian words to elementary number theory
    Brown, TC
    THEORETICAL COMPUTER SCIENCE, 2002, 273 (1-2) : 5 - 9
  • [34] Conjugacy and episturmian morphisms
    Richomme, G
    THEORETICAL COMPUTER SCIENCE, 2003, 302 (1-3) : 1 - 34
  • [35] The average lengths of the factors of the standard factorization of Lyndon words
    Bassino, F
    Clément, J
    Nicaud, C
    DEVELOPMENTS IN LANGUAGE THEORY, 2003, 2450 : 307 - 318
  • [36] The standard factorization of Lyndon words:: an average point of view
    Bassino, F
    Clément, J
    Nicaud, C
    DISCRETE MATHEMATICS, 2005, 290 (01) : 1 - 25
  • [37] ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS
    Piatkowski, Marcin
    Rytter, Wojciech
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (02) : 303 - 321
  • [38] Inverse Lyndon words and inverse Lyndon factorizations of words
    Bonizzoni, Paola
    De Felice, Clelia
    Zaccagnino, Rocco
    Zizza, Rosalba
    ADVANCES IN APPLIED MATHEMATICS, 2018, 101 : 281 - 319
  • [39] ω-Lyndon words
    Postic, Mickael
    Zamboni, Luca Q.
    THEORETICAL COMPUTER SCIENCE, 2020, 834 : 60 - 65
  • [40] ω-Lyndon words
    Postic, Mickael
    Zamboni, Luca Q.
    THEORETICAL COMPUTER SCIENCE, 2020, 809 : 39 - 44
12345