Theory of codes. (English) Zbl 0587.68066

This book is the first treatise on variable-length codes; it provides a systematic exposition of the topic, showing its connection with theoretical computer science (automata, semigroups, formal languages), probability, noncommutative algebra, permutation groups, combinatorics. The subject is part of what is called effective mathematics and presents many algorithms and constructions of families of codes - although the construction of all finite maximal codes is still an open problem.
The authors have chosen to develop the theory in the most general way, in order to point out the main arguments. Indeed, they treat the case of thin codes, which generalize finite and even recognizable codes. Chapter 0 is an introductory chapter on monoids, words, automata, formal series and permutation groups. Chapter 1 is the real beginning: codes, a test for codes, complete and maximal codes. Chapter 2 gives a systematic study of prefix codes; this chapter is very intuitive, particularly because of the use of trees; however, it ends with a deep result on deciphering delay. Chapter 3 presents the beautiful combinatorial theory of biprefix codes, and the various characterizations of the degree. Chapter 4 is rather technical, but necessary for the syntactic approach which is used in the next chapter; it presents a special class of automata, the unambiguous automata; the first application is the theorem of synchronization of semaphore codes. In chapter 5 the permutation groups associated with biprefix codes are studied; the main result states that if the code is moreover finite and indecomposable, then this group is doubly transitive. Chapter 6 gives the probabilistic approach of codes; the formula relating degree and density is proved. Chapter 7 deals with problems about conjugacy; it gives results on circular codes and various results on constructions of optimal circular codes and factorization of free monoids. Chapter 8 presents the commutative factorization theorem; see the last chapter of the forthcoming book of J. Berstel and the reviewer (Rational series and their languages, Springer Verlag) for the extension of this theorem to the noncommutative case; the last result links biprefix codes and semisimple algebras.
The whole book is written at an elementary level and may be used for courses at various levels in computer science, algebra or probability theory. Each chapter ends with an exercise section and bibliographical and historical notes.
Reviewer: C.Reutenauer


68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
94A45 Prefix, length-variable, comma-free codes
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
20M12 Ideal theory for semigroups
20B20 Multiply transitive finite groups
60B99 Probability theory on algebraic and topological structures
16S10 Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.)