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: