License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.2
URN: urn:nbn:de:0030-drops-104732
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10473/
Dolce, Francesco ;
Restivo, Antonio ;
Reutenauer, Christophe
Some Variations on Lyndon Words (Invited Talk)
Abstract
In this paper we compare two finite words u and v by the lexicographical order of the infinite words u^omega and v^omega. Informally, we say that we compare u and v by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Algèbres de Lie libres et monoïdes libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].
BibTeX - Entry
@InProceedings{dolce_et_al:LIPIcs:2019:10473,
author = {Francesco Dolce and Antonio Restivo and Christophe Reutenauer},
title = {{Some Variations on Lyndon Words (Invited Talk)}},
booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
pages = {2:1--2:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-103-0},
ISSN = {1868-8969},
year = {2019},
volume = {128},
editor = {Nadia Pisanti and Solon P. Pissis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10473},
URN = {urn:nbn:de:0030-drops-104732},
doi = {10.4230/LIPIcs.CPM.2019.2},
annote = {Keywords: Lyndon words, Infinite words, Left Lyndon trees, Left Cartesian trees}
}
|
Keywords: |
|
Lyndon words, Infinite words, Left Lyndon trees, Left Cartesian trees |
|
Collection: |
|
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.06.2019 |
