Algebraic Combinatorics on Words

M. 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.

2 thoughts on “Algebraic Combinatorics on Words

  1. I quite enjoyed the first book, but probably won’t get time to read the second for a while. How does it stack up to the first?

  2. It’s definitely a sequel and not an updated version of the original work. The subject that I was particularly interested in, the free Lie algebra, gets short shrift in the new book, probably because nothing new has happened on the topic. Symbolic dynamics plays a bigger role (I don’t remember if it appears in the first book), and it covers several new results and applications.

Comments are closed.