Séminaire Lotharingien de Combinatoire, B54h (2006), 16 pp.
Christophe Reutenauer
Mots de Lyndon généralisés
Abstract.
By choosing for each position i of infinite words in
AN a
total order on A, one defines a lexicographical order on
AN.
It allows to define generalized Lyndon words. They factorize
the free monoid, form Hall sets and give bases of the free Lie
algebras. The main example, apart from usual Lyndon words, are the
Galois words, obtained through the alternate lexicographical order on
AN. They have several number-theoretical applications:
Galois numbers, their homographics classes, binary indefinite
quadratic forms, Markoff numbers.
Received: May 6, 2005.
Accepted: March 14, 2006.
Final Version: April 20, 2006.
The following versions are available: