Foreword

Summary

This is the first book devoted to broad study of the combinatorics of words, that is to say, of sequences of symbols called letters. This subject is in fact very ancient and has cropped up repeatedly in a wide variety of contexts. Even in the most elegant parts of abstract pure mathematics, the proof of a beautiful theorem surprisingly often reduces to some very down to earth combinatorial lemma concerning linear arrays of symbols. In applied mathematics, that is in the subjects to which mathematics can be applied, such problems are even more to be expected. This is true especially in those areas of contemporary applied mathematics that deal with the discrete and non-commutative aspects of the world about us, notably the theory of automata, information theory, and formal linguistics.

The systematic study of words seems to have been initiated by Axel Thue in three papers [Norske Vid. Selsk. Skr. I Mat. Nat. Kl. Christiania, 1906, 1–22; 1912, 1–67; 1914, 1–34.]. Even more than for his theorems, we owe him a great debt for delineating this subject. Both before and after his time, a multitude of fragmentary results have accumulated in the most diverse contexts, and a substantial but not very widely known lore was beginning to crystallize to the point where a systematic treatment of the subject was badly needed and long over due.

This need is splendidly fulfilled by the present volume.