Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0587.68066
Berstel, Jean; Perrin, Dominique
Theory of codes. (English)
[B] Pure and Applied Mathematics, 117. Orlando etc.: Academic Press, Inc. XIV, 433 P. {\$} 60.00; \sterling 60.00 (1985).

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. \par 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 {\it 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. \par 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.
[C.Reutenauer]

MSC 2000:: *68Q45 Formal languages
68Q70 Algebraic theory of automata
68-01 Textbooks (computer science)
94-01 Textbooks (information and communication)
94A45 Codes in connection with formal languages
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups
20M12 Ideal theory of semigroups
20B20 Multiply transitive finite permutation groups
60B99 Probability theory on general structures
16S10 Associative rings determined by universal properties

Keywords: variable-length codes; algorithms; thin codes; prefix codes; deciphering delay; biprefix codes; syntactic approach; unambiguous automata; synchronization of semaphore codes; permutation groups; probabilistic approach; conjugacy; circular codes; factorization of free monoids; semisimple algebras

Cited in: Zbl 1187.94001 Zbl 1187.68297 Zbl 1199.94055 Zbl 0852.20058 Zbl 1023.68572 Zbl 0802.94012 Zbl 0818.20086 Zbl 0873.94010 Zbl 0798.68083 Zbl 0737.68049 Zbl 0675.20056 Zbl 0667.68080 Zbl 0649.68074 Zbl 0978.68079

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]