Lothaire's Books

Applied Combinatorics on Words

The project of this book is the continuation of an already published volumes: ``Combinatorics on Words'' and ``Algebraic Combinatorics on Words''.

The purpose of this volume is to present in a unified form the various applications of combinatorics on words. The fields of the applications include computer science (text processing and compression), linguistics, and biology (genome analysis). It also includes domains of applied mathematics, such as combinatorial enumeration or fractal analysis.

The level of the intended audience is that of a general scientific culture with no specialized knowledge, neither in the fields of applications nor in the detailed contents of the two previous volumes. Thus for example a reader working in computer science could get through the content of the book and obtain enough information about the algorithmic problems and solutions.

As for the previous volumes, the book will be written by a group of authors working together, under the guidance of the editors.


Algebraic Combinatorics on Words

This book covers developments on new topics in the domain of Combinatorics on Words. Cambridge University Press ;Available May 2002.
ISBN: 0521812208


(may 16, 2001)
  1. Contents and Preface
  2. Finite and Infinite Words ( Jean Berstel, Dominique Perrin)
  3. Sturmian Words ( Jean Berstel, Patrice Séébold)
  4. Unavoidable Patterns ( Julien Cassaigne)
  5. Sesquipowers ( Aldo de Luca, Stefano Varricchio)
  6. The Plactic Monoid ( Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon)
  7. Codes (Véronique Bruyère)
  8. Numeration Systems (Christiane Frougny)
  9. Periodicity ( Filippo Mignosi, Antonio Restivo)
  10. Centralizers of Noncommutative Series and Polynomials ( Christophe Reutenauer)
  11. Transformations on words and q-Calculus ( Dominique Foata, Guo-Niu Han, )
  12. Statistics on Permutations and Words ( Jacques Désarménien)
  13. Makanin's Algorithm ( Volker Diekert)
  14. Independent Systems of Equations ( Tero Harju, Juhani Karhumäki, Wojciech Plandowski)
  15. Bibliography and index (see also: About the bibliography)
The whole book is available in PostScript as acw.ps (approx. 3.6 Mo) or compressed PostScript as acw.ps.gz (approx 1.2 Mo).

See also The ACW Style

Combinatorics on Words

New printing

The 1983 edition of M. Lothaire's "Combinatorics on Words", Encyclopedia of Mathematics, Vol. 17, Addison-Wesley has been reprinted in 1997 by Cambridge University Press , with only minor corrections, in the Cambridge Mathematical Library.

Chapter 1 "Words" of the book is available as

The bibliography is available