Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melançon. 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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-06, Vol.380 (3), p.393-400
Main Author: Richomme, G.
Format: Article
Language:English
Subjects:
Applied sciences
Computer Science
Computer science
control theory
systems
Conjugacy
Discrete Mathematics
Exact sciences and technology
Lyndon decomposition
Miscellaneous
Morphisms
Sturmian words
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melançon. 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.03.028