Generalized Lyndon words. (Mots de Lyndon généralisés.) (French. English summary) Zbl 1183.68445
Summary: By choosing for each position \(i\) of infinite words in \(A^{\mathbb N}\) a total order on \(A\), one defines a lexicographical order on \(A^{\mathbb N}\). This can be used 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 the usual Lyndon words, is the Galois words, obtained through an alternate lexicographical order on \(A^{\mathbb N}\). These words have several number-theoretical applications involving, for example, Galois numbers and their homographic classes, binary indefinite quadratic forms, and Markov numbers.
MSC:
68R15 | Combinatorics on words |
05A05 | Permutations, words, matrices |
11J06 | Markov and Lagrange spectra and generalizations |