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 条
  • [21] Lyndon morphisms
    Richomme, G
    BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2003, 10 : 761 - 785
  • [22] Standard Sturmian words and automata minimization algorithms
    Castiglione, G.
    Sciortino, M.
    THEORETICAL COMPUTER SCIENCE, 2015, 601 : 58 - 66
  • [23] The maximal number of runs in standard Sturmian words
    Baturo, Pawel
    Piatkowski, Marcin
    Rytter, Wojciech
    ELECTRONIC JOURNAL OF COMBINATORICS, 2013, 20 (01):
  • [24] Inequalities characterizing standard Sturmian and episturmian words
    Pirillo, G
    THEORETICAL COMPUTER SCIENCE, 2005, 341 (1-3) : 276 - 292
  • [25] Standard Lyndon Loop Words: Weighted Orders
    Khomych, Severyn
    Korniichuk, Nazar
    Molokanov, Kostiantyn
    Tsymbaliuk, Alexander
    INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2025, 2025 (05)
  • [26] Affine Standard Lyndon Words: A-Type
    Avdieiev, Yehor
    Tsymbaliuk, Alexander
    INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2024, 2024 (21) : 13488 - 13524
  • [27] On a faithful representation of Sturmian morphisms
    Lepsova, Jana
    Pelantova, Edita
    Starosta, Stepan
    EUROPEAN JOURNAL OF COMBINATORICS, 2023, 110
  • [28] Conjugation of standard morphisms and a generalization of singular words
    Levé, F
    Séébold, P
    BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2003, 10 : 737 - 747
  • [29] Compressed string-matching in standard Sturmian words
    Baturo, Pawel
    Rytter, Wojciech
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (30-32) : 2804 - 2810
  • [30] Computing the Number of Cubic Runs in Standard Sturmian Words
    Piatkowski, Marcin
    Rytter, Wojciech
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011, 2011, : 106 - 120
12345