Algebraic Combinatorics on Words
Monday, July 11th, 2005M. Lothaire is a pseudonym for a group of authors who wrote the book Combinatorics on Words. The study of words — strings of letters drawn from a fixed alphabet — is surprisingly fruitful in mathematics. For example, finite words form a basis of the free algebra. Sets of infinite words closed under shifts form dynamical systems known as symbolic dynamical systems. Many apparently more-complicated dynamical systems can be reduced to symbolic systems.
A more complicated application is that of Lyndon words. The property of being an aperiodic word is preserved under cyclic permutations. Let two aperiodic words which are cyclic permutations of each other be considered equivalent. Lyndon words are a particular method of choosing one member of each equivalence class. Surprisingly Lyndon words can be used to write down a vector space basis for the free Lie algebra.
M. Lothaire is back with a sequel, Algebraic Combinatorics on Words. The best part? It’s available online.