Codes and automata.

*(English)*Zbl 1187.94001
Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press (ISBN 978-0-521-88831-8/hbk). xiii, 619 p. (2010).

This book is a comprehensive study of the theory of variable length codes, being a complete reworking of the book “Theory of Codes” published by the first two authors more than 20 years ago. This theory has now become a part of theoretical computer science and is strongly related to combinatorics on words, automata theory, formal languages, and the theory of semigroups. The object of the theory of codes being the study of the properties concerning factorizations of words into sequences of words taken from a given set, one of the basic techniques used in this book is constructing special automata that perform this kind of parsing. The problem of encoding here is the study of embeddings of a free monoid into another and this book indicates how the study of a group associated with a code can reveal some of its properties.

The aim of the theory of codes is to give a structural description of codes in a way that allows their construction; this is accomplished for prefix codes in Chapter 3 and the more difficult case of bifix codes and its complete structural description is given in Chapter 6. The result given in Chapter 14 about the factorization of the polynomial of a code must be considered as a step toward the understanding of codes. Many of the results presented in this book are concerned with extremal properties, which in general reflect some optimization in the encoding process. Two types of methods are used in the book: direct methods on words, and automata and semigroups, used in Chapters 9-14, including the study of special automata associated with codes, called unambigous automata and the corresponding monoids of relations. Codes and automata are related to algorithms on words and graphs, whose computational complexity is one of the topics of the book.

Chapter 1 (Preliminaries) is intended to present notation concerning monoids, words, automata, semirings and matrices, formal series, weighted automata, ideals in a monoid, permutation groups. Chapter 2 (Codes) contains the definition, the relationship with submonoids, and the introduction of the notions of complete, maximal, and thin codes. Chapter 3 (Prefix codes) is devoted to a systematic study of prefix codes, by considering optimal prefix codes under various constraints, in particular the Garsia-Wachs algorithm. Chapter 4 (Automata) describes the automata used for representing codes, and for encoding and decoding words, the flower automaton being the basic tool for a syntactic study of codes. It is shown how to construct deterministic transducers (encoders and decoders). Chapter 5 (Deciphering delay) introduces the deciphering delay, the family of weakly prefix codes and their relation with weakly deterministic automata. Chapter 6 (Bifix codes) describes the structure of maximal bifix codes and methods for constructing the finite ones, including the use of formal power series. Chapter 7 (Circular codes) contains a description of length distributions of circular codes, related to classical enumerative combinatorics and the study of comma-free codes. Chapter 8 (Factorizations of free monoids) introduces the factorizations of a free monoid and the characterization of the codes that may appear as factors. Chapter 9 (Unambiguous monoids of relations) contains the characterization of thin maximal codes by a finiteness condition on the transition monoid of an unambiguous automaton. Chapter 10 (Synchronization) presents results linked to the notion of synchronized codes and a proof of the road coloring problem, which has been recently solved. Chapter 11 (Groups of codes) contains the proof of the theorem of synchronization of semaphore codes and several results on the groups of finite maximal bifix codes. Chapter 12 (Factorizations of cyclic groups) describes several classes of factorizations of cyclic groups, such as those due to Hajós and Rédei. Chapter 13 (Densities) starts with a presentation of basics on probability spaces, and contains Kolmogorov’s extension theorem, as well as the formula of densities. Chapter 14 (Polynomials of finite codes) contains the proof and discussion of the theorem of the factorization of the polynomial of a finite maximal code. The book ends with the connection between maximal bifix codes and semisimple algebras. In the appendix the conjectures mentioned in the book and some additonal open problems are presented. Many examples are given which come from practical applications and illustrate the notions.

Each chapter is followed by a section of exercises, which frequently complement the material covered in the text. Solutions of some 200 exercises are proposed at the end of the book. Each chapter ends with notes containing references, bibliographic discussions, complementary material, and references for the exercises.

The book is a valuable contribution to the field. It may be used by researchers in coding theory, as well as a material for several courses, at various levels, in undergraduate or graduate curricula. Because of the extensive use of trees and of the corresponding algorithms and the properties of the structure of unambiguous monoids of relations, some chapters of this book and associated exercises might constitute an interesting complement to a programming course or to a course in algebra.

The aim of the theory of codes is to give a structural description of codes in a way that allows their construction; this is accomplished for prefix codes in Chapter 3 and the more difficult case of bifix codes and its complete structural description is given in Chapter 6. The result given in Chapter 14 about the factorization of the polynomial of a code must be considered as a step toward the understanding of codes. Many of the results presented in this book are concerned with extremal properties, which in general reflect some optimization in the encoding process. Two types of methods are used in the book: direct methods on words, and automata and semigroups, used in Chapters 9-14, including the study of special automata associated with codes, called unambigous automata and the corresponding monoids of relations. Codes and automata are related to algorithms on words and graphs, whose computational complexity is one of the topics of the book.

Chapter 1 (Preliminaries) is intended to present notation concerning monoids, words, automata, semirings and matrices, formal series, weighted automata, ideals in a monoid, permutation groups. Chapter 2 (Codes) contains the definition, the relationship with submonoids, and the introduction of the notions of complete, maximal, and thin codes. Chapter 3 (Prefix codes) is devoted to a systematic study of prefix codes, by considering optimal prefix codes under various constraints, in particular the Garsia-Wachs algorithm. Chapter 4 (Automata) describes the automata used for representing codes, and for encoding and decoding words, the flower automaton being the basic tool for a syntactic study of codes. It is shown how to construct deterministic transducers (encoders and decoders). Chapter 5 (Deciphering delay) introduces the deciphering delay, the family of weakly prefix codes and their relation with weakly deterministic automata. Chapter 6 (Bifix codes) describes the structure of maximal bifix codes and methods for constructing the finite ones, including the use of formal power series. Chapter 7 (Circular codes) contains a description of length distributions of circular codes, related to classical enumerative combinatorics and the study of comma-free codes. Chapter 8 (Factorizations of free monoids) introduces the factorizations of a free monoid and the characterization of the codes that may appear as factors. Chapter 9 (Unambiguous monoids of relations) contains the characterization of thin maximal codes by a finiteness condition on the transition monoid of an unambiguous automaton. Chapter 10 (Synchronization) presents results linked to the notion of synchronized codes and a proof of the road coloring problem, which has been recently solved. Chapter 11 (Groups of codes) contains the proof of the theorem of synchronization of semaphore codes and several results on the groups of finite maximal bifix codes. Chapter 12 (Factorizations of cyclic groups) describes several classes of factorizations of cyclic groups, such as those due to Hajós and Rédei. Chapter 13 (Densities) starts with a presentation of basics on probability spaces, and contains Kolmogorov’s extension theorem, as well as the formula of densities. Chapter 14 (Polynomials of finite codes) contains the proof and discussion of the theorem of the factorization of the polynomial of a finite maximal code. The book ends with the connection between maximal bifix codes and semisimple algebras. In the appendix the conjectures mentioned in the book and some additonal open problems are presented. Many examples are given which come from practical applications and illustrate the notions.

Each chapter is followed by a section of exercises, which frequently complement the material covered in the text. Solutions of some 200 exercises are proposed at the end of the book. Each chapter ends with notes containing references, bibliographic discussions, complementary material, and references for the exercises.

The book is a valuable contribution to the field. It may be used by researchers in coding theory, as well as a material for several courses, at various levels, in undergraduate or graduate curricula. Because of the extensive use of trees and of the corresponding algorithms and the properties of the structure of unambiguous monoids of relations, some chapters of this book and associated exercises might constitute an interesting complement to a programming course or to a course in algebra.

Reviewer: Ioan Tomescu (Bucureşti)

##### MSC:

94-00 | General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to information and communication theory |

94A60 | Cryptography |

94Bxx | Theory of error-correcting codes and error-detecting codes |

20M35 | Semigroups in automata theory, linguistics, etc. |