Theory of Codes
This is a volume in PURE AND APPLIED MATHEMATICS A Series of Monographs and Textbooks Editors: SAMUEL EILENBERG AND HYMAN BASS
A list of recent titles in this series appears at the end of this volume.
THEORY OF CODES
JEAN BERSTEL VniversitP Paris VI
DOMINIQUE PERRIN Vniversitk Paris V l l
1985
ACADEMIC PRESS, INC. (Harcourl Brace Jovanovlch, Publishers)
Orlando San Diego New York London Toronto Montreal Sydney Tokyo
COPYRIGHT@ 1985, BY ACADEMIC PRESS. INC. ALL RIGHTS RESERVED. NO PART O F THIS PUBLICATION MAY BE REPRODUCED OR TRANSMITTED IN ANY FORM OR BY ANY MEANS. ELECTRONIC OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR ANY INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT PERMISSION IN WRITING FROM THE PUBLISHER.
ACADEMIC PRESS, INC. Orlando, Florida 32887
United Kin om Edition ublished by
ACADEMG PRESS dc. (LONDON) LTD. 24/28 Oval Road, London NWI 7DX
Library of Congress Cataloging in Publication Data
Berstel, Jean, Date Theory of codes. and applied mathematics ; ) 11.Pure ibliO aphy: P. Codcg theory. I. Perrin. Domlnique.
11. Title. 111. Series: Pure and applled mathematics (Academlc
&?d0-12-093420-5 ' [ Q M h ] 510 s E519.4 (alk. paper] ISBN
PRINTEDIN THE UNITEDSTATESOP AMERICA
85868788
9 8 7 6 5 4 3 2 I
84-12445
to
Mahar
This Page Intentionally Left Blank
Contents
xi
PREFACE
CHAPTER
0
Preliminaries
0 1 2
9
Introduction Notation Monoids Words Automata Ideals in a Monoid Semirings and Matrices Formal Series Permutation Groups Notes
1
Codes
3 4 5
6 7 8
CHAPTER
Introduction Definitions Codes and Submonoids A Test for Codes Measure of a Code Complete Sets Composition Exercises Notes
1 1
2 4 10 18 26 29
32 36
37 37 42 50 54 61 71 78 81
CHAPTER
2
Prefix Codes
0 1 2 3 4 5 6 8 9 10
Introduction Prefix Codes The Automaton of a Prefix Code Maximal Prefix Codes Operations on Prefix Codes Semaphore Codes Synchronous Codes Average Length Deciphering Delay Exercises Notes
3
Biprefix Codes
7
CHAPTER
Introduction Parses Maximal Biprefix Codes Degree Kernel Finite Maximal Biprefix Codes Exercises Notes
CHAPTER
CHAPTER
4
Automata
0 1 2 3 4 5 6 7 8 9
Introduction Au toniata Flower Automaton Monoids of Unambiguous Relations Rank and Minimal Ideal Very Thin Codes Group and Degree of a Code Synchronization of Semaphores Exercises Notes
5
Groups of Biprefix Codes Introduction Group Codes Automata of Biprefix Codes Depth Groups of Finite Biprefix Codes Examples Exercises Notes
83 84 90 98 103 107 115 121 128 134 138
140 141 144 150 163 168 175 178
180 180
189 202 217 224 234 248 255 260
26 1 262 264 269 27 1 279 285 288
CONTENTS
CHAPTER
6
Densities
0 2 3 4 5
Introduction Densities Probabilities over a Monoid Contexts Exercises Notes
7
Conjugacy
0 1 2 3 4 5 6
7
Introduction Circular Codes Limited Codes Length Distributions Factorizations of Free Monoids Finite Factorizations Exercises Notes
8
Polynomial of a Code
0
Introduction Factorizing Codes Determinants State Space Evaluation of the Polynomials Proof of the Theorem Commutative Equivalence Complete Reducibility Exercises Notes
1
CHAPTER
CHAPTER
1
2 3 4 5 6
7 8 9
REFERENCES INDEX
290 290 296 309 318 320
32 1 322 329 337 35 1 364 374 377
379 380 382 385 394 398 404 408 418 422
424 429
This Page Intentionally Left Blank
Preface
The theory of codes takes its origin in the theory of information devised by Shannon in the 1950s. In the past thirty years, this theory has developed in several directions, one of which is the theory of entropy, a branch of probability theory. Another is the theory of error-correcting codes which is one of the beautiful applications of commutative algebra. This volume presents a comprehensive study of the theory of variable length codes, and provides a systematic exposition of the topic. The theory of codes, as presented here, uses both combinatorial and algebraic methods. Due to the nature of the questions raised and solved, this theory is now clearly a part of theoretical computer science and is strongly related to cornbinatorics on words, automata theory, formal languages, and the theory of semigroups. The object of the theory of codes is, from an elementary point of view, the study of the properties concerning factorizations of words into a sequence of words taken from a given set. Thus it is related to syntactic analysis, even though the connection seems loose at first glance. One of the basic techniques used in this book is constructing special automata that perform certain kinds of parsing. It is quite remarkable that the problem of encoding as treated here admits a rather simple mathematical formulation: it is the study of embeddings of one free monoid into another. We may consider this to be a basic problem of algebra. There are related problems in other algebraic structures. For instance, if we replace free monoids by free groups, the study of codes reduces to that of subgroups of a free group. However, the situation is quite different at the very beginning. In fact, according to the Nielsen-Schreier theorem, any subgroup of a free group is
xii
PREFACE
itself free, whereas the corresponding statement is false for free monoids. Nevertheless the relationship between codes and groups is more than an analogy, and we shall see in this book how the study of a group associated with a code can reveal some of its properties. It was M.P.Schutzenberger’s discovery that coding theory is closely related to classical algebra. He has been the main architect of this theory. The main basic results are due to him and most further developments were stimulated by his conjectures. The aim of the theory of codes is to give a structural description of the codes in a way that allows their construction. This is easily accomplished for prefix codes, as shown in Chapter 2. The case of biprefix codes is already much more difficult, and the complete structural description given in Chapter 3 is one of the highlights of the theory. However, the structure of general codes (neither prefix nor suffix) still remains unknown to a large extent. For example, no systematic method is known for constructing all finite codes. The result given in Chapter 8 about the factorization of the commutative polynomial of a code must be considered (despite the difficulty of its proof) as an intermediate step toward the understanding of codes. Many of the results given in this book are concerned with extremal properties, the interest in which comes from the interconnection that appears between different concepts. But it also goes back to the initial investigations on codes considered as communication tools. Indeed, these extremal properties in general reflect some optimization in the encoding process. Thus a maximal code uses, in this sense, the whole capacity of the transmission channel. Primarily, two types of methods are used in this book: direct methods on words and syntactic methods. Direct methods consist of a more or less refined analysis of the sequencing of letters and factors within a word. Syntactic methods, as used in Chapters 4-8, include the study of special automata associated with codes and of the corresponding monoids of relations. As usual during the preparation of a book, we had to make choices about the material to be covered. We have included mainly results concerning codes themselves. We have neglected in particular their relationship with varieties of languages and semigroups and also with free Lie algebras. We have not treated the developments leading toward ergodic theory. On the other hand, we have included results of combinatorial nature such as the description of comma-free codes or bisections and trisections of free monoids. There were other choices to be made, beyond terminology and notation which of course vary through the research papers. These concern the degree of generality of the exposition. It appears that many facts discovered for finite codes remain true for recognizable codes and even for a larger class of codes (thin codes) encountered in the literature. In general, the transition from finite to recognizable codes does not imply major changes in the proof. However, changing to thin codes may imply some rather delicate computations. This is clearly demonstrated in Chapters 4 and 6, where the summations to be made become infinite when the
PREFACE
xiii
codes are no longer recognizable. But this approach leads to a greater generality and, as we believe, to a better understanding by focusing attention on the main argument. Moreover, the characterization of the monoids associated with thin codes given in Chapter 4 may be considered to be a justification of our choice. The organizationof the book is as follows: A preliminary chapter (Chapter 0) is intended mainly to fix notation and should be consulted only when necessary. The book is composed of three major parts: part one consisting of Chapters 1-3, part two of Chapters 4-6, and part three of Chapters 7 and 8, which are independent of each other. Chapters 1-3 constitute an elementary introduction to the theory of codes in the sense that they primarily make use of direct methods. Chapter 1 contains the definition, the relationship with submonoids, the first results on measure, and the introduction of the notions of complete, maximal, and thin codes. Chapter 2 is devoted to a systematic study of prefix codes, developed at a very elementary level. Indeed, this is the most intuitive and easy part of the theory of codes and certainly deserves considerable discussion. We believe that its interest largely goes beyond the theory of codes. The chapter ends with the well-known theorem on deciphering delay. Chapter 3 is also elementary, although more dense. Its aims are to describe the structure of maximal biprefix codes and to give methods for constructing the finite ones. The use of formal power series is of great help. The presentation of the results, frequently scattered or unpublished, appears to be new. The next three chapters contain what is known about codes but can be proved only by syntactic methods. Chapter 4 is devoted to these techniques, using a more systematic treatment. Instead of the frequently encountered monoids of functions we study monoids of unambiguous relations which do not favor left or right. Chapter 4 concludes with a first illustration of these techniques: the proof of the theorem of synchronization of semaphore codes. Chapter 5 deals with the groups of biprefix codes. Chapter 6 shows how to compute the density of the submonoid generated by a code by transferring the computation into the associated monoid of unambiguous relations. The formula of densities, linking together the density of the submonoids, the degree of the code, and the densities of the contexts, is the most striking result. As previously mentioned, Chapter 7 is very combinatorial in nature. It contains for circular codes a systematic theory that leads to the study of the well-known comma-free codes. It is followed by the study of factorizations of a free monoid and more importantly of the characterizationof the codes that may appear as factors. Chapter 8 contains the proof and discussion of the theorem of the factorization of the polynomial of a finite maximal code. Many of the results of the preceding chapters are used in the proof of this theorem which contains the most current detailed information about the structure of general codes. The book ends with the connection between maximal biprefix codes and semisimple algebras. The book is written at an elementary level. In particular, the knowledge re-
XI\'
PREFACE
quired is covered by a basic mathematical culture. Complete proofs are given and the necessary results of automata theory or theory of semigroups are presented in Chapter 0. Each chapter is followed by an exercise section which frequently complements the material covered in the text. As is customary, difficult exercises are starred or double starred. The chapters end with notes containing references for the more important results, bibliographic discussions, complementary material, and references for the exercises. It seems impossible to cover the whole text in a one-year course; however, the book contains enough material for several courses, at various levels, in undergraduate or graduate curricula. Moreover, several chapters are largely independent and can be lectured on separately. As an example, we taught a course based solely on Chapter 7. In addition, a one-year lecture at the undergraduate level may be composed of Chapter 1, Chapter 2 without the last section, Chapter 3, and the first two sections of Chapter 4.The methods used there are all elementary and semigroup theory is not employed. Because of the extensive use of trees, Chapter 2 by itself might constitute an interesting complement to a course in the theory of programming. Chapters 4 and 5 , which rely on the structure of monoids of unambiguous relations, are an excellent illustration for a course in algebra. Similarly, Chapter 6 can be used as an adjunct to a course on probability theory. During the four years of preparation of this book, we have received help and collaboration from many people. It is a pleasure for us to express our thanks to them. First, several colleagues who offered to read preliminary versions of several chapters, discovered errors and suggested improvements and complements. We are greatly indebted to A. de Luca, G. Hansel, J.-E. Pin, C. Reutenauer, and A. Restivo. We also appreciated the invaluable help of S. W. Margolis and P. E. Schupp. Needless to say, we are greatly indebted to M.P. Schutzenberger. The project of writing this book stems from him and he has encouraged us constantly in many discussions. In addition, the typing of the manuscript, first in French then in English, involved the talents of Claudine Beaujean, Anne Berstel, Maryse Brochot, ZoC Civange, Martine Chaumard, Rosa De Marchi, and Arlette Dupont. Their help is gratefully acknowledged. Finally, this work was accomplished at the Laboratoire d'hformatique et Programmation, which provided moral and technical support.
CHAPTER
0
Preliminaries
0. INTRODUCTION
In this preliminary chapter, we give a short but complete account of some basic notions which will be used throughout the book. This chapter is not designed for a systematic reading but rather as a reference. The first three sections contain our notation and basic vocabulary. Each of the four subsequent sections is an introduction to a topic which is not completely treated in this book. These sections are concerned mainly with the theory of automata. Kleene’s theorem is given and we show how to construct a minimal automaton from a given automaton. Syntactic monoids are defined. These concepts and results will be discussed in another context in Chapter IV.
1. NOTATION As usual, N, Z, Q, 03, and C denote the sets of nonnegative integers, integers, and rational, real, and complex numbers, respectively. By convention, 0 E N. We set
R, = { x E R J X 2 0 } .
0 . PRELIMINARIES
2
Next, n!
(;)
= p!(n - p ) !
denotes the binomial coefficient of n and p. Given two subsets X, Y of a set 2,we define
x - Y = { z E Z l z E X , Z # Y}. An element x and the singleton set {x} will usually not be distinguished.The set of all subsets of a set X is denoted by Cp(X). The function symbols are usually written on the left of their arguments but with some exceptions: When we consider the composition of actions on a set, the action is written on the right. In particular, permutations are written on the right. A partition of a set X is a family (XJi., of nonempty subsets of X such that
(0 x = Ul.,Xi (ii) X, n X, = 0,
(i # j ) .
We usually define a partition as follows: “Let X =
UiE,Xi be a partition of
X.”We denote the cardinality of a set X by Card(X). 2. MONOIDS
A monoid is a set M equipped with an associativebinary operation and has a neutral element. The operation is usually written multiplicatively.The neutral element is unique and is denoted by 1, or simply by 1. For any monoid M, the set V ( M )is given a monoid structure by defining,for X,Y c M , XY = {xyIxEX,yE Y}. The neutral element is { 1). A submonoid of M is a subset N which is stable under the operation and which contains the neutral element of M NN c N, 1,
E
N.
(2.1) (2.2)
Note that a subset N of M satisfying (2.1) does not always satisfy 1, = 1, and therefore may be a monoid without being a submonoid of M. A morphism from a monoid M into a monoid N is a function cp:
M-iN
3
2. MONOIDS
which satisfies, for all m, m' E M , cpbm') = cp(m)cp(m'), and furthermore cp(1),
= .1,
A congruence on a monoid M is an equivalence relation 8 on M such that, for all m,m' E M,u,v E M m = m' mod 9 3 umv 3 um'v mod 8. Let cp be a morphism from M onto N . The equivalence 9 defined by m = m' mod 9 iff p(m) = cp(m') is a congruence. It is called the nuclear congruence induced by cp. Conversely,if 9 is a congruence on the monoid M , the set MI8 of the equivalence classes of 9 is equipped with a monoid structure, and the canonical function from M onto M / 9 is a monoid morphism. An idempotent of a monoid M is an element e of M such that e = e2. For each idempotent e of a monoid M, the set M(e) = eMe
is a monoid contained in M . It is easily seen that it is the largest monoid contained in M having e as a neutral element. It is called the monoid localized at e. It will sometimes be convenient to use the term semigroup to denote a set equipped with an associative operation but without the requirement of the existence of a neutral element. The notions of subsemigroup and semigroup morphism are then defined in the same way as the corresponding notions for monoids. Let M be a monoid. The set of (left and right) invertible elements of M is a group called the group of units of M . A cyclic monoid is a monoid with just one generator, i.e., M = {a"InE N}
with a' = 1. If M is infinite, it is isomorphic to the additive monoid N of nonnegative integers. If M is finite, the index of M is the smallest integer i 2 0 such that there exists an integer r 2 1 with =
(2.3) The smallest integer r such that (2.3)holds is called the period of M. The pair composed of index i and period p determines a monoid having i + p elements, Mi,p = { l,a, a',
...,ai-',a*, . ..,d'"-'}.
Its multiplication is conveniently represented in Fig. 0.1.
4
0. PRELIMINARIES
..
. *
Fig. 0.1 The monoid Mi,p.
The monoid Mi,p contains two idempotents (provided a # 1). Indeed, assume that ai = a'? Then either j = 0 or j 2 i and j and 2j have the same residue mod p, hence j = Omod p. Conversely, if j 2 i and j = Omodp, then I.
= a2j,
Consequently, the unique idempotent e # 1 in Mi,pis e = aj, where j is the unique integer in {i, i + 1,. . ,,i + p - I} which is a multiple of p . Let M be a monoid. For x,y E M , we define
1
and
x - 'y = { z E M xz = y}
I
xy - = { z E M x = zy}.
For subsets X , Y of M , this notation is extended to x-'y =
u
and
Ux-ly
XY-'=
xrXyoY
u uxy-'.
xeXyoY
The following identities hold for subsets X , Y, 2 of M :
(XY)-'Z = Y-'(X-'Z)
and
X-'(YZ-') =(X-'Y)Z-'.
Given a subset X of a monoid M , we define
F(X)= M - ' X M - ' to be the set of factors of elements in X . We have
F(X)=
{mE MI3u,uEM:umvEX}.
We sometimes use the notation F ( X )to denote the complement of F ( X )in M ,
F(X)= M - F(X). 3. WORDS
Let A be a set, which we call an alphabet. A word w on the alphabet A is a finite sequence of elements of A
w = (a1,a2,.
. .,a,),
a, E A.
3.
5
WORDS
The set of all words on the alphabet A is denoted by A* and is equipped with the associative operation defined by the concatenation of two sequences a,,
,an)(bl, b, , * * *
3
bm)
=
a,
9 .
*
>
an,b l , b,
9 * * * 3
bm).
This operation is associative. This allows us to write w = U,U,.*~U,,
instead of w = (a,, a,, . ..,a,,), by identifying each element a E A with the sequence (a). An element a E A is called a letter. The empty sequence is called the empty word and is denoted by 1. It is the neutral element for concatenation. Thus the set A* of words is equipped with the structure of a monoid. The monoid A* is called the free monoid on A. The set of nonempty words on A is denoted by A'. Thus we have A + = A*'- 1. The length IwI of the word w = alaz...anwith ai E A is the number n of letters in w. Clearly, 111 = 0. The function w H IwI is a morphism from A* onto the additive monoid N. For n 2 0, we use the notation A(,,)= {w E A* I IWI I n - 1)
and also A"" = { W EA*
I IwI
I n}.
In particular, A(') = 0 and At'] = { 1). For a subset B of A, we let Iwle denote the number of letters of w which are in B. Thus
For a word w E A*, the set alph(w) = {a E A I IwI, > 0} is the set of all letters occurring at least once in w. For a subset X of A*, we set alph(X) =
u alph(x).
xeX
A word w E A* is a factor of a word x E A* if there exist u, u E A* such that x = uwv.
The relation is a factor of is a partial order on A*. A factor w of x is proper if w # x. A word w E A* is a left factor of a word x E A* if there is a word u E A* such that x = wu. The factor w is called proper if w # x. The relation is a left factor of is again a partial order on A* called the prefix ordering. We write w I x when w is a left factor of x and w < x whenever w Ix and w # x. This order has the following fundamental property. If for some x, w I x, WI I x,
6
0 . PRELIMINARIES
then w and w‘ are comparable, i.e., or
w 5 w’
W ’ S w.
In other words, if uw = u’w’, then either there exists s E A* such that u = u‘s (and also sw = w‘) or there exists t E A* such that u’ = ut (and then w = tw’). In an entirely symmetric manner we define a right factor w of a word x by x = uw for some u E A*. A set P c A* is caHed prejx-closed if it contains the left factors of its elements: uu E P =$ u E P. A suffix-closed set is defined symmetrically. The reuerse w of a word w = ala2~-.a,,, ai E A, is
3 = a,***a2a1. The notations 3 and w - are equivalent. Note that for all u, u E A*, (uu)-=
5ii.
Thereuersezof a s e t X c A * i s t h e s e t z = {XIXEX}. A factorization of a word w E A* is a sequence(ul,u 2 , ...,u,) of n 2 0 words in A* such that w = U1U2”‘U,. For a subset X of A*, we denote by X* the submonoid generated by X,
x* = {x1x2”’x,Jn 2 O,XiEX}. Similarly, we denote by X + the subsemigroup generated by X,
X + = { x l x z * * - x , I n2 l,xiEX}. We have .+=r*-1
ifl#X, otherwise.
X*
By definition, each word w in X* admits at least one factorization .. .,x,) whose elements are all in X.Such a factorization is called an Xfactorization. We frequently use the pictorial representation of an Xfactorization given in Fig. 0.2. A word x E A* is called primitive if it is not a power of another word. Thus x is primitive iff x = y” with n 2 0 impliesx = y. Observe that the empty word is not primitive.
(xi, x2,
...
...
W
Fig. 0.2 An X-factorization of w.
3.
7
WORDS X
Fig. 0.3 Two conjugate words.
Two words x, y are called conjugate if there exists words u, u such that x = uu, y = uu. (See Fig. 0.3.) We frequently say that y is a conjugate of x. Two conjugate words are obtained from each other by a cyclic permutation. More precisely, let y be the function from A* into itself defined by and y(au) = ua (3.1) for a E A, u E A*. It is clearly a bijection from A* onto itself. Two words x and y are conjugate iff there exists an integer n 2 0 such that y(1) = 1
x = YYY). This easily implies that the conjugacy relation is an equivalence relation. A conjugacy class is a class of this equivalence relation.
F~OPOSITION 3.1 Each nonempty word is a power of a unique primitive word. Proof Let x E A and 6 be the restriction of the function y defined by (3.1) to the conjugacy class of x. Then 6' = 1 iff x is a power of some word of length k. Let p be the order of 6, i.e., the g.c.d. of the integers k such that 6' = 1. Since aP = 1,there exists a word r of length p such that x = re withe 2 1.The word r is primitive, otherwise there would be a word s of length q dividing p such that r E s*, which in turn implies that x E s*, contrary to the definition of p. This proves the existence of the primitive word. To show unicity, consider a word t E A*suchthatx~t*andletk = Itl.Sincedk = 1,theintegerkisamultipleof p. Consequently t E r*. Thus if t is primitive, we have t = r. 0 +
Let x E A +.The unique primitive word r such that x = r" for some integer n is called the root of x. The integer n is the exponent of x. We sometimes write I=&.
PROPOSITION 3.2 Two nonempty conjugate words have the same exponent and their roots are conjugate. Proof Let x, y E A + be two conjugate words, and let i be an integer such that y = y'(x). Set r = f i and s = f i and let x = r". Then y = y'(r")= (yi(r))".
8
0. PRELIMINARIES
TABLE 0.1 The Number l,(k) of Primitive Conjugacy Classes over a k-Letter Alphabet n
1
2
3
4
5
6
7
8
9
10
11
12
4(2) 1.Q)
2 3
1
6 48
9 116
18
30
56
99
186
335
1J4)
4
6
2 8 20
3
3
18
This shows that y'(r) E s*. Interchanging the roles of x and y , we have yJ(s) E r*. It follows that y'(r) = s and yJ(s) = r. Thus r and s are conjugate and consequently x and y have the same exponent. 0
PROPOSITION 3.3 All words in a conjugacy class have the same exponent. If C is a conjugacy class of words of length n with exponent e, then
Card(C) = n/e. Proof Let x E A" and C be its conjugacy class. Let 6 be the restriction of y to C and p be the order of 6. The root of x is the word r of length p such that x = re. Thus n = pe. Now C = { x ,6(x), . . .,dP- '(x)}. These elements are distinct since p is the order of 6.Thus Card(C) = p. 0 We now compute the number of conjugacy classes of words of given length over a finite alphabet. Let A be an alphabet with k letters. For all n 2 1, the number of conjugacy classes of primitive words in A* of length n is denoted by l,,(k). The notation is justified by the fact that this number depends only on k and not on A. The first values of this function, for k = 2,3,4, are given in Table 0.1. Clearly 1,(1) = 1 if n = 1, and 1,,(1) = 0, otherwise. Now for n 2 1
k"
= xdld(k), dln
where d runs over the divisors of n. Indeed, every word of length n belongs to exactly one conjugacy class of words of length n. Each class has d = n / e elements, where e is the exponent of its words. Since there are as many classes whose words have exponent n/e as there are classes of primitive words of length d = n/e, the result follows. 0 We can obtain an explicit expression for the numbers l,(k) by using the classical technique of Mobius inversion which we now recall. The Mobius function is the function p:
defined by
N - (0)
+N
3.
9
WORDS
and p(n) =
n is the product of [(-t)i ifotherwise.
i distinct prime numbers,
PROPOSITION 3.4 (Mobius Inversion Formula) Let a, B be two functions from N - (0)into N. Then
!f P(n) = C A d ) a ( n / d )
(n 2 1).
(3.4)
dln
Proof Define a product on the set Y of functions from N - {0}into N by setting, for f, g E 9,
c
f*s(n)= n = d e f ( d ) s ( e ) . It is easily verified that Y is a commutative monoid for this product. Its neutral element is the function 1 taking the value 1 for n = 1 and 0 elsewhere. Let I E Y be the constant function with value 1. Let us verify that (3.5) Indeed i * p ( l ) = 1; for n 2 2, let n = pflp",' * * p i mby the prime decomposition of n. If d divides n, then p ( d ) # 0 iff d = p y p ? . . .pftl" r*p=l.
with all li = 0 or 1. Then p ( d ) = (- 1)' with t = Zy'
l i . It follows that
Now let a, p E 9'.Then formula (3.3) is equivalent to a = I * p and formula (3.4) is equivalent to p = p * a. By (3.5) these two formulas are equivalent. 0 PROPOSITION 3.5 The number of conjugacy classes of primitive words of length n over an alphabet with k letters is In(k) =
1p(n/d)kd* dln
Proof
This is immediate from formula (3.2) by Mobius inversion. D
A word w E A + is called unbordered if no proper nonempty left factor of w is a right factor of w. In other words, w is unbordered iff
W E U A +n A + u
implies u = 1.
0. PRELIMINARIES
-- a --
U
blU I 0
Fig. 0.4 The word uablYI.
If w is unbordered, then wA* n A*w = WA*Wu W. The following property holds.
PROPOSITION 3.6 Let A be an alphabet with at least two letters. For each word u E A', there exists v E A* such that uv is unbordered. Proof Let a be the first letter of u, and let b E A - a. Let us verify that the word w = uabl"1 is unbordered (Fig. 0.4). A nonempty left factor t of w starts with the letter a. It cannot be a right factor of w unless It1 > lul. But then we have t = sabl"l for some s E A*, and also t = uablSI.Thus Is1 = IuI, hence t=w. 0 Let A be an alphabet. The free group A@on A is defined as follows: Let an alphabet in bijection with A and disjoint from A. Denote by
be
UHii the bijection from A onto A. This notation is extended by setting, for all UEAUA,
-
a = a. Let 6 be the symmetric relation defined for u, v E ( A u A)* and a E A u
A by
uaiiv = uv mod 6. Let p be the reflexive and transitive closure of 6. Then p is a congruence. The quotient A@= ( A u A)*/p is a group. Indeed, for all a E A u 2, aZ E 1 mod p, Thus the images of the generators are invertible in
[email protected] group A@is called the free group on A. 4. AUTOMATA
Let A be an alphabet. An automaton over A is composed of a set Q (the set of states), a subset I of Q (the initial states), a subset T of Q (the terminal or final states), and a set 9 c Q x A x Q
4.
AUTOMATA
called the set of edges. The automaton is denoted by = (Q,I, T )
The automaton isjnite when the set Q is finite. A path in the automaton d is a sequence c = (fl ,f2,. edges f;: = (qi,ai,qi+l), 1 Ii I n.
. .,f,,)of consecutive
The integer n is called the length of the path c. The word w = ala2 ...a,, is the label of the path c. The state q1 is the origin of c, and the state q,,+ the end of c. A useful notation is W
c:
41-
4n+l.
By convention, there is, for each state q E Q, a path of length 0 from q to q. Its label is the empty word. A path c: i + t is successful if i E I and t E 'I: The set recognized by d , denoted by L ( d ) ,is defined as the set of labels of successful paths. A state q E Q is accessible (resp. coaccessible) if there exists a path c: i + q with i E I (resp. a path c: q + t with t E T). An automaton is trim if each state is both accessible and coaccessible. Let P be the set of accessible and coaccessible states, and let d o=L (P,I n P, T n P).Then it is easy to see that d ois trim and L ( d )= L(d"). An automaton d = (Q,I, T) is deterministic if Card(1) = 1 and if (p,a,q),( p , a , r )E L F
*
4 = r.
Thus for each p E Q and a E A, there is at most one state q in Q such that p L q . For p E Q, and a E A, define
The partial function QxA+Q defined in this way is extended to words by setting, for all p
E
Q,
P . 1 =p,
and, for w E A*and a E A, p wa = ( p * w) a. 9
This function is called the transitionfunction or next-state function of d.With this notation, we have with I = { i } ,
-
L ( d ) = { w E A* I i w E T } .
0. PRELIMINARIES
I2
An automaton is complete if for all p such that p p_ q.
E
Q,a E A, there exists at least one q E Q
PROPOSITION 4.1 For each automaton d,there exists a complete deterministic automaton 93 such that L ( d ) = L(W). If d isfinite, then 9 can be chosen to befinite.
Proof
Set d = (Q,I, T). Define 9 = (R, u, V )by setting R = Y(Q),u = I , V = {S c QlS n T #
0).
Define the transition function of 9,for S E R, a E A by S - a = {qEQ13sES:s-P--,q}.
The automaton W is complete and deterministic. It is easily seen that L ( d ) = L(W). 0 Let d = (Q,i, T ) be a deterministic automaton. For each q E Q,let
L,
= {w E A * l q
w
E
T}.
Two states p, q E Q are called inseparable if L, = L,;
they are separable otherwise. A deterministic automaton is reduced if two distinct states are always separable. Let X be a subset of A*. We define a special automaton d ( X ) = (Q,i, T ) in the following way. The states of d ( X )are the nonempty sets
u-'x for u E A*. The initial state is X = l-'X, and the final states are those containing the empty word. The transition function is defined for a state Y = u- ' X and a letter a E A by Yea = a-'X
Observe that this indeed defines a partial function. We have
L(d(X)) = x. Indeed, an easy induction shows that for w E A*
x
w = w-'x.
Consequently
WEL(d(X))0 1EX.W
0
lEw-'X
0
WEX.
4.
AUTOMATA
'3
The automaton d ( X ) is reduced. Indeed, for Y = u 'X, L y = {VEA*I Y . V
E
T }= {MA*
UV
E
X}.
Thus Ly = Y. The automaton d ( X ) is called the minimal automaton of X. This terminology is justified by the following proposition.
PROPOSITION 4.2 Let d = (Q, i, T )be a trim deterministic automaton and let X = L ( d ) . Let d ( X ) = (P,j , S) be the minimal automaton of X . The function from Q into P defined by cp:
q+L,
is surjective and satisfies
.
cp(4 ' a) = cp(d a.
Proof
Let q E Q. Let u E A* such that i u = q. Then
I .
L, = { w E A* q w E T } = u-'x. Since d is trim, L, # 0.This shows that L, E P. Thus cp is a function from Q into P. Next, let us show that cp is surjective. Let u-'X E P. Then u-'X # 0. Thus u # 0 and setting q = i u, we have L, = u-'X = cp(q). Thus cp is surjective. Finally, for q = i u, q ( q . a) = L,.a = (ua)-'X = (u-lx). a = L, a. 0
Assume furthermore that the automaton d in the proposition is reduced. Then the function cp is a bijection, which identifies d with the minimal automaton. In this sense, there exists just one reduced automaton recognizing a given set. Let d = (Q, i, T ) be a deterministic automaton. Consider the set 9-of partial functions from Q into Q. These functions are written on the right: if q E Q and m E F,then the image of q by m is denoted by qm. Composition is defined by dmn) = (qm)n. Thus F has a monoid structure. Let cp be the function which to a word w E A* associates the partial function from Q into Q defined by qcpw = 4 * w.
'4
0. PRELIMINARIES
The function cp is a morphism from A* into the monoid 9. The submonoid cp(A*)of F is called the transition monoid of the automaton d. Observe that, setting X = L ( d ) ,we have
q-'cp(X)= x. (4.1) Indeed w E cp-'cp(X)iff q(w)E cp(X)which is equivalent to icp(w)E ?: i.e., to WEX. A morphism cp from A* onto a monoid M is said to recognize a subset X of A* if
q-'cp(X)= x. Let X be a subset of A*. For w E A*, set
I
T(w)= {(u, U) E A* x A* uwu E X}. The syntactic congruence of X is the equivalence relation ox on A* defined by
w
= W'
mode, o r(w) = T(w').
It is easily verified that ox is a congruence. The quotient of A* by ox is, by definition, the syntactic monoid of X.We denote it by A(X), and we denote by q x the canonical morphism from A* onto A(X).
PROPOSITION 4.3 Let X be a subset of A*, and let cp: A* + M be a surjective morphism. If cp recognizes X,then there exists a morphism $from M onto the syntactic monoid A ( X ) such that cpx = * O c p .
Proof
It suffices to show that
cp(w) = cp(w') * c p x w = cpx(w'). (4.2) Indeed, if (4.2) holds, then for an element m E M, $(m) is defined as the unique element in cpx(rp- '(m)).To show (4.2), we consider (u, u) E r(w).Then uwv E X. Thus q(u)cp(w)cp(u)E cp(X).From cp(w) = cp(w'), it follows that cp(u)cp(w')cp(v) E cp(X).Since cp recognizes X, this implies that uw'u E X . Thus (u,u) E r(w'). 0 PROPOSITION 4.4 Let X be a subset of A*. The syntactic monoid of X is isomorphic to the transition monoid of the minimal automaton d(X). Proof Let M be the transition monoid of the automaton d(X)= (Q, i, T ) and let cp: A* + M be the canonical morphism. By (4.1), the morphism cp recognizes X.By Proposition 4.3, there exists a morphism $ from M onto the syntactic monoid A(X)such that cpx = $ 0 cp.
4.
15
AUTOMATA
+
It suffices to show that is injective. For this, consider m,m’ E M such that $(m) = $(m’). Let w, w‘ E A* such that cp(w) = m, cp(w’) = m‘. Then cpx(w) = cpx(w’). To prove that cp(w) = ~ ( w ’ )we , consider a state p E Q, and let u E A* be such that p = u - ‘ X . Then
I
p c p ( ~= ) p w = (uw)- ‘ X = {U E A* (u,0 ) E T(w)}.
Since T(w)= r(w’), we have pcp(w) = pcp(w’). Thus ~ ( w=) cp(w’), i.e.,
m = m’. 0 We now turn to the study of properties which are specificto finite automata.
THEOREM 4.5 Let X
c A*. The following conditions are equiualent.
(i) The set X is recognized by a finite automaton. (ii) The minimal automaton d ( X ) is finite. (iii) The family of sets u-
‘x,
for u E A*, is finite. (iv) The syntactic monoid A ( X ) is finite. (v) The set X is recognized by a morphism ffom A* onto a finite monoid. Proof (i)=$ (ii) Let d be a finite automaton recognizingX.By Proposition 4.1, we can assume that d is deterministic. By Proposition 4.2, the minimal automaton d ( X ) also is finite.
(ii) e (iii) is clear. (ii) =$ (iv)holds by Proposition 4.4 and by the fact that the transition monoid of a finite automaton is always finite. (iv) =$ (v) is clear. (v) =. (i) Let cp: A* + M be a morphism onto a finite monoid M ,and suppose that cp recognizes X. Let d = (M,l,cp(X)) be the deterministic automaton with transition function defined by
.
m a = mcp(a). Then 1 w E cp(X) iff cp(w)E cp(X), thus iff w E X . Consequently L ( d ) =
x.
0
A subset X of A* is called recognizable if it satisfies one of the equivalent conditions of Theorem 4.5.
PROPOSITION 4.6 The family of recognizable subsets of A* is closed under all boolean operations: union, intersection,complementation. Proof Let X , Y c A* be two recognizable subsets of A*. Let d = (P,i, S ) and 1 = (Q, j , T ) be complete deterministic automata such that X = L ( d ) ,
16
0. PRELIMINARIES
Y = L ( 1 ) . Let %' = ( P x
Q, (i,A, R)
be the complete deterministic automaton defined by ( p , q) a = ( p a, q a).
For R = (S x Q ) u (P x T), we have L(%) = X u Y. For R = S x T, we have L(W) = X n Y. Finally, for R = S x (Q - T), we have L(W) = x-Y. 0 Consider now a slight generalization of the notion of automaton. An asynchronous automaton on A is an automaton d = (Q,I, T), the edges of which may be labeled by either a letter or the empty word. Therefore the set of its edges satisfies 9 c Q x ( A u1) x Q. The notions of a path or a successful path extend in a natural way so that the notion of the set recognized by the automaton is clear.
PROPOSITION 4.7 For any finite asynchronous automaton d,there exists a finite automaton a such that L ( d ) = L(i3). Proof Let d = ( Q , I , T ) be an asynchronous automaton. Let 9 = (Q,I, T) be the automaton, the edges of which are the triples (p, a, q) such that there exists a path p A q in d.We have
L ( d ) n A + = L(a)n A'. If I n T # 0,both sets L ( d ) and L(@) contain the empty word and are therefore equal. Otherwise, the sets are equal up to the empty word and the result follows from Proposition 4.6 since the set { l} is recognizable. 0 The notion of an asynchronous automaton is useful to prove the following result.
PROPOSITION 4.8 I f X c A* is recognizable, then X* i s recognizable. If X,Y c A* are recognizable, then XY is recognizable. Proof Since X* = (X - 1)* and since X - 1 is recognizable, we may suppose that 1 # X.Let d = (Q,I, T) be a finite automaton recognizing X.Let 9 be the set of its edges. Since 1 # X,we have I n T = 0.Let = (Q, I, T) be the asynchronous automaton with edges 9 u (T x 11) x I).
Then L(i3)= X'. In fact, the inclusion X* - 1 c L(1)is clear. Conversely, let c: i 4j be a successful path in A?, By the definition of 1, this path has the
4.
‘7
AUTOMATA
form i l W 1 - t l + i 12 W 2 ‘ t 2 * . . in -%t n with i = i,, j = tn and where no path ck: ik5t k contains an edge labeled by the empty word. Then wl, w2,. ..,wn E X and therefore w E X’. Now let d = (P,I, S ) and L3i’ = (Q, J , T) be two finite automata with sets of edges 4t and Q, respectively. Let X = L ( d ) and let Y = L(9Y). One may assume that P n Q = 0.Let %? = (P u Q,I,T) be the asynchronous automaton with edges c:
4t u Q u (S x (1) x J ) .
Then L(%) = XY as we may easily check. 0 We shall now give another characterization of recognizable subsets of A *. Let M be a monoid. The family of rational subsets of M is the smallest family 9t of subsets of M such that (i) any finite subset of M is in W, (ii) ifX, Y E 9 , t h e n X u Y E W a n d X Y E 9 , (iii) if X E 9,then X* E 9.
THEOREM 4.9 Let A be a jinite alphabet. A subset of A* is recognizable iff it is rational. Proof Denote by Rec(A*) the family of recognizable subsets of A * and by Rat(A*) that of rational subsets of A*. Let us first prove the inclusion Rat(A*) c Rec(A*). In fact, any finite subset X of A* is clearly recognizable. Moreover, Propositions 4.6 and 4.8 show that the family Rec(A*) satisfies conditions (ii) and (iii) of the definition of Rat(A*). This proves the inclusion. To show that Rec(A*) c Rat(A*), let us consider a recognizable subset X of A*. Let d = (Q, I, T) be a finite automaton recognizing X. Set Q = {1,2,...,n } a n d f o r l I i , j ~ n ,
Xi,j = {w E A* I i L j } . We have
x=
u u xi,j. iE1j E T
It is therefore enough to prove that each X,,is rational. For k E {0,1,. ..,n}, denote by XIS the set of those w E A * such that there exists a path c: i “j passing only through states 1 I k except perhaps for i, j. In other words we have w E Xrfij’iff w = a,a,--.a,with c: i L i , - az t2*..i,,,-l5 j
18
0. PRELIMINARIES
and i , I k,.. .,i,-
5
k. We have the formulas X'O' i.j C A u 1,
(4.3)
x13 = xi,,
(4.4)
Xlk+ 1 ) = XW i,j v X(k) r.k+1(XJrk!l,k+l )*XW k+l.j J
(O
< n)'
(4*5)
Since A is finite, Xi!j E Rat(A*) by (4.3). Then (4.5) shows by induction on E Rat(A*). Therefore X,, E Rat@*) by (4.4). 0
k 2 0 that Xi:]
5. IDEALS IN A MONOID
Let M be a monoid. A right ideal of M is a nonempty subset R of M such that RMcR or equivalently such that for all r E R and all m E M , we have rm E R . Since M is a monoid, we then have RM = R because M contains a neutral element. A left ideal of M is a nonempty subset L of M such that M L c L. A two-sided ideal (also called an ideal)is a nonempty subset I of M such that
MIM c I .
A two-sided ideal is therefore both a left and a right ideal. In particular, M itself is an ideal of M . An element 0 of M is a zero if 0 # 1 and for all m E M Om = mO = 0. If M contains a zero it is unique and the set (0) is a two-sided ideal which is contained in any ideal of M. An ideal 1 (resp., a left, right ideal) is called minimal if for any ideal J (resp., left, right ideal) J c Z => J = I . If M contains a minimal two-sided ideal, it is unique because any nonempty intersection of ideals is again an ideal. If M contains a 0, the set (0)is the minimal two-sided ideal of M.An ideal I # 0 (resp., a left, right ideal) is then called 0-minimal if for any ideal J (resp., left, right ideal) Jcl
=S
J=O
For any m E M , the set
R=mM
or
J=I.
5.
19
IDEALS IN A MONOID
is a right ideal. It is the smallest right ideal containing m. In the same way, the set
L=Mm is the smallest left ideal containing m and the set I = MmM
is the smallest two-sided ideal containing m. We now define in a monoid M four equivalence relations 9,Y,f and 2 as
m9m'
iff
mM = m ' M ,
mYm'
iff
M m = Mm',
mfm'
iff
MmM=Mm'M,
mXm'
iff
mM = m ' M
and M m = Mm'.
Therefore, we have for instance, d m ' iff there exist u, u' E M such that
m' = mu,
m = m'u'.
We have W c f , Y c f , and &' = W n 8.
PROPOSITION 5.1 The two equivalence W and 14 commute:
BY
= 99.
Proof Let m, n E M be such that m W f i . There exists p p Y n (see Fig. 0.5).
E
M such that
&p,
There exist by the definitions, u, u', u, u' n = up, p = v'n.
EM
Fig. 0.5 419 = 9 4 1 .
such that p = mu, m = pu',
0. PRELIMINARIES
20
Set q = urn. We then have q = um = u(pu’) = (up)u’ = nu’, n = up = u(mu) = (um)u = qu.
This shows that qWn. Furthermore, we have
m = pu’ = (u’n)u’ = u’(nu’)= u’q. Since q = urn by the definition of q, we obtain m Y q . Therefore m Y q W n and consequently rnYWn. This proves the inclusion 82’c 9%’ The . proof of the converse inclusion is symmetrical. 0 Since W and Y commute, the relation 9=WY=YW is an equivalence relation. We have the inclusions x c 9,Y c 9 c y. The classes of the relation 9,called 9-classesYcan be represented by a schema called an “egg-box” as in Fig. 0.6. The W-classes are figured by rows and the Y-classes by columns. The squares at the intersection of an W-class and an Y-class are the X-classes. We denote by L(m), R(m), D(m), H(m), respectively, the 9, W,9, and Af‘ classes of an element m E M.We have
H(m) = R(m) n L(m)
and
R(m), L(m) c D(m).
PROPOSITION 5.2 Let M be a monoid. Let rn, m’ E M be W-equivalent. Let u, u’ E M be such that
m = m’u‘,
m’ = mu.
Fig. 0.6 A %class.
5.
21
IDEALS IN A MONOID
The mappings pu: q -P qu,
pu,: q’ -+q’u’
are bijections from L(m) onto L(m’) inverse to each other. Moreover they preserve 9’-classes. Proof We first verify that p,, maps L(m) into L(m’). If q E L ( r n ) , then Mq = M m and therefore M q u = Mmu = Mm‘. Hence qu = p,,(q) is in L(m’). AnaIogously, putmaps L(m’)into L(m). Let q E L(m)and compute p,,p,,.(q).Since q Y m , there exist v, v’ E M such that q = urn, m = v‘q (see Fig. 0.7). We have p,p,,.(q) = quu‘ = (urn)uu’ = o(mu)u’ = vm’u’ = vm = q,
This shows that pupu.is the identity on L(m). We show in the same way that pup,,. is the identity on L(m’). Finally, since quu’ = q for all q E L(m), the elements q and pu(q) are in the same W class. 0 Proposition 5.2 has the following consequence which justifies the regular shape of Fig. 0.7.
PROPOSITION 5.3 Any two &-classes contained in the same .%class have the same cardinality. 0 We now come to the point of locating the idempotents in an ideal. The first result describes the &‘-class of an idempotent.
Fig. 0.7 The reciprocal bijections.
0. PRELIMINARIES
22
PROPOSITION5.4 Let M be a monoid and let e E M be an idempotent. The 2-class of e is fhe group of units of the monoid. M(e) = eMe. Proof
Let m E H(e).Then, we have for some u, u’, u, u’
e = mu,
m = eu‘,
e = om,
E
M
m = v’e.
Therefore em = e(eu’) = eu’ = m and in the same way me = m. This shows that m E M(e). Since
m(eue) = mue = e,
(eue)m= eum = e.
the element m is both right and left invertible in M. Hence, m belongs to the group of units of M(e).Conversely, if m E M(e)is right and left invertible, we have mu = um = e for some u, u E M(e).Since m = em = me, we obtain m 2 e . 0
PROFQSITION 5.5 An 2-class of a monoid M is a group iff it contains an idempotent. Proof Let H be an 2-class of M. If H contains an idempotent e, then H = H(e)is a group by Proposition 5.4. The converse is obvious. 0 PROPOSITION5.6 Let M be a monoid and m,n E M. Then mn E R(m) n L(n)
zfl
R(n) n L(m)contains an idempotent. Proof
If R(n) n L(m)contains an idempotent e, then
e = nu,
n = eu’,
e = urn,
m = v’e
for some u, u’, u, u‘ E M. Hence mnu = m(nu) = me = (u’e)e= u’e = m so that mnWm. We show in the same way that mnYn. Hence mn E R(m) n L(n). Conversely,if mn E R(m) n L(n),then m d m and nYmn. By Proposition 5.2 the multiplication on the right by n is a bijection from L(m)onto L(mn).Since n E L(mn), this implies the existence of e E L(m) such that en = n. Since n preserves W classes, we have additionally e E R(h). Hence there exists u E M such that e = nu. Hence
nunu = enu = nu and e = nu is an idempotent in R(n) n L(rn). 0
5.
IDEALS IN A MONOID
23
PROPOSITION 5.7 Let M be a monoid and let D be a %class of M . The following conditions are equivalent. (i) D contains an idempotent. (ii) Each W-class of D contains an idempotent. (iii) Each 9-class of D contains an idempotent. Proof Obviously, only (i)*(ii) requires a proof. Let e E D be an idempotent. Let R be an 9 class of D and let n E L(e) n R. (See Fig. 0.8). Since n z e , there exist v, v' E M such that
n = ve,
e = u'n.
Let m = ev'. Then mn = e because
mn = (ev')n = e(v'n) = ee = e. Moreover, we have m 9 e since mn = e and m = ev'. Therefore, e = mn is in R(m)n L(n). This implies, by Proposition 5.6, that R contains an idempotent. 0 A %class D satisfying one of the conditions of Proposition 5.7 is called regular.
PROPOSITION5.8 Let M be a monoid and let H be an %'-class of M . The two following conditions are equivalent. (i) There exist h, h' E H such that hh'
E
H.
(ii) H is a group. Proof (i)*(ii) If hh' E H, then by Proposition 5.6, H contains an idempotent. By Proposition 5.5, it is a group. (ii) * (i) is obvious. 0 We now study the minimal and O-minimal ideals in a monoid. Recall that if
M contains a minimal ideal, it is unique. However, it may contain several @minimal ideals.
rn
Fig. 0.8 Finding an idempotent in R.
24
0. PRELIMINARIES
Let M be a monoid containing a zero. We say that M is prime if for any m, n E M - 0, there exists u E M such that mun # 0. PROPOSITION 5.9 Let M be a prime monoid. 1. I f M contains a O-minimal ideal, it is unique. 2. If M contains a O-minimal right (resp., left) ideal, then M contains a O-minimal ideal; this ideal is the union of all minimal right (resp. left) ideals of M . 3. I f M both contains a O-minimal right ideal and a O-minimal lefi ideal, its O-minimal ideal is composed of a regular %class and zero.
Proof 1. Let I, J be two O-minimal ideals of M. Let m E I - 0 and let n E J - 0. Since M is prime, there exist u E M such that mun # 0. Then mun E I n J implies I n J # 0. Since I n J is an ideal, we obtain I n J = I = J . 2. Let R be a O-minimal right ideal. We first show that for all m E M , either m R = (0) or the set mR is a O-minimal right ideal. In fact, m R is clearly a right ideal. Suppose m R # 0 and let R' # 0 be a right ideal contained in mR. Set S = { r E R I mr E R'}.Then R' = mS and S # (0) since R' # {O}. Moreover, S is a right ideal because R' is a right ideal. Since S c R , the fact that R is a O-minimalright ideal implies the equality S = R. This shows that m R = R' and consequently that m R is a O-minimal right ideal. Let I be the union of all the minimal right ideals. It is a right ideal, and by the preceding discussion, it is also a left ideal. Let J # (0) be an ideal of M . Then for any O-minimal right ideal R of M , R J c R n J c R. We have RJ # (0) since for any r E R and m E J - 0, there exists u E M such that rum # 0 whence rum E R J - { 0). Since R is a O-minimal right ideal and R n J is a right ideal distinct from {O}, we have R n J = R. Hence R c J. This shows that I c J. Hence I is contained in any nonzero ideal of M and therefore is the O-minimal ideal of M . 3. Let I be the O-minimal ideal of M. Let m, n E I - (0). By 2 the right ideal mM and the left ideal M n are O-minimal. Since M is prime, there exists u E M such that mun # 0. The right ideal mM being O-minimal, we have mM = munM and therefore mgmun. In the same way, rnun9n. Hence we have m 9 n . This shows that I - (0) is contained in a %class. Conversely, if m E 1 - {0), n E M and m g n , there exists a k E M such that mM = k M and M k = Mn. Hence MmM = M k M = M n M and this implies n E I - (0). This shows that I - (0) is a 9-class. Let us show that I - (0) is a regular .%class. By Proposition 5.7, it is enough to prove that I - (0) contains an idempotent. Let m, n E I - (0).
5.
IDEALS IN A MONOID
25
Since M is prime, there exists u E M such that mun # 0. Since the right ideal mM is 0-minimal and since mun # 0, we have mM = muM = munM. Whence mun E R(mu). Symmetrically, since Mn is a 0-minimal left ideal, we have M n = Mun = Mmun, whence mun E L(n). Therefore mun E R (mu)n L(n)and by Proposition 5.6, this implies that R(n)n L(mu) contains an idempotent. This idempotent belongs to the 9 class of m and n and therefore to I - (0). 0 COROLLARY 5.10 Let M be a prime monoid. If M contains a 0-minimal right ideal and a 0-minimal left ideal, then M contains a unique 0-minimal ideal I which is the union of all the 0-minimal right (resp., left) ideals. %is ideal is composed with*a regular 9 class and 0. Moreover, we have the following computational rules. 1. For m E I - ( 0 ) and n E M such that mn # 0, we have
m9mn. 2. For m E I
- { 0)
and n E M such that nm # 0, we have mYnm.
3. For any &' class H c I
-
( 0 ) we have
H ~ = H or
H2 = (0).
Proof The first group of statements is an easy consequence of Proposition 5.9. Let us prove 1. We have mnM c mM. Since mM is a 0-minimal right ideal and mn # 0, this forces the equality mnM = mM. The proof of 2 is symmetrical. Finally, to prove 3, let us suppose H Z # (0). Let h, h' E H be such that hh' # 0. Then, by 1 and 2, hWhh' and h'Yhh'. Since h 9 h ' and h'yhh', we have hYhh'. Therefore hh' E Hand H i s a group by Proposition 5.8. 0 We finally give the statements corresponding to Proposition 5.9 and Corollary 5.10 for minimal ideals instead of 0-minimal ideals. This is of course of interest only in the case where the monoid does not have a zero.
PROPOSITION 5.1 1 Let M be a monoid. 1. If M contains a minimal right (resp., left) ideal, then M contains a minimal ideal which is the union of all the minimal right (resp., lest) ideals. 2. If M contains a minimal right ideal and a minimal left ideal, its minimal ideal I is a .%class. All the &'-classes in I are groups.
Proof
Let 0 be an element that does not belong to M and let
M0=MuO be the monoid whose law extends that of M in such a way that 0 is a zero. The monoid Mo is prime.
26
0 . PRELIMINARIES
An ideal I (resp., a right ideal R,a left ideal L ) of M is minimal iff I u {0} (resp., R u {0}, L u (0))is a 0-minimal ideal (resp., right ideal, left ideal) of Mo, Moreover the restriction to M of the relations W ,9,9,&' in Mo coincide with the corresponding relations in M. Therefore statements 1 and 2 can be deduced from Proposition 5.9 and Corollary 5.10. 0 COROLLARY 5.12 Let M be a monoid containing a minimal right ideal and a minimal left ideal. 'Ihen M contains a minimal ideal which is the union of all the minimal right (resp., left) ideals. 'Ihis ideal is a 9 class and all its &' classes are groups. 0 6. SEMIRINGS AND MATRICES
A semiring K is a set equipped with two operations denoted + and * satisfying the following axioms: (i) The set K is a commutative monoid for + with a neutral element denoted 0. (ii) The set K is a monoid for multiplication with a neutral element denoted by 1. (iii) Multiplication is distributive on addition. (iv) For all x E K, 0 x = x 0 = 0.
-
-
Clearly, any ring with unit is a semiring. Other examples of semirings are as follows. The boolean semiring 93 is composed of two elements 0 and 1. The axioms imply o + 1 = 1 + o = 1, o+o=o, 0 . 1 = 1 . 0 = 0 ~ 0 = 0 , 1.1 = l . is specified by 1+1=1. The other possibility, viz., 1 + 1 = 0, defines the field 2/22. M is the semiring of natural integers and R, is the semiring of nonnegative real numbers. For any monoid M, the set Cp(M)is a semiring for the operations of union and set product.
The semiring
A semiring K is called ordered if it is given with a partial order Isatisfying the following properties: (i) 0 is the smallest element of K; (ii) the following implications hold: x s y
x
sy
*
x+zsy+z, xz I y z , zx I zy.
6.
SEMIRINGS AND MATRICES
27
The semirings a, N, 88 + ,are ordered by the usual ordering. x s y
x=y+z.
An ordered semiring is said to be complete if any subset X of K admits a least upper bound in K. It is the unique element k of K such that (i) x ~ X = t - x ~ ; k , (ii) if x I; k' for all x E X , then k I k'.
We denote k = sup(X) or k = sup{x I x E X } or k = supxex(x). Semiring a is complete. Semirings N, R, are not complete. They may be completed according to the following general procedure: Let K be an ordered semiring whose order is total. Let
X=Kum, where co # K. The operations of K are extended to X by setting for x
E
K,
(i) x + c o = c o + x = c o , (ii) if x # 0; then xco = cox = co, (iii) coco = co,000 = 000 = 0.
Extending the order of K to X by x I; co for all x E K, the set X becomes a totally ordered semiring. It is a complete semiring because any subset has an upper bound and therefore also a least upper bound. We define N=Nuco,
W,=R,wco
to be the complete semirings obtained by applying this construction to N and 88,. If X is a complete semiring, the sum of an infinite family of elements of X is defined by
c xi
= sup
iol
c xjI J
c I, J finite
{jeJ
In the case of semiringW , ,this gives the usual notion of a summablefamily: A family (xi)ielof elements in R, is summable if sum (6.1) is finite. In particular, for a sequence ( x , ) , , ~of elements of a complete semiring, we have nLO
x , = sup
c xi }
nLO{is,
(6.2)
since any finite subset of N is contained in some interval { O , l , ...,n}. Moreover, if I = u j E lj is a partition of I , then J
c xi c (c
iol
=jsJ
ioljXi).
(6.3)
28
0. PRELIMINARIES
Consider, for instance, a mapping n:A*
+ R+
. Let X be a subset of A* and let
X, = { X E X l l x l In}. Then
c
xsx
=sup( ntO
.(X)
c n(x)}.
xsX.
Formulas (6.1)-(6.3) lead to results of the following kind:
PROPOSITION 6.1 Let rE
(u,,),,~ be a sequence of elements of R,
R+,
. Let, for
c anrn.
a(r) =
ntO
If a(r) < co for r E [0,1[, then sup{a(r)1 r E [O, I[} = a(1). Proof The mapping a: r H a(r) from R, into R, is nondecreasing. By successive applications of (6.2), (6.3), and then (6.2), we have
sup{a(r)I r E [0, I[} = sup = sup(
sup
1air')
rc[O.l[ i S a
ntO
c
= SUP( n 2 0 i s n 4)
=
c
a, = a(1).
ntO
0
Let P, Q be two sets and let K be a semiring. A P x Q-matrix with coefficients in K is a mapping m:
P x Q+K.
We denote indistinctly by
(p,m,q) or mp.4 the value of m on ( p , q) E P x Q. We also say that m is a K-relation between P and Q.If P = Q, we say that it is a K-relation ouer Q. The set of all K-relations between P and Q is denoted by KP Let m E K P x Qbe a K-relation between P and Q. For p E P, the row of index p of m is denoted by mp*. It is the element of K Q defined by Q.
(mp)q
= mpq.
7.
29
FORMAL SERIES
Similarly, the column of index 4,of m is denoted by w qIt . is an element of K P . Let P , Q, R be three sets and let K be a complete semiring. Form E K P and n E K Q'R, the product rnn is defined as the following element of K P '. Its value on ( p , r ) E P x R is
When P = Q = R, we thus obtain an associative multiplication which turns K Q'Q into a monoid. Its identity is denoted I,. A monoid of K-relations over Q is a submonoid of K Q'Q. It contains in particular the identity ZQ.
7. FORMAL SERIES Let A be an alphabet and let K be a semiring. A formal series (or just series) over A with coefficients in K is a mapping a: A*
--*
K.
The value of a on w E A* is denoted (a,w). We indifferently denote by or
KA*
K((A))
the set of formal series over A. We denote by K ( A ) the set of formal series a E K ( ( A ) ) such that (c,w ) = 0 for all but a finite number of w E A*. An element of K ( A ) is called a polynomial. A series c E K ( ( A ) )can be extended to a linear function from K ( A ) into K by linearity. For p E K ( A ) , (0,
PI
=
1 (a,W N P , w).
WEA*
This definition makes sense because p is a polynomial. Let a, z E K ( ( A ) ) and k E K.We define the formal series a + z, az, and ka by .(
+ z, w ) = (at, w ) =
(CT,
+ (7, w),
(7.1)
(a,u)(z,U),
(7.2)
w)
c
uv=w
(ka,w ) = k(a,w).
(7.3) In (7.2), the sum runs over the 1 + IwI pairs (u,u) such that w = uv. It is therefore a finite sum. The set K ( ( A ) )contains two special elements denoted 0 and 1 defined by
(0,w ) = 0,
(1, w ) =
1 0
if w = 1, else.
As usual, we denote a" = a a * * *(n a times) and a '
=
1. With the operations
30
0. PRELIMINARIES
defined by (7.1)and (7.2)the set K ( ( A ) )is a semiring. It may be verified that when K is complete K ( ( A ) ) is also complete. The support of a series a E K ( ( A ) )is the set supp(o) = { w E A* I (a,w ) # O}. The mapping a- supp(a) is an isomorphism from i3?((A))onto V(A*). A family (a&, of series is said to be locally finite if for all w E A*, the set { i E z l ( a , , w )# O }
is finite. In this case, a series a denoted t3=cui iEI
can be defined by
This notation makes sense because in the sum (7.4)all but a finite number of terms are different from 0. We easily check that for a locally finite family (&I,
Let E K ( ( A ) )be a series such that
(6,l)= 0. Then th6 family (a")nlois locally finite. In fact, the support of contain words of length less than n. We denote o*=
c a",
o+ =
0"
does not
C a'. n l 1
'20
Then a* = 1 + a+,
a*@= aa* = a + .
PROFQSITION 7.1 Let K be a ring with unit and let a E K ( ( A ) ) be a series such that (a, 1)= 0. Then 1 - a is inoertible and a* = (1 - a)-'. Proof
We have
1 = a* - a + = a* - a*g = a*(l - a). Symmetrically, 1 = (1 - @)a*,hence the result. 0
(7.5)
7.
31
FORMAL SERIES
For X c A*, we denote by 3 the characteristic series of X defined by ( X , X )=
1 0
if X E X , else.
We consider the characteristic series X of X as an element of N((A)). When X = {x} we usually write x instead of 5. In particular, since the family ( x ) is~locally ~ ~ finite, we have X = c x s x x More . generally, we have for any series a E K ((A)), 0
=
c (a,w)w.
weA*
PROPOSITION 7.2 Let X , Y c A*. Then
if W # X U Y , if W E ( X - Y ) U ( Y - X ) , if W E X ~ Y .
1
0
(X+_Y,w)= 1 2 In particular, with Z = X v Y,
&+r=z
if
XnY=@.
0
Given two sets X , Y c A*, the product XY is said to be unambiguous if any word w E X Y has only one factorization w = xy with x E X , y E Y.
PROPOSITION 7.3 Let X , Y c A*. Then
(X_Y,w) = Card{(x, y ) E X
I
x Y w = xy}.
In particular, with Z = X Y ,
z=gy iff the product X Y is unambiguous. 0 The following proposition approaches very closely the main subject of this book. PROPOSITION 7.4
For X c A', we haoe
((X)*,w)=Card{(x,,...,x , ) I n 2 0 , x i ~ X , w = x 1 x Z . . . x , } . (7.6) Proof
By the definition of
(X)*we have
Applying Proposition 7.2, we obtain (($)k,
W)
= Card{(x,,x,,
whence formula (7.6). 0
. ..,Xk) I X i E x, W = "1x2 " ' x k } ,
32
0. PRELIMINARIES
EXAMPLE 7.1 A*
= (1
- A)-’ = CWEA, w and (A*A*, w ) = 1 + IwI.
We now define the Hadamard product of two series a, z E K((A)) as the series a 0 z given by (a 0 7 , w ) = (a,w)(z,w). This product is distributive over addition, viz. a0(z
+ z’) = o a t +oat’.
If the semiring K satisfies xy = 0 =. x = 0 or y = 0, then supp(a 0 z) = supp(a) n supp(z) In particular, for X,Y c A* and Z = X n Y,
z=xo_r. Given two series a, z E Z ( ( A ) ) we write a I; z when (a,w ) I(z, w ) for all w E A*. 8. PERMUTATION GROUPS
In this section we give some elementary results and definitions on permutation groups. Let G be a group and let H be a subgroup of G. The right cosets of H in G are the sets H g for g E G. The equality Hg = Hg’ holds iff gg‘-’ E H . Hence the right cosets of H in G are a partition of G. When G is finite. [G:H ] denotes the index of H in G. This number is both equal to Card(G)/Card(H) and to the number of right cosets of H in G. Let Q be a set. The symmetric group over Q composed of all the permutations of Q is denoted by 6,.For Q = { 1,2,, , ,,n} we write 6, instead of 6~1,2,..,,n). A permutation is written to the right of its argument. Thus for g E 6, and q E Q the image of q by g is denoted by qg. A permutation group over Q is any subgroup of 6,. For instance, the alternating group over { 1,2,. ..,n } , denoted by a,,,is the permutation group composed of all even permutations. Let G be a permutation group over Q. The stabilizer of q E Q is the subgroup of G composed of all permutations of G fixing q,
H = { h E G I qh = 4). A permutation group over Q is any subgroup of 6,. For instance, the exists g E G such that p g = q. PROPOSITION 8.1 1. Let G be a group and let H be a subgroup of G. Let Q be the set of right cosets of H in G.
Q = { H g l g E GI.
8.
33
PERMUTATION GROUPS
Let cp be the mapping from G into Gladefined for g E G and H k E Q by ( H k )cp(d = H(kg). The mapping cp is a morphismfrom G into 6, and the permutation group q ( G ) is transitive. Moreover, the subgroup cp(H)is the stabilizer of the point H E Q. 2. Conversely, let G be a transitive permutation group over Q, let q E Q and let H be the stabilizer of q. The mapping y from G into Q defined by
Y: 9 H 4 8 induces a bijection a from the set of right cosets of H onto Q and for all k E G, G, a(Hk) g = a(Hkg).
g E
Proof 1. The mapping cp is well defined because H k = Hk' implies Hkg = Hk'g. It is a morphism since cp(1) = 1 and (Hk)cp(g)cp(g')= (Hkg)cp(g')= Hkgg' = (Hk)cp(gg'). The permutation group q ( G ) is transitive since for k,k' E G, we have ( H k ) cp(k-'k') = Hk'. Finally, for all h E H , cp(h)fixes the coset H and conversely, if cp(g) ( g E G ) fixes H , then Hg = H and thus g E H. 2. Assume that Hg = Hg'. Then gg'-* E H , thus qgg'-' =-q, showing that qg = qg'. Thus y ( g ) = y(g'). This shows that we can define a function a by setting a(Hg) = y(g). Since G is transitive, y is surjective and therefore also a is surjective. To show that a is injective, assume that a(Hg) = a(Hg'). Then qg = qg', whence qgg'-l = q. Thus gg'-' fixes q. Consequently gg'-' E H , whence Hg = Hg'. The last formula is a direct consequence of the fact that both sides are equal to qkg. 0
Let G be a transitive permutation group over a finite set Q. By definition,the degree of G is the number Card(Q).
PROPOSITION 8.2 Let G be a transitive permutation group over a Jinite set Q. Let q E Q and let H be the stabilizer of q. The degree of G is equal to the index of H in G. Proof The function a: Hg Hqg of Proposition 8.1(2)is a bijection from the set of right cosets of H onto Q. Consequently Card(Q) = [ G : H I . 0 Two permutation groups G over Q and G' over Q' are called equivalent if there exists a bijection a from Q onto Q' and an isomorphism cp from G onto G' such that for all q E Q and g E G, C4qg) = a(q)cp(g)
34
0 . PRELIMINARIES
or equivalently, for q’ E Q and g E G, q ’ d d = a((@- ‘(4’))g).
As an example, consider a permutation group G over Q and let H be the stabilizer of some q in Q. According to Proposition 8.1(2) this group is equivalent to the permutation group over the set of right cosets of H obtained by the action of G on the cosets of H. Another example concerns any two stabilizersH and H’of two points q and q’ in a transitive permutation group G over Q. Then H and H’are equivalent. Indeed, since G is transitive, there exists g E G such that qg = q’. Then g defines a bijection a from Q onto itself by a@) = p g . The function cp: H -+ H‘ given by cp(h) = g - ’ hg is an isomorphism and for all p E Q, h E H, a(PN = a ( p )
cpm.
Let G be a transitive permutation group over Q.An imprimitivity equivalence of G is an equivalence relation 8 over Q that is stable for the action of G, i.e., such that for all g E G, p=q
mod0 + p g r q g mod8
The partition associated with an imprimitivity equivalence is called an imprimitiuity partition. Let 0 be an imprimitivity equivalence of G. The action of G on the classes of 8 defines a transitive permutation group denoted by Go called the imprimitivity quotient of G for 8. For any element q in Q, denote by [ q ] the equivalence class of q mod 8, and let K, be the transitive permutation group over [ q ] formed by the restrictions to [q] of the permutations g that globally fix [a], i.e., such that [ q l g = [ q ] . The group K, is the group induced by G on the class [ q ] . We prove that the groups K,,q E Q all are equivalent. Indeed let q,q’ E Q and g E G be such that qg = q‘. The restriction a of g to [ q ] is a bijection from [ q ] onto [q’].Clearly, a is injective. It is surjective since if p = q’ mod 8, then p g - ’ = q mod 8 and a ( p g - ’ ) = p . Let cp be the isomorphism from Kq onto K,. defined for k E K, by p’cp(k)= a(a- ‘(p’)k).This shows that the groups K , and K,.are equivalent. In particular, all equivalence classes mod 8 have the same number of elements. Any of the equivalent groups K, are called the induced groups of G on the classes of 8 and are denoted by G’. Let d = Card Q be the degree of G, e the degree of Go,and f the degree of G’. Then d = ef.
Indeed, e is the number of classes of 8 and f is the common cardinality of each of the classes mod 0.
Let G be a transitive permutation group over Q. Then G is called primitive if the only imprimitivity equivalences of G are the equality relation and the universal relation over Q.
PROPOSITION8.3 Let G be a transitive permutation group over Q. Let q E Q and H be the stabilizer of q. Then G is primitive iff H is a maximal subgroup of G. Proof Assume first that G is primitive. Let K be a subgroup of G such that c K c G. Consider the family of subsets of Q having the form qKg for g E G. Any two of these subsets are either disjoint or identical. Suppose indeed that for some k, k’ E K and g , g‘ E G, we have qkf = qk’g’. Then qkg g ‘ - k‘- = q, showing that keg’- k’- E H c K.Thus gg’- E K , whence Kg = Kg’ and consequently qKg = qKg’. Thus the sets 4Kg form a partition of Q which is clearly an imprimitivity partition. Since G is primitive this implies that either qK = {q} or qK = Q. The first case means that K = H. In the second case, K = G since for any g E G there is some k E K with qk = qg showing that g k - E H c K which implies g E K . This proves that His a maximal subgroup. Conversely, let H be a maximal subgroup of G and let 0 be an imprimitivity equivalence of G. Let K be the subgroup
H
’
K ={kEGlqk=qmodO}. Then H c K c G, which implies that K = H or K = G. If K = H, then the class of q is reduced to q and 0 is therefore reduced to the equality relation. If K = G, then the class of q is equal to Q and 8 is the universal equivalence. Thus G is primitive. 0 Let G be a transitive permutation group on Q. Then G is said to be regular if all elements of G - { 1) have no fixed point. It is easily verified that in this case Card(G) = Card(Q).
PROPOSITION 8.4 Let G be a transitive permutation group over Q and let q E Q. The group G is regular iff the stabilizer of q is a singleton. 0 Let k 2 1 be an integer. A permutation group G over Q is called k-fold trunsitiue (or k-transitive) if for all k-tuples ( p l , p 2 , ...,p k ) E Qk and (ql, q 2 , . ..,qk) E Qk composed of distinct elements, there is a g E G such that PIg = 41, P 2 g = qZ,.**,Pkg= qk. The 1-transitive groups are just the transitive groups. Any k-transitive group for k 2 2 is clearly also (k - 1) transitive. The group 6, is n-fold transitive.
PROPOSITION 8.5 Let k 2 2 be an integer. A permutation group G over Q is ktransitive iff G is transitive and fi the restriction to the set Q - (4)of the stabilizer of q E Q is (k - lktransitiue.
36
0 . PRELIMINARIES
Proof The condition is clearly necessary. Conversely assume that the condition is satisfied and let (pl, p 2 , . . .,p k ) E Qk,and (ql,q2,. .., q k )E Qkbe k-tuples composed of distinct elements. Since G is transitive, there exists a g E G such that plg = q l . Let H be the stabilizer of q l . Since the restriction of H to the set Q - { q l } is (k - 1)-fold transitive, there is an h E H such that p z g h = q 2 , . . .,pkgh = qk. Since plgh = ql, the permutation g’ = gh satisfies p l g f = q l , . ..,pkg’ = qk.This shows that G is k transitive. 0 .
A 2-transitive group is also called doubly transitive. PROPOSITION 8.6
A doubly transitive permutation group is primitive.
Proof Let G be a doubly transitive permutation group over Q and consider an imprimitivity equivalence 8 on G. If 8 is not the equality on Q, then there are two distinct elements q,q’ E Q such that q = q’mod 8. Let q” E Q be distinct from q. Since G is 2-fold transitive, there exist g E G such that qg = q and q’g = q”. Since 8 is an imprimitivity equivalence we have q 3 q” mod 8. Thus 8 is the universal relation on Q. This shows that G is primitive. 0
The converse of Proposition 8.6 is false. Indeed, for any prime number p , the cyclic group generated by the permutation (12.3- p) is primitive but is not doubly transitive. An interesting case where the converse of Proposition 8.6 is true is described in a famous theorem of Schur that will be stated in Chapter 5. NOTES
Each of the subjects treated in this chapter is part of a theory that we have considered only very superficially. A more complete exposition about words can be found in Lothaire (1983). For automata (Sect. 4) we follow the notation of Eilenberg (1974). Theorem 4.9 is due to S. Kleene. Our presentation of ideals in monoids (Sect. 5 ) is developed with more detail in Clifford and Preston (1961) or Lallement (1979). The notion of a prime monoid is not classical but it is well fitted to the situation that we shall find in Chapter IV. The 0-minimal ideals of prime monoids are usually called completely 0-simple semigroups. For semirings and formal series see Eilenberg (1974) or Berstel and Reutenauer (1984). Our definition of a complete semiring is less general than that of Eilenberg (1974) but it will be enough for our purposes. A classical textbook on permutation groups is Wielandt (1964).
CHAPTER
I
Codes
0. INTRODUCTION
The definitions and some important general properties of codes are presented in this chapter. The first two sections contain several equivalent definitions of codes and free submonoids. In Section 3 we give a method for verifying that a given set of words is a code. A more appropriate franework to answer this question will be given in Chapter IV where automata with multiplicities will be considered. In Section 4 we introduce the notion of a Bernoulli distribution over an alphabet. This allows us to give a necessary condition for a set to be a code (Theorem 4.2). The questions about probabilities raised in this and in the following section will be developed in more depth in Chapter VI. Section 5 introduces the concept of a complete set. This is in some sense a notion dual to that of a code. The main result of this chapter (Theorem 5.10) describescomplete codes by using results on Bernoulli distributions developed previously. In the last section the operation of composition of codes is introduced and several properties of this operation are established. 1. DEFINITIONS
This section contains the definitions of the notions of code, prefix (suffix, biprefix) code, maximal code, and coding morphism and gives examples. 37
38
I . CODES
Let A be an alphabet. A subset X of the free monoid A* is a code over A if for all n, m 2 1 and x,,. . .,x n , x \ , . . .,xk E X,the condition X,X~”’X,
= x’1 x’2”’X:,
(1.1)
implies
n =m and xi = xi for i = 1, ..., n. (1.2) In other words, a set X is a code if any word in X + can be written uniquely as a product of words in X,that is, has a unique factorization in words in X.Since 1.1 = 1, a code never contains the empty word 1. It is clear that any subset of a code is a code. In particular, the empty set is a code. The definition of a code can be rephrased as follows:
PROPOSITION 1.1 If a subset X of A* is a code, then any morphism /I: B* + A* which induces a bijection of some alphabet B onto X is injective. Conversely, if there exists an injective morphism 8:B* + A* such that X = /3(B), then X is a code. Proof Let 8: B* + A* be a morphism such that /?is a bijection of B onto X.Let u,u E B* be words such that B(u) = p(u). If u = 1, then u = 1; indeed, B(b) # 1 for each letter b E B since X is a code. If u # 1 and u # 1, set u = b , b,, u = b; bk, with n, m 2 1, b , ,. , .,b,, b; ,. . .,bk E B. Since p is a morphism, we have B(bl)***B(bn) = B(b\).**B(bk)* But X is a code and b(b,),B(b;)E X . Thus n = m and B(b,) = /?(b;) for i = l,.. ,,n. Now B is injective on B. Thus b, = b; for i = 1,. ..,n, and u = u. This shows that B is injective. Conversely, if 8:B* + A* is an injective morphism, and if
(1.3) for some n,m 2 1, x,,. . . ,x,, xi,. . .,xk E X = B(B), then we consider the letters b,, b; in B such that /3(bi)= x i , B(b;) = xi, i = 1,. . .,n,j = 1,. ..,m. Since bisinjective,Eq.(1.3)irnplies that b , . - . b , = b;..*bk.Thusn = mand b, = b:, whencex,=x;fori= 1, ...,n. 0 x l * * * x=nx;...x;
A morphism /IB* : -+ A * which is injective and such that X = B(B),is called a coding morphism for X . For any code X c A*, the existence of a coding morphism for X is straightforward: it suffices to take any bijection of a set B onto X and to extend it to a morphism from B* into A*. Proposition 1.1 is the origin for the terminology since the words in X encode the letters of the set B. The coding procedure consists of associating to a word bl b2 * * - b, (b, E B ) which is the text in plain language an encoded or enciphered message fl(b,).../?(b,)by the use of the coding morphism b. The fact that /3 is
I . DEFINITIONS
39
injective ensures that the coded text can be deciphered in a unique way to get back the original text.
1.1 For any alphabet A, the set X = A is a code. More generally, EXAMPLE if p 2 1 is an integer, then X = APis a code called the uniform code of words of length p. Indeed, if elements of X satisfy Eq. (l.l),then the constant length of words in X implies the conclusion (1.2). EXAMPLE 1.2 Over an alphabet A consisting of a single letter a, a nonempty subset X c a* is a code iff X is a singleton distinct from 1 (=ao). EXAMPLE 1.3 The set X = {aa, baa, ba} over A = {a, b} is a code. Indeed, suppose the contrary. Then there exists a word w in X + , of minimal length, that has two distinct factorizations, w = X 1 X z ” ’ X , = x;x;***x:, (n, m 2 1, x i , x J E X). Since w is of minimal length, we have x1 # x i . Thus x1 is a proper left factor of x i or vice versa. Assume that x1 is a proper left factor of x i . By inspection of X, this implies that x1 = ba, x i = baa. This in turn implies that x2 = aa, x; = aa (see Fig. 1.1). Thus x i = xla, xix; = xlx2a, and if we assume that x;x;. * * xb = x1x2 xpa, it necessarily follows that X p + l -- aa and ~ l p = + aa. ~ Thus x;x;*..xk+l = x l x z * ~ * x p + l aBut . this contradicts the existence of two factorizations.
EXAMPLE 1.4 The set X = {a, ab, ba} is not a code since the word w = aba has two distinct factorizations w = (ab)a = a(ba). The following corollary to Proposition 1.1 is useful. 1.2 Let a: A* + C* be an injective morphism. I f X is a code COROLLARY over A, then a ( X ) is a code over C. I f Y is a code over C , then a-’( Y ) is a code over A.
Proof Let 8:B* + A* be a coding morphism for X.Then a(p(B))= a ( X ) , and since a 0 8:B* + C*is an injective morphism, Proposition 1.1 shows that a ( X )is a code.
Fig. 1.1 A double factorization starting.
40
I . CODES
Conversely, let X = a - ' ( Y ) , let n, m 2 l , x l ,...,x , , , x ; , : . . , x ; that X I " ' X , = x; * . * x ; .
E
X be such
Then a ( x l ) * * a(x,) = a(x;) * * * a(x;).
Now Y is a code; therefore n = m and a(xJ = a(xf) for i = 1,. . . , a The injectivity of 01 implies that xi = xf for i = 1 , . . .,n, showing that X is a code. 0 COROLLARY 1.3 If X c A* is a code, then X " is a code for all integers n > 0. Proof Let p: B* + A* be a coding morphism for X. Then X" = p(B").But B" is a code. Thus the conclusion follows from Corollary 1.2. 0 EXAMPLE 1.5 We show that the product of two codes is not a code in general. To do this, we consider the sets X = {a, ba} and Y = {a, a b ) which are easily seen to be codes over the alphabet A = {a, b ) . Then
Z
=X
Y = { aa, aab, baa, baab}.
The word w = aabaab has two distinct factorizations,
w = (aa)(baab)= (aab)(aab). Thus 2 is not a code. An important class of codes is the class of prefix codes to be introduced now. Let X be a subset of A*. Then X is a prefix set if no element of Xis a proper left factor of another element in X.In an equivalent manner, X is prefix if for all x, x f in X , x I x f =$ x = x'. (1.4) This may be rephrased as: two distinct elements in X are incomparable in the prefix ordering. It follows immediately from (1.4) that a prefix set X containing the empty word just consists of the empty word. Suffix sets are defined in a symmetric way, A subset X of A* is sufix if no word in X is a proper right factor of another word in X. A set is biprefix if it is both prefix and suffix. Clearly, a set of words X is suffix iff 2 is prefix. 1.4 Any prefix (suffix,biprefix) set of words X # { I } is a code. PROPOSITION
Proof If X is not a code, then there is a word w of minimal length having two factorizations w =x1x*'"x" = x;x'z-.*x;
(Xi,X>EX).
4'
I . DEFINITIONS
Both x 1,x', are nonempty, and since w has minimal length, they are distinct. But then x l < x', or x i < x 1 contradicting the fact that Xis prefix. Thus Xis a code. The same argument holds for suffix sets. 0
A prefix code (sufix code, biprefix code) is a prefix set (suffix, biprefix set) which is a code, that is distinct from { 1). EXAMPLE 1.6 Uniform codes are biprefix. The sets X and Y of Example 1.5 are a prefix and a suffix code. EXAMPLE 1.7 The sets X = a*b and Y = {a"b":n 2 l } over A = {a, b } are prefix, thus prefix codes. The set Y is suffix, thus biprefix, but X is not. This example shows the existence of infinite codes over a finite alphabet. A code X is maximal over A if X is not properly contained in any other code over A, that is, if X cX',
X' code
X =X'.
The maximality of a code depends on the alphabet over which it is given. Indeed, if X c A* and A E B, then X c B* and X is certainly not maximal over B, even if it is a maximal code over A. The definition of a maximal code gives no algorithm that allows us to verify that it is satisfied. However, maximality is decidable, at least for recognizable codes (see Section 5).
EXAMPLE 1.8 Uniform codes A" are maximal over At Suppose the contrary. Then there is a word u E A + - A" such that Y = A" u ( u } is a code. The word w = u" belongs to Y*, and it is also in (A")* because its length is x Isome , I x 1,...,x,,, E A". Now a multiple of n. Thus w = u" = x 1 x 2 ~ ~ ~for u 4 A". Thus the two factorizations are distinct, Y is not a code and A" is maximal. PROPOSITION 1.5 Any code X over A is contained in some maximal code over A. Proof Let 9 be the set of codes over A containing X, ordered by set inclusion. To show that 9 contains a maximal element, it suffices to demonstrate, in view of Zorn's lemma, that any chain V (i.e., any totally ordered subset) in 9admits a least upper bound in 9. Consider a chain C of codes containing X ;then
is the least upper bound of C.It remains to show that n,m 2 1, y l , ..., y n y y ' , , . . . , y Ek ?be such that y,..'y" =y;...y&.
? is a code. For this, let
42
I . CODES
Each of the y,, y; belongs to a code of the chain W and this determines n + m elements (not necessarily distinct) of W. One of them, say 2, contains all the others. Thus y,, * , y,, y', ,* * *, y; E 2,and since 2 is a code, we have n = m and y, = y; for i = 1,. . .,n. This shows that P is a code. 0
--
Proposition 1.5 is no longer true if we restrict ourselves to finite codes. There exist finite codes which are contained in no finite maximal code. An example of such a code will be given in Section 5 (Example 5.1 1). The fact that a set X c A* is a code admits a very simple expression in the terminology of formal power series.
PROPOSITION 1.6 Let X be a subset of A', and let M = X * be the submonoid generated by X . Then X is a code ir &I = (X)*or equivalently M = (1 - X)-'. Proof
According to Proposition 0.7.3,the coefficient ((X)*, w ) of a word win
(X)*is equal to the number of distinct factorizations of w in words in X . By definition, X is a code iff this number takes only the values 0 and 1 for any word in A*. But this is equivalent to saying that (X)* is the characteristic series of its support, that is, (X)*= &I. 0 2. CODES AND SUBMONOIDS
The submonoid X * generated by a code X is sometimes easier to handle than the code itself. The fact that X is a code (prefix code, biprefix code) is equivalent to the property that X* is a free monoid (a right unitary, biunitary monoid). These latter properties may be verified directly on the submonoid without any explicit description of its base. Thus we can prove that sets are codes by knowing only the submonoid they generate. We start with a general property.
PROPOSITION 2.1 Let A be an alphabet. Any submonoid M of A* has a unique minimal set of Benerators X = ( M - 1) - ( M- l),. Proof Set Q = M - 1. First, we verify that X generates M , i.e., that X * = M . Since X c M , we have X * c M . We prove the opposite inclusion by induction on the length of words. Of course, 1 E X * . Let m E Q. If m # Q2, then m E X . Otherwise m = m1m2 with m,, rn, E Q both strictly shorter than m. Therefore m,, m2 belong to X * and m E X*. Now let Y be a set of generators of M.We may suppose that 1 4 Y. Then each x E X is in Y* and therefore can be written as x = yly2*.*y,
( y , Y,n ~ 2 0).
The facts that x # 1 and x 4 Q2force n = 1 and x E Y. This shows that X c Y. Thus X is a minimal set of generators and such a set is unique. 0
2. CODES
AND SUBMONOIDS
43
EXAMPLE 2.1 Let A = {a, b } and let M = { w E A* I IwI, = Omod2). Then we compute X = (M - 1) - ( M - 1)' = b u ub*a. We now turn to the study of the submonoid generated by a code. By definition, a submonoid M of A* is free if there exists an isomorphism a: B * + M
of a free monoid B* onto M.
PROPOSITION2.2 Zf M is a free submonoid of A*, then its minimal set of generators is a code. Conversely, if X c A* is a code, then the submonoid X * of A* is free and X is its minimal set of generators. Proof Let a: B* + M be an isomorphism. Then a, considered as a morphism from B* into A*, is injective.By Proposition 1.1, the set X = a(B)is a code. Next M = a(B*) = (a@))* = X * . Thus X generates M. Furthermore B = B + - B + B + and a(B+)= M - 1. Consequently X = (M - 1) (M - l)', showing that X is the minimal set of generators of M. Conversely,assume that X c A*, is a code and consider a coding morphism a: B* + A* for X . Then a is injective and a is a bijection from B into X . Thus a is a bijection from B* onto a(B*)= X * . Consequently X * is free. Now a is a bijection, thus B = B + - B + B + implies X = X + - X + X + , showing by Proposition 2.1 that X is the minimal set of generators of M. 0 The code X which generates a free submonoid M of A* is called the base of M.
COROLLARY 2.3 Let X and Y be codes over A. Zf X* = Y*, then X = Y EXAMPLE 2.1 (continued ) The set X is a (biprefix)code, thus M is a free submonoid of A*. According to Proposition 2.2, we can distinguish two cases where a set X is not a code. First, when X is not the minimal set of generators of M = X*,that is, there exists an equality x = XIX*"'X,
with x, x i E X and n 2 2. Note that despite this fact, M might be free. The other case holds when X is the minimal set of generators, but M is not free (this is the case of Example 1.4). We now give a characterization of free submonoids of A* which is intrinsic in the sense that it does not rely on the bases. Another slightly different characterization is given in the exercises. Let M be a monoid. A submonoid N of M is stable (in M) if for all u,u, WEM, u, v, uw, wv E N
-
wE N.
(2.1)
44
I . CODES
The hypotheses of (2.1) may be written as w EN-’N nNN-’,
thus the condition for stability becomes N-’N nNN-’ c N
or simply N-’N nNN-’ = N,
(2.2)
since 1 E N and therefore N c N - ’ N n N N - ’ . Figure 1.2 gives a pictorial representation of condition (2.1) when the elements u, u, w are words. The membership in N is represented by an arch. Stable submonoids have interesting properties. As a result, they appear in almost all of the chapters in this book. A reason for this is Proposition 2.4 which yields a remarkable characterization of free submonoids of a free monoid. As a practical application, the proposition is used to prove that some submonoids are free, and consequently, that their bases are codes without knowing the bases.
PROPOSITION 2.4 A submonoid N of A* is stable ifl
it is free.
Proof Assume first that N is stable. Set X = ( N - 1) - ( N - 1)’. To prove that X is a code, suppose the contrary. Then there is a word z E N of minimal length having two distinct factorizations in words of X, z = X 1 X 2 ” ’ X n = y,y,.**y,
withxl ,...,x,, yl,. . .,y, EX.We may suppose ( x l l < lyll. Then yl = x l w for some nonempty word w. It follows that Xi,
y2*.*ym,X 1 W = y1,
WY2”‘J”X2‘’’Xn
are all in N . Since N is stable, w is in N.Consequently y, = x1w $ X,which yields the contradiction. Thus X is a code. Conversely, assume that N is free and let X be its base. Let u, u, w E A* and suppose that u, v, uw, wu E N .
Fig. 1.2 Representation of stability.
2. CODES AND SUBMONOIDS
45
Set u = x l " ' xk, uw= Yl.**Y,,
Wv
= xk+l'"x,,
=Yl+l**.ys,
with x i , y j in X.The equality ~ ( w u = ) ( u w ) implies ~ x1 "'xkxp+l " ' x , = y1 "'y,y1+1 " ' y , .
Thus r = s and x i = yi( i = 1,. . .,s)since X is a code. Moreover, 1 2 k because luwl 2 IuI, showing'that 1(w
= xI"'xkxk+l"'xI = U X k + l " ' X l r
hence w = X k + 1 * * * xEl N . Thus N is stable. 0 For a prefix code X,the submonoid X* is free, as we have seen, but has a stronger property. Those submonoids which are generated by prefix codes, can also be characterized by a condition which is independent of the base. Let M be a monoid and let N be a submonoid of M. Then N is right unitary (in M ) if for all u, u E M , u,uu~N UEN. In a symmetric way, N is left unitary if for all u, u E M , U,UUEN= U E N .
The conditions may be rewritten as follows: N is right unitary iff N - ' N = N , and N is left unitarv ifr NN-' = N The submonoid N of M is biunitary if it is both left and right unitary. The four properties stable, left unitary, right unitary, and biunitary are of the same nature. Their relationships can be summarized as stable: N - ' N n N N - ' = N
a
\
left unitary: N N - ' = N
N - ' N = N : right unitary
\
8
biuriitary: N - ' N = N N - ' = N
EXAMPLE 2.1 (continued) The submonoid M is biunitary. Indeed, if u, uu E M then Iul, and (uu(, = IuI, Iul, are even numbers; consequently IuI, is even and u E M. Thus M is right unitary.
+
EXAMPLE 2.2 In group theory, the concepts stable, unitary and biunitary collapse and coincide with the notion of subgroup. Indeed, let H be a stable submonoid of a group G. For all h E H,both hh-' and h - ' h are in H . Stability implies that h-' is in H. Thus H is a subgroup. If H is a subgroup, then conversely HH-' = H - ' H = H,showing that H is biunitary.
46
I . CODES
The following proposition shows the relationship between the submonoids we defined and codes. PROPOSITION 2.5 A submonoid M of A* is right unitary (resp., left unitary, biunitary) iff its minimal set of generators is a prejix code (suffix code, bipreJix code). In particular, a right unitary (left unitary, biunitary) submonoid of A* is free. Proof Let M c A* be a submonoid, Q = M - 1 and let X = Q - Q2be its minimal set of generators. Suppose M is right unitary. To show that X is prefix, let x, xu be in X for some u E A*. Then x, xu E M and thus U E M. If u # 1, then U E Q ;but then X U E Q ' contrary to the assumption. Thus u = 1 and X is prefix. Conversely,suppose X is prefix. Let u, u E A* be such that u, uu E M = X*. Then u = x 1" ' X , ,
for some x,,. ..,x,, y , , . ..,y,
E
uu = y , " ' y ,
X . Consequently
X,X,"'X,U
= y,...y,.
Since X is prefix, neither x , nor y, is a proper left factor of the other. Thus xl = y,, and for the same reason x , = y,, ...,x, = y,. This shows that m 2 n and u = Y , + ~* * - y , belongs to M. Thus M is right unitary. 0 Let M be a submonoid of A*. Then M is maximal if M # A* and M is not properly contained in any other submonoid excepted A*. PROPOSITION 2.6 If M is a maximal free submonoid of A*, then its base X is a maximal code. Proof Let Y be a code on A with X 9 Y; Then X* c Y* and X* # Y* since otherwise X = Y by Corollary 2.3. Now X * is maximal. Thus Y* = A* and Y = A.'Thus X 9 A. Let b E A - X . The set Z = X v b2 is a code and M 9 Z * g A* since b' 4 M and b 4 Z*. This contradicts the maximality of M. 0
Note that the converse of the proposition is false since uniform codes A" (n 2 1) are maximal. But if k, n 2 2, we have (A'")* (A")* q A*. showing that (Ank)*is not maximal. We now introduce a family of biprefix codes called group codes which have interesting properties. Before we give the definition, let us consider the following situation. Let G be a group, H be a subgroup of G, and rp:
A*+G
(2.3)
47
2. CODES AND SUBMONOIDS
be a morphism. The submonoid M = cp-'(H) (2.4) is biunitary. Indeed, if, for instance, p , p4 E M, then cp(p), cp(p4) E H, therefore cp(p)-'cp(pq) = q(q)E H and q E M. The same proof shows that M is left unitary. Thus the base, say X,of M is a biprefix code. The definition of the submonoid M in (2.4)is equivalent to a description as the intersection of A* with a subgroup of the free group A@on A. Indeed, the morphism cp in (2.3)factorizes in a unique way in
with I the canonical injection. Setting Q = t j - ' ( H ) , we have M=QnA*.
Conversely if Q is a subgroup of A @and M = Q n A*, then
M
= [-' (Q).
A group code is the base X of a submonoid M = cp-'(H), where cp is a morphism given by (2.3)which, moreover, is supposed to be surjective. Then X is a biprefix code and X is a maximal code. Indeed, if M = A*, then X = A is maximal. Otherwise take w E A* - M and setting Y = X u w, let us verify that Y is not a code. Set m = cp(w). Since cp is surjective, there is word l E A* such that c p ( l ) = m-'. The words u = w l , v = l w both are in M , and w l w = uw = wv E Y*. This word has two distinct factorizations in words in Y, namely, uw formed of words in X followed by a word in Y, and wv which is composed the other way round. Thus Y is not a code and X is maximal. We give now three examples of group codes.
EXAMPLE 2.3 Let A = {a,b} and consider the set
M
= {w E
A*
I 1 WI, = Omod 2)
'
of Example 2.1. We have M = cp - (0), where cp:
A* -+ 2/22
is the morphism given by cp(a) = 1, cp(b) = 0. Thus the base of M,namely the code X = b u ab*a, is a group code, hence maximal.
48
I . CODES
EXAMPLE 2.4 The uniform code A" over A is a group code. The monoid (A")* is indeed the kernel of the morphism of A* onto Z / m Z mapping all letters on the number 1. EXAMPLE 2.5 Let A = {a, b } , and consider now the submonoid A* I IwIa = Iwlb) composed of the words on A having as many a's as b's. Let
iW
(2.5)
6: A* + Z be the morphism defined by a(a) = 1,6(b) = - 1 . Clearly 6(w) = IwIa - lwlb
for all w E A*. Thus the set (2.5) is equal to S-'(O). The base of S-'(O) is denoted by D or D,, the submonoid itself by D* or D1*.Words in D are called Dyck-primes, D is the Dyck code over A. The set D* is the Dyck set over A.
EXAMPLE 2.6 More generally, let A = B u B ( B n B = 0)be an alphabet with 2n letters, and let 6: A* + B* be the morphism of A* onto the free group Badefined by 6(b) = b, 6(b)= b - for b E B, 6 E B. The base of the submonoid 6-,(1) is denoted by D, and is called the Dyck code over A or over n letters. We now furn to a slightly different topic and consider the free submonoids of A* containing a given submonoid. We start with the following observation which easily follows from Proposition 2.4.
PROPOSITION 2.7 The intersection of an arbitrary family of free submonoids of A* is a free submonoid.
Proof Let (Mi)icfbe family of free submonoids of A*, and set M nlEf MI.Clearly M is a submonoid, and it suffices to show that M is stable. If a
=
u, vw, uv, w
E M,
then these four words belong to each of the Mi. Each Mi being stable, w is in Mi for each i E I . Thus w E M. 0 Proposition 2.7 leads to the following considerations. Let X be a subset of A*. As we have just seen, the intersection of all free submonoids of A* containing X is again a free submonoid. It is the smallest free submonoid of A* containing X.We call it the free hull of X . If X* is a free submonoid, then it coincides of course with its free hull. Let X be a subset of A*, let N be its free hull and let Y be the base of N.If X is not a code, then X # Y. The following result, known as the defect theorem gives an interesting relationship between X and Y.
49
2. CODES AND SUBMONOIDS
THEOREM 2.8 Let X be a subset of A*, and let Y be the base of the free hull of X.If X is not a code, then Card(Y) I Card(X) - 1. The following result is a consequence of the theorem. It can be proved directly as well (Exercise 2.1). COROLLARY 2.9 Let X = {xI,x2}. Then X is not a code ifl x1 and x2 are powers of the same word: x1 = y p , x2 = yq for some y E A', p , q 2 0. Note that this corollary entirely describes the codes with two elements. The case of sets with three words is already much more complicated. For the proof of Theorem 2.8, we first show the following result.
PROPOSITION 2.10 Let X c A* and let Y be the base of the free hull of X . Then
Y c X(Y*)-'
n (y*)-'X,
i.e., each word in Y appears as the j r s t (resp.,last) factor in the factorization of some word x E X in words belonging to Y. Proof Suppose that a word y E Y is not in (Y*)-'X. Then X c 1 u Y *( Y - y). Setting
z = Y*(Y - Y), we have 2' = Y*( Y - y), thus X c Z*. Now Z* is free. Indeed, any word z Z* has a unique factorization
E
z = Y ~ Y ~ * * . Y ~Y, ~ , * * * , Y ~YEn Y Z Y, ,
and therefore can be written uniquely as Z=yP~ZlyP2Z2...y~rZr, z1, ...,Z , E Y - y ,
piro.
Now X c Z* g Y*, showing that Y* is not the free hull of X. This yields the contradiction. 0 Proof of Theorem 2.8 If X contains the empty word, then X and X' = X - 1 have same free hull Y*. If the result holds for X', it also holds for X, since if X' is a code, then Y = X and Card(Y) = Card(X) - 1, and otherwise Card(Y) 5 Card(X') - 1 < Card(X) - 2. Thus we may assume that 1 $ X. Let a:X + Y be the mapping defined by a(x) = y
if
x~yY*.
This mapping is uniquely defined since Y is a code; it is everywhere defined since X c Y*. In view of Proposition 2.10, the function a is surjective. If X is
50
not a code, then there exists a relation X1X2"'X,
= x'x' 1 2
* * a
x m' ,
xi,x;EX
with xl # x i . However, Y is a code, and by (2.6) we have a(xl) = a ( x i ) .
Thus a is not injective. This proves the inequality. 0 3. A TEST FOR CODES
It is not always easy to verify that a given set of words is a code. The test described in this section is not based on any new property of codes but consists merely in a systematic organization of the computations required to verify that a set of words satisfies the definition of a code. In the case where X is finite, or more generally if X is recognizable, the amount of computation is finite. In other words, it is effectively decidable whether a finite (recognizable)set is a code. Before starting the description of the algorithm, let us consider 3.1. Let A = {a,b},and X = {b,abb,abbba,bbba,baabb}.This EXAMPLE set is not a code. For instance, the word
w = abbbabbbaabb
has two factorizations (see Fig. 1.3) w = (abbba)(bbba)(abb)= (abb)(b)(abb)(baabb).
These two factorizations define a sequence of left factors of w, each one corresponding to an attempt at a double factorization. We give this list, together with the attempt at a double factorization: (abbba) = (abb)ba (abbba) = (abb)(b)a (abbba)bb = (abb)(b)(abb) (abbba)(bbba)= (abb)(b)(abb)ba (abbba)(bbba)abb= (abb)(b)(abb)(baabb) (abbba)(bbba)(abb)= (abb)(b)(abb)(baabb).
Each but the last one of these attempts fails, because of the rest corresponding to the italicized right factor, which remains after the factorization. The algorithm presented here computes all the remainders in all attempts at a double factorization. It discovers a double factorization by the fact that the empty word is one of the remainders.
3.
5'
A TEST FOR CODES
Fig. 1.3 Two factorizations.
Formally, the computations are organized as follows. Let X be a subset of A + , and let
u, = x - ' x - 1, for n 2 1.
V,,,, = X-'U,, v Un-'X Then we have the following result:
THEOREM 3.1 The set X c A + is a code iff none of the sets U,,defined above contains the empty word. EXAMPLE 3.1 (continued) The word ba is in U, ,next a E U,, then bb E U, and ba E U,, finally abb E U, and since 1 E U,, the set X is not a code, according to Theorem 3.1. The proof of Theorem 3.1 is based on the following lemma. 3.2 Let X c A + and let (U,,),,2,be defined as above. For all n 2 1 LEMMA and k E { 1,. ..,n}, we have 1 E U,, iff there exist a word u E uk and integers i, j 2 0 such that u X ' n X J#
a,
i
+ j + k = n.
(3.1) Proof We prove the statement for all n by descending induction on k. Assume, first k = n. If 1 E U,,, taking u = 1, i = j = 0, Eq. (3.1) is satisfied. Conversely, if (3.1) holds, then i = j = 0. This implies u = 1 and consequently 1 E v,. Now let n > k 2 1, and suppose that the equivalence holds for n, n - 1 , . . .,k + 1. If 1 E U,,, then by induction hypothesis, there exists v E U,, and two integers i,j 2 0 such that
,
vX'nX'#@,
i + j + k + l =n.
Thus there are words x E X i , y E X Jsuch that vx = y . Now v E U,, are two cases. Either there is a word z E X such that
zv =
E
uk,
or there exist z E X , u E Uk such that z = uv.
',and there
52
I . CODES U
z
*
m
0
0
Y
Y
0
(b)
(a)
Fig. 1.4 The two cases.
In the first case [see Fig. 1.4a], one has ux = z y , thus uXi nX j + l #
125,
u E U,.
,
In the second case [see Fig. 3.2(b)], one has z x = uux = uy, thus uXI n X i + ' # fa,
u E uk.
In both cases, Formula (3.1) is satisfied. Conversely, assume that there are u E Uk and i , j 2 0 with uXi nXj,
i
+ j + k = n.
Then UX,X,"'Xi
=y,y,***yj
for some x,, y, in X . If j = 0, then i = 0 and k = n. Thus j 2 1. Once more, we distinguish two cases, according to the length of u compared to the length of Yl-
If u = y,u for some u E A + , then u E x - ' U k c UX1X2"'Xi
and further
&+I
= yz***yj.
Thus u X i n X j - l # 125 and by the induction hypothesis 1 E U,. If y , = uu for some u E A + , then u E U ; ' X c u k + l and X1XZ"'Xi
= oy,'*.y,,
showing that X i n ox]-' # fa, Thus again 1 E U,, by the induction hypothesis. This concludes the proof. 0 It may be noteworthy that the nature of U1did not play any role in the proof of the lemma. In other words, the lemma remains true if U1 is replaced by any set Y, provided that for n > 1, the sets U,,are defined as before. However, the definition of U , is essential in the proof of Theorem 3.1 itself. Proof of Theorem 3.1 If X is not a code, then there is a relation x1x~*'*xp=ylyz*.*yq,xi,yjEX,
XI
ZyI.
3.
A TEST FOR CODES
53
Assume lyll < Ixll. Then x1 = y , u for some u E A'. But then and
u E U,
uXp-' n X 4 - ' #
0.
According to the lemma, 1 E U p + , Conversely, if 1 E U,,, take k = 1 in the lemma. There exists u E U, and integers i , j 2 0, such that UX'n X j # 0.Now u E U, implies that xu = y for some x, y E X . Furthermore x # y since u # 1. It follows from XUX' n x X i # 0 that yX' n x X j # 0, showing that X is not a code. This establishes the theorem. 0 Proposition 3.3 shows that Theorem'3.1 provides an algorithm for testing whether a recognizable set is a code.
PROPOSITION 3.3 If X c A + is a recognizable set, then the set of all V,, ( n 2 0) is jnite. This statement is straightforward for a finite set X since each U,,is composed of right factors of words in X . Proof
Let o be the syntactic congruence of X , defined by w=w'
modo
iff ( V U , O E A * , ~ W U E X O U W ' V E X ) .
Let p be the congruence of A* with the two classes { 1) and A'. Let i = o n p. We use the following general fact. If L c A* is a union of equivalence classes of a congruence 8, then for any subset Y' of A*, Y - ' L is a union of congruence classes mod 8. (Indeed, let z E Y-'L and z' = zmod 8. Then yz E L for some y E Y, whence yz' E L. Thus z' E Y-'L). We prove that each U,,is a union of equivalence classes of z by induction on n 2 1. For n = 1, X is a union of classes of o,thus X - ' X also is a union of classes for o,and finally X - ' X - 1 is a union of classes of 1. Next, if U,, is a union of classes of z, then by the previous fact both U,,- ' X and X - U,, - are unions of classes of 1. Thus U,,, is a union of classes of z. The fact that X is recognizable implies that z has finite index. The result follows. 0
'
EXAMPLE 3.1 (continued) For X = {b,abb, abbba, bbba, baabb}, we obtain Ul = {ba,bba,aabb};
X - ' U l = {a,ba};
U ; ' X = {abb};
V, = {a,ba,abb};
X - ' U , = {a, l};
U;'X
Thus 1 E U, and X is not a code.
=
{bb,bba,abb, 1, ba}.
I . CODES
54
EXAMPLE 3.2 Let X = {a,& ba} and A = {a,b}. We have
U, = { b } ;
U3 = { 1, b);
U, = {a};
U, = X ;
U, = U,.
The set U3 contains the empty word. Thus X is not a code. EXAMPLE 3.3 Let X = {aa,ba, bb, baa, bba} and A = {a, b } . We obtain
U,= {a}, U, = U,.Thus U, = {a} for all n 2 1 and X is a code. If X c A " is prefix (thus a code), then U, = X - ' X - 1 = 0. Thus the algorithm ends immediately for such codes. On the other hand, if X is suffix, the algorithm does not stop after one step. This asymmetrical behavior is due of course to the definition of the U,, which favors computing from left to right. 4. MEASURE OF A CODE
In this section,we give a precise formulation to the idea that a code has only few words, by introducing the notion of the measure of a code. A Bernoulli distribution on A* is a function n: A* + R,
which is a morphism into the multiplicative monoid R, of nonnegative real numbers, and which moreover satisfies
c n(a)
= 1.
ae.4
A distribution is positive if n(a) > 0 for all a E A. It follows from the definition
that n(1) = 1
and that
Indeed, for u E A", we have
c n(ua)
acA
= n(u)
.
c n(a)
= n(u),
acA
thus
Thus n defines a probability distribution on each set A". We extend n to '$(A*) by setting for L c A*
4.
55
MEASURE OF A CODE
Then a becomes a function a: V ( A * ) + @
and satisfies the following properties: for all L c A*;
a(L) 2 0 for any family
I
a(@)= 0;
of subsets of A*
if the sets Li are pairwise disjoint, then
The value a(L)is the measure of the set L relative to a. It is a nonnegative number or + co. There is a special case of these formulas which is useful for the computation of the measure of a set. Let L c A*, and for n 2 0 set s, = a {w E L
I IW I I n}.
Then the following formula holds in 9: a(L) = SUPS,.
(4.3)
n20
EXAMPLE 4.1 Let A be a finite nonempty set, and 1
.(a) = -
Card(A)’
a E A.
Then n defines a Bernoulli distribution on A* called the unijorrn distribution.
EXAMPLE 4.2 Let A = {a,b} and X = {a,ba,bbj. Let a:A* + R, be a distribution. Setting as usual a(b)= q
.(a) = p ,
=
1- p,
we have a ( X )= p
+ pq +
q2
=p
If L, M are subsets of A*, then LM =
+ p q + (1 - p ) q = p + q = 1.
u u {lrn}.
IeLmEM
(4.4)
56
I . CODES
It follows from (4.1) that
The inequality in (4.5) may be strict if the union in (4.4) is not disjoint. For any subset X of A*, Eqs. (4.1) and (4.5) imply that
c n(X,) c rc(X),.
n(X*) I
I
ntO
n2O
Thus if n(X)< 1, then n(X*) < co. Proposition 4.1 shows that for codes, the converse implication holds, and that the inequalities in (4.6) are equalities.
PROPOSITION 4.1 Let X c A + and let a be a Bernoulli distribution on A*. (1) If X is a code, then for n 2 1; a(X)";
n(X")= n(X),,
.(X*) =
c
(4.7)
ntO
and in particular
a ( X * )< co
ifl
a ( X ) < 1.
(2) Conversely, if rc is positiue, if n ( X ) is finite, and if rc(Xn)= rc(X)"
for all n 2 1,
(4.8)
then X is a code. For n 2 1, let S,, be the n-fold Cartesian product of X:S,, = X x
Proof
xx
* * *
x
x.
(1) Assume that X is a code. Then the function (XI,.
.. ,x,) H X I
"
'X,
is a bijection of S, onto X".Consequently
n(X), = (X1
c
....,x.)
rc(x,)**.n(x,)= E S"
C
a(x) = n(X").
XEX"
This shows (4.7). Next the sets (X"),,,o are pairwise disjoint. Thus a(X*)=
c n(X,).
ntO
This together with (4.7) proves the second equality. The last one is an immediate consequence. (2) Assume that X is not a code. Then there is a word u E X* having two distinct factorizations in words in X,say u = X1XZ"'Xn = x;X;.**xk,
4.
57
MEASURE OF A CODE
with n, m 2 1 and x i ,X J E X . The word w = uu has two factorizations: u =x ~ x 2 ~ ~ ~ x "= x x; '1'x~'2 "' 'xX ~~ X 1 X ~ " * X ,
of the same length k = n + m. It follows that
+
1
n ( X ) k=
n(Y1"'Yk) 2 n ( X k ) n(w).
(Yl,. . . . Y k ) E S k
But the finiteness of n ( X )and condition (4.8)imply n(w) I0, hence n(w) = 0. This contradicts the hypothesis that n is positive. 0
THEOREM 4.2 Let X be a code over A. For all Bernoulli distributions n on A*, we have n ( X ) I1. In the case where the alphabet A is finite and where the distribution n is uniform, we obtain,
COROLLARY 4.3 Let X be a code over an alphabet with k letters; then
Proof of Theorem 4.2 We prove the statement first in the case where the numbers 1x1, for x E X, are bounded. (This is the case of a finite code, but a code satisfying the condition is not necessarily finite when the alphabet is infinite.) Thus we assume that there is some integer k 2 1 with
X
c A uA2 u
*
u Ak.
It follows that for n 2 1, X " c A u A 2 u ... u Ank,hence n(X") Ink.
Arguing by contradiction, assume now that n ( X ) > 1, that is, n ( X )= 1 + & for some E > 0. Then by Eq. (4.7),for n 2 1 n(X)" = (1 + &)"* In view of (4.9),we have for all n 2 1 (1
+
E)"
Ikn,
which is impossible. Thus n(X)I1. If X is an arbitrary code, set for n 2 1 X,, = { x E X 11x1 In}. The set X , is a code satisfying the conditions of the first part of the proof. Consequently
.(X") I 1.
58
I . CODES
This shows, in view of Eq. (4.3),that n(X) = supn(X,) I1. 0 n21
EXAMPLE 4.3 Let A = {a,b}, and X = {b,ab,ba}. Define n by .(a) = n(b) = 3. Then n(X) = 3
4,
+ 8 + y,
thus X is not a code. Note that for n(a)= n(b)= 4,we get n(X) = 1. Thus it is impossible to conclude that X is not a code from the second distribution. The following example shows that the converse of Theorem 4.2 is false.
EXAMPLE4.4 Let A
= {a,b},and X = {ab,aba,aab}. The set X is not a
code since (aba)(ab)= (ab)(aab).
However, any Bernoulli distribution n gives n ( X ) < 1. Indeed, let n(a)= p , n(b) = q. Then n(x) = p q
+ 2p2q.
It is easily seen that we always have p q I and also p 2 q I&, provided that + q = 1. Consequently
p
n(X) I $
+ & < 1.
This example gives a good illustration of the limits of Theorem 4.2 in its use for testing whether a set is a code. Indeed, the set X of Example 4.4, where the test fails, is obtained from the set of Example 4.3, where the test is successful, simply by replacing b by ab. This shows that the counting argument represented by a Bernoulli distribution takes into account the lengths as well as the number of words, In other words, Theorem 4.2 allows us to conclude that X is not a code only if there are “too many too short words.” Proposition 4.4 is very useful for proving that a code is maximal. The direct method for proving maximality, based on the definition, indeed is usually much more complicated than the verification of the conditions of the proposition. A more precise statement, holding for a large class of codes, will be given in the next section (Theorem 5.10). PROPOSITION 4.4 Let X be a code over A. If there exists a positive Bernoulli distribution A on A* such that n(X) = 1, then the code X is maximal. Proof Assume that X is not maximal. Then there is some word y E X such that Y = X u y is a code. By Theorem 4.1, we have n ( Y ) I1. On the
4.
MEASURE OF A CODE
59
other hand, a(Y)= a(X)
+ a(y) = 1 + a( y).
Thus a(y) = 0,which is impossible since n is positive. 0
EXAMPLE 4.2 (continued) Since a(X)= 1 and X is prefix, X is a maximal code. EXAMPLE 4.5 We examine again the Dyck code D over A = {a,b} of Example 2.5. Let a:A* + R + be a positive Bernoulli distribution, and let
44 = P,
a(b)= q,
d!,*)= a(D*n A"),
d, = x ( D n A"),
n 2 0.
In view of computing the measure of D, consider the formal power series
We have for n 2 0
(
d#+
d$*' = :)p"q";
= 0.
On the other hand, n(L n A") I1 for any L c A* and for all n. In particular, dl?) I1 for all n 2 0, and consequently the series dF'z" converges in the region {z E C I IzI < I}. In fact
xnZO
1
d'*'(z) =
JW
for IzI < 1
(4.10)
since in this region, the (generalized) binomial formula gives 1
1(- 1)"( -')4"p"qnz2", n Jv =
"20
and an elementary verification shows that
);(
= (-I)"(
3 4 "
(4.1 1)
Each word in D* n A" has a unique factorization into words in D. Thus
d!,*' =
C
C
kL 0 ml + ... +mk = n
dm,dm;~~dm,.
For the corresponding generation functions, this gives 1 d'*'(t) = ___ 1 - d(t)'
(4.12)
60
I . CODES
Consequently we have, for (zI < 1, (4.13)
It follows that
1 d, =
n(D) =
n t O
lim
C d,z"
z+l n t O z=[O.lI
lim ~ - J w = l - J i - Y i & .
=
2'1 ZE P , 1 [
It is easily seen that 1 - ,/-
= 1 - Ip
K ( D )= 1 - ( p - q ( = 1
-
- 41. Thus we get
Ix( u )
- a(b)l.
4,
For n(a) = n(b) = we have n(D)= 1. This gives another proof that D is a maximal code (Example 2.5). Note that n ( D ) < 1 for any other Bernoulli distribution. By Formula (4.12),we have (using again the binomial formula)
Since (t)= (1/2n)(,,:+) we obtain [using again Formula (4.1l)] (4.14)
This gives as a byproduct the following formula Card(D n A2")= Let D' = D n aA* = D n A*b. The set D'* is exactly the set of well parenthesized strings when letter a stands for '(' and letter b for ')'. The previous formulae allow us to compute easily its length distribution. Let D" = D n bA* = D n A*a and
d; = n(D' n A"),
d r = n(D" n A")
let d'(t), d"(t) be the series d'(t) = C n 2 0 d b t n ,d r ( t ) = C n 2 0 d ~ t "We . have d' = D" and d'(t) = d"(t). Since d(t) = d'(t) + d"(t), we obtain d'(t) = i d ( t ) . Let d$*) = n(D'* n A") and d'(*)(t)= ~ n t O d ~ * ) Then, t " . as for (4.12) d"*'(t) =
1 1 - d'(t)'
5.
61
COMPLETE SETS
Since d'(t) = i d ( t ) ,we obtain from (4.13)
2
d"*'(Z) =
1
+ Jiq$
=- 44
2P9Z2'
Therefore by (4.14)
and also Card(D'* n A'") =
-(2")# 1
(4.15)
n
n+l
The numbers y,, = (l/(n + 1)(2,") for n 2 0 are called the Catalan numbers. Their first values are given below n
o
1
yn
1
1
2
2
3
5
4
5
14
42
EXAMPLE 4.6 The set X = Un,,a"bA" is prefix, and therefore is a code over A = {a, b } . It is a maximal code. Let indeed K be a positive Bernoulli distribution, and set p = A@). Then K(U"bA")= p"(1 - p )
hence
.(X) =
c p"(1 - p )
= (1/(1- p))(l - p ) = 1.
n2O
5. COMPLETE SETS
Any subset of a code is itself a code. Consequently, it is important to know the structure of maximal codes. Many of the results contained in this book are about maximal codes. The notion of complete sets introduced in this section is in some sense dual to that of a code. For instance, any set containing a complete set is itself complete. Even if the duality is not perfectly balanced, it allows us to formulate maximality in terms of completeness, thus replacing an extremal property by a combinatorial one. Let M be a monoid and let P be a subset of M . An element m E M is completable in P if there exist u, v in M such that umv E P .
62
I . CODES
It is equivalent to say that P meets the two-sided ideal M m M , MmM n P # 0,
or, in other words, that m E F(P) = M - l P M - ' . A word which is not completable in P is incompletable. The set of words completable in P is of course F(P);the set F(P) = M - F(P) of incompletable words is a two-sided ideal of M which is disjoint from P. A subset P of M is dense in M if all elements of M are completable in P, thus if F(P) = M or, in an equivalent way, if P meets all (two-sided)ideals in M . Clearly, each superset of a dense set is dense. The use of the adjective dense is justified by the fact that dense subsets of M are exactly the dense sets relative to some topology on M (see Exercise 5.3).
EXAMPLE 5.1 Let A
= {a}.The dense subsets of A*
are the infinite subsets.
EXAMPLE 5.2 In a group G , any nonempty subset is dense, since GmG = G for m in G. EXAMPLE 5.3 The Dyck code D over A = {a,b } is dense in A*. Indeed, if w E A*, then u = a31W1bwblWI is easily seen to be in D*.Furthermore, no proper nonempty left factor of u is in D*. Thus u is is D,showing that w is completable in D. It is useful to have a special term for codes X such that the submonoid X* is dense. A subset P of M is called complete in M if the submonoid generated by P is dense. Every dense set is also complete. Next a subset X of A* is complete iff
F(X*)= A*. EXAMPLE 5.4 Any nonempty subset of a + is complete, since it generates an infinite submonoid. The following theorem is of fundamental importance. 5.1 Any maximal code is complete. THEOREM
To prove this result, we first describe a method for embedding any code in a complete code.
PROPOSITION 5.2 Let X c 4' be a code. Let y such that A*yA* n X* = 0.Let
U
= A*
- X* - A*yA*.
Then the set
Y = x u y(Uy)* is a complete code.
E
A* be an unbordered word
5.
COMPLETE SETS
Proof
63
Let V = A* - A*yA*.
Then by assumption X *
c
Vand U = V - ' X * . Let us first observe that the set 2 = vy
is a prefix code. Assume indeed that uy u'y for two words u and u' in V. Since y is unbordered, uy must be a left factor of u'. But then u' is in A*yA*, a contradiction. Thus Z is prefix. Now we show that Y is a code. Assume the contrary and consider a relation
-=
~
1 ***Yn ~ = 2 Y'IY;
~k
with y,, .. . ,yk E E: and y, # y',. The set X being a code, one of these words must be in Y - X. Assume that one of y,, . . .,y, is in Y- X,and let p be the smallest index such that y p E y(Uy)*. From y $ F(X*) it also follows that y, $ F(X*). Consequently one of y', ,.. .,yk is in y(Uy)*. Let q be the smallest index that yb E y(Uy)*. Then
Y,...Y,-lY,
,
--
y;y;.**y;-lyEZ
,
whence y1 * y,- = y', yb - since 2 is prefix. The set X is a code, thus from y, # y', it follows that p = q = 1. Set yl
= yuly*"yuky,
Y', = yu;y..-yu;y,
with u , , . . ., u k ,u', ,.. . ,u; E U.Assume y , c y ; . Since 2 is prefix, the set Z* is right unitary. From U c V, it follows that each uiy, uiy is in 2. Consequently u1 = u',
9 .
Let t = u; + y
* *
. ., uk = u;.
yuiy. We have y , * * * y , = ty;***y;.
The word y is a factor of t, and thus occurs also in y2 y., This shows that one of y2,...,y,,, say y,, is in y(Uy)*. Suppose r is chosen minimal. Then y,***y,-,y ~Zandu;+,y~Zareleftfactorsof thesameword. With theset2 being prefix, we have ~ ; + = l ~ 2 * * * ~ r - 1 *
Thus u;+ E X*, in contradiction with the hypothesis u ; + ~E U . This shows that Y is a code. Finally, let us show that Y is complete. Let w E A* and set
w
=u,yu~y~~*yU,~,yu,
64
I . CODES
with n 2 1 and uiE A*
- A*yA*.
Then ywy E Y*.
Indeed let ui,,u i z r , ..,uik be those u:s which are in X*.Then YWY
= (WIY * * * Y ~ i l lY)vil(YOi, + 1 Y * * . Yuiz-
x
1 ~ )
x uik(Yui~+ly***y~ny)*
Each of the parenthesized words is in Y. Thus the whole word is in Y *. 0
Proof of Theorem 5.1 Let X c A + be a code which is not complete. If Card(A) = 1, then X = 125, and X is not maximal. If Card(A) 2 2, consider a word u 4 F(X*). According to Proposition 3.6 of Chapter 0, there is a word u E A* such that y = uu is unbordered. We still have y I# F(X*).If follows then from Proposition 5.2 that X u y is a code. Thus X is not maximal. 0
EXAMPLE 5.5 Let A = {a, b } and X = {bb,bbab, babb}. The word y = aba is incompletable in X*. However, X u y is not a code, since (bb)(aba)(babb)= (bbab)(aba)(bb). This example shows that Proposition 5.2 is false without the assumption that y is unbordered.
EXAMPLE 5.6 We are able now to verify one of the claims made in Section 1, namely that there do exist finite codes which are not contained in a maximal finite code. Let X = {a5,ba2,ab, b } . It is a code over A = {a, b } . Any maximal code containing X is infinite. Indeed, let Y be a maximal code over A containing X,and assume Y finite. Set m = max(ly1 I y E Y} and let u = bma4+5mbm.
The maximality of Y implies its completeness. Thus u is a factor of a word in Y *, Neither b" nor can be proper factors of a word in Y. Thus there exist y, y' E Y u 1 and integers p, q, r 2 0 such that u = bpyaqy'b'
with a4 E Y* (see Fig. 1.5). The word a5 is the only word in Y which does not I y'l. = 4mod 5. contain b; thus q is a multiple of 5; this implies that I y .1 Let y = bha5s+i and y' = a'+ srbkwith 0 Ii, j I4. We have i + j = 4 mod 5 whence i + j = 4.We will show that any choice of i, j leads to the conclusion that Y is not a code. This yields the contradiction.
+
k b * a 5 ( ' + '*) ab * bk-'. If i = 0,j = 4,then k 2 1 and we have ba2 - u 5 f + 4 b=
.
-
If i = 1,j = 3, then bha5s+1 b = bh ass ab.
5.
65
COMPLETE SETS
bm
b"
Y
Y'
Fig. 1.5 The factorization of bma4+5nbm in words in Y
-
If i = 2, j = 2, then b a2+"bk = b a 2 .a''. bk.
. - -
If i = 3, j = 1, then h 2 1 and bha5s+3b = bh-' ba2 ass ab. Finally,
.
if i = 4, j = 0,then bha5s+4.,ab = bh a5(s+1).b. This example is a particular case of a general construction (see Exercise 5.2). The converse of Theorem 5.1 is false (see Example 5.7). However, it is true under an additional assumption that relies on the following definition. A subset P of a monoid M which is not dense is called thin. If P is thin, there is at least one element m in M which is incompletable in P, i.e., such that MmM n P = 0,or equivalently F(P) # M . The use of the adjective thin is justified by results like Proposition 5.3 or 5.6. PROPOSITION 5.3 Let M be a monoid and P , Q c M . Then the set P u Q is thin iff P and Q are thin. J" R is dense and P is thin, then R - P is dense. Proof
If P and Q are thin, then there exist m, n E M such that MmM n P = @,
MnM n Q = @.
Then mn is incompletable in P u Q and therefore P u Q is thin. Conversely if P u Q is thin, there exists m E M which is uncompletable in P u Q and therefore incompletable in P and also in Q. Hence P and Q are thin. If R is dense in M and P is thin, then R - P cannot be thin since otherwise R = ( R - P ) u P would also be thin by the above statement. 0 Thin subsets of a free monoid have additional properties. In particular, any finite subset of A* is clearly thin. Furthermore, if X, Yare thin subsets of A* then the set XY
is thin. In fact, if u # F ( X ) , u 4 F( Y), then uu 4 F(X Y). EXAMPLE 5.7 The Dyck code D over A = {a,b ) is dense (See Example 5.3). It is a maximal code since it is a group code (see Example 2.5). For each x E D, the code D - x remains dense, in view of Proposition 5.3, and thus remains complete. But of course D - x is no more a maximal code. This example shows that the converse of Theorem 5.1 does not hold in general.
66
I . CODES
Theorem 5.1 admits a converse in the case of codes which are both thin and complete. Before going on to prove this, we give some useful properties of these sets. PROPOSITION 5.4 Let X c A* be a thin and complete set. Let w be a word incompletable in X . Then A* = d - l X * g - l = D-'X*G-' (5.3)
u
dED geG
where D and G are the sets of right (resp. left)factors of w. Note that the set D x G is finite. Proof Let z E A*. Since X * is dense, the word wzw is completable in X * , thus for some u, v E A*
uwzwv E x*. Now w is not a factor of a word in X . Thus there exist two factorizations w = g l d = gd, such that ug,,dzg,d,v E X*. This shows that z E d-'X*g-'.
0
PROPOSITION 5.5 Let X be a thin and complete subset of A*. For any positive Bernoulli distribution R on A*, we have
R ( X ) 2 1. Proof We have n(A*) = OD.In view of Eq. (5.3), there exists a pair (d,g) E D x G such that n(d-'X*g-') = 00. Now d(d-'X*g-')g c X*. This implies n(d)n(d- ' X * g - ' ) n ( g ) 5 n(X*). The positivity of n shows that n(dg) # 0. Thus n(X*)= OD. Now n(X*)5
1 n ( X n )Ic (R(X))".
nTO
n2O
Assuming R ( X ) < 1, we get n(X*) < OD. Thus n ( X ) 2 1. 0 Note the following property showing, as already claimed before, that a thin set has only few words.
5.
67
COMPLETE SETS
PROPOSITION 5.6 Let X c A* be a thin set. For any positive Bernoulli distribution on A*, we have n(X) < 00. Proof Let w be a word which is not a factor of a word in X : w I$ F ( X ) . Set n = IwI. We have n 2 1. For 0 5 i I n - 1, consider X,={x~XIIxI=imodn}.
It suffices to show that n(Xi)is finite for i = 0,. ..,n
-
1. Now
x,c A'(A" - w)*. Since A" - w is a code, we have
C (n(A"- w ) ) =~ 1 ( 1 - T C ( W ) ) ~ .
n[(A" - w)*] =
k2O
ktO
The positivity of n implies n(w) > 0, and consequently 1 n[(A" - w)*] = n(w)*
Thus .(Xi) I l/n(w). 11 We are now ready to prove
THEOREM 5.7 Any thin and complete code is maximal. Proof Let X be a thin, complete code and let IT be a positive Bernoulli distribution. By Proposition 5.5, n(X) 2 1, and by Theorem 4.2, we have n(X) I 1. Thus n ( X ) = 1. But then Proposition 4.4 shows that X is maximal. 0 Theorems 5.1 and 5.7 can be grouped together to give THEOREM 5.8 Let X be a code over A. Then X is complete if X is dense or maximal. Proof Assume X is complete. If X is not dense, then it is thin, and consequentlyX is maximal by the previous theorem. Conversely, a dense set is complete, and a maximal code is complete by Theorem 5.1. 0 Before giving other consequences of these statements, let us present a first application of the combinatorial characterization of maximality.
PROPOSITION 5.9 Let X c A* be a j n i t e maximal code. For any nonempty subset B of A, the code X n B* is a maximal code over B. In particular, for each letter a E A, there is an integer n such that a" E X. Proof The second claim results from the first one by taking B = {a}.Let n = max (1x1 1 x E X} be the maximal length of words in X, and let 0 # B c A. To show that Y = X n B* is a maximal code over B, it suffices to show,
68
I . CODES
..' U
... .'.
*..
-
b" t 1
w
... b"+l
..* v
Fig. 1.6 The factorization of ub"+'wb"+'u,
in view of Theorem 5.7, that Y is complete (in B*). Let w E B* and b E B. Consider the word w' = bfl+lwbfl+1. The completeness of X gives words u, u E A* such that uw'v = x1x2"'xk
for some xl, x 2 , .. .,xk E X . But by the definition of n, there exist two integers i,j(l IicjIk)suchthat x i x i + l * * * x=j b'wbs
for some r, s E { 1 , . . ,,n } (see Fig. 1.6). But then x i ,xi + l,. . .,x j E X n B* = Y. This shows that w is completable in Y*. 0 Let X c A + be a finite maximal code, and let a E A be a letter. The (unique) integer n such,that a" E X is called the order of a relative to X . TWREM5.10 Let X be a thin code. 7kefollowing conditions are equivalent: (i) (ii) (iii) (iv)
X is a maximal code. 'Ihere exists a positive Bernoulli distribution x with x ( X ) = 1. For any positive Bernoulli distribution II, we have n ( X ) = 1 . X is complete.
Proof (i) =. (iv) is Theorem 5.1. (iv) (iii) is a consequence of Theorem 4.2 and Proposition 5.5. (iii) =. (ii)is not very hard, and (ii) * (i) is Proposition 4.4. 0
Theorem 5.10 gives a surprisingly simple method to test whether a thin code is maximal. It suffices to take any positive Bernoulli distribution and to check whether the measure of the code equals 1 . EXAMPLE 5.8. The Dyck code D over A = {a,b} is -maximal and complete, but satisfies z ( D ) = 1 only for one Bernoulli distribution (see Example 4.5). Thus the conditions (i) + (ii) + (iv) do not imply (iii) for dense codes. 5.9 The prefix code X = UnZO a"bA" over A = {a,b } is dense EXAMPLE since for all w E A*, alWlbwE X . It satisfies (iii), as we have seen in Example 4.6. Thus X satisfies the four conditions of the theorem without being thin.
5.
69
COMPLETE SETS
THEOREM 5.11 Let X be a thin subset of A', and let n be a positive Bernoulli distribution. Any two among the three following conditions imply the third (i) X is a code, (ii) n ( X ) = 1, (iii) X is complete. Proof (i) + (ii) * (iii).The condition n ( X ) = 1 implies that X is a maximal code, by Proposition 4.4. Thus by Theorem 5.1, X is complete. (i) + (iii) => (ii)Theorem 4.2 and condition (i)imply that n ( X )I 1. Now X is thin and complete; in view of Proposition 5.5, we have n ( X ) 2 1. (ii) + (iii) (i) Let n 2 1 be an integer. First, we verify that X" is thin and complete. To see completeness, let u E A*, and let u, w E A* be such that uuw E X * . Then uuw E X k for some k 2 0. Thus (uuw)"E (X")kc (X")*. This Further, since X is thin and because the shows that u is completable in (X")*. product of two thin sets is again thin, the set X" is thin. Thus, X" is thin and complete. Consequently, n(X")2 1 by Proposition 5.5. On the other hand, we have n(X") In(X)"and thus n(X") I 1. Consequently n(X")= 1. Thus for all n 2 1 n(X") = n(X)".
Proposition 4.1 shows that X is a code. I] Thin codes constitute a very important class of codes. They will be characterized by some finiteness condition in Chapter IV. We anticipate these results by proving a particular case which shows that the class of thin codes is quite a large one. PROPOSITION 5.12 Any recognizable code is thin. Proof Let X c A* be a recognizable code, and let d = (Q,i, T ) be a deterministic complete automaton recognizing X . Associate to a word w, the number p(w) = Card@. w) = Card{q w Iq E Q}.
-
We have p(w) I Card Q and for all u, u, P(UWU)
P(W).
Let J be the set of words w in A* with minimal p(w). The inequality above shows that J is a two-sided ideal of A*. Let w E J,andlet P = Q w. Then P . w = P . Indeed P. w c Q w = P,and on the other hand, P w = Q w2. Thus Card(P w) = p(w2). Since p(w) is minimal, p(w2)= p(w), whence the equality. This shows that the mapping p H p w from P onto P is a bijection. It follows that there is some integer n with the property with the mapping p H p w" is the identity mapping on P .
-
+
.
-
70
I . CODES
Since P = Q w, we have q.w=q-w"+'
forall q E Q .
To show that X is thin, it sufficesto show that X does not meet the two-sided ideal J. Assume that J n X # 0 and let x E X n J . Then i.x=tE?: Next x E J and, by the previous discussion, there is some integer n 2 1 such that i x"+' = t. This implies that x"' E X.But this is impossible, since X is a code. 0
.
The converse of Proposition 5.12 is false: EXAMPLE 5.10 The code X = {a"b"I n 2 l } is thin (e.g., ba is not a factor of X),but X is not recognizable.
EXAMPLE 5. I 1 In one interesting case, the converse of Proposition 5.12 holds: Any thin group code is recognizable. Indeed let X c A* be a group code. Let cp: A* + G be a surjective morphism onto a group G, and let H be a subgroup of G such that X* = cp-'(H). By assumption, X is thin. Let m be a word that is incompletable in X.We show that H has finite index in G, and more precisely that G
=
u HCcp(p)l-',
psm
(where p runs over the left factors of m).Indeed let g E G and w E cp-'(g). Let u E A* be such that cp(u) is the group inverse of gcp(m). 73en cp(wmu) = gcp(rn)cp(u)= 1, whence wmu E X * . Now m is incompletable in X.Thus m is not factor of a word in X and consequently there is a factorization m = pq such that wp, qu E X * . But then h = cp(wp) E H . Since h = gcp(p), we have g E Hcp(p)-'. This proves the formula. The formula shows that there are finitely many right cosets of H in G. Thus the permutation group on the right cosets, say K,is also finite. Let a: G -+ K be the canonical morphism defined by Hra(g) = Hrg (see Section 0.8). Then, setting N = {a E K I Ha = H } , we have H = a - ' ( N ) = a-'(a(H)). Thus X* = $-I$(X*), where $ = a cp. Since K is finite, this shows that X* is recognizable. Consequently, X is also recognizable (Exercise 2.7). Remark We have used in the preceding paragraphs arguments which rely essentially on two techniques: measures on the one hand which allowed us to prove especially Theorem 5.7 and direct combinatorial arguments on words on the other (as in the proof of Theorem 5.1). It is interesting to note that some of the proofs can be done by usingjust one of the two techniques. A careful analysis shows that all preceding statements with the exception of those involving maximality can be established by using only arguments on measures. As an example, the implication (ii) (iv)
6.
7'
COMPOSITION
in Theorem 5.10 can be proved as follows without using the maximality of X . If X is not complete, then X* is thin. Thus, by Proposition 5.6, a(X*) 00 which implies a ( X ) 1 by Proposition 4.1. Conversely, there exist, for some of the results given here, combinatorial proofs which do not rely on measures. This is the case for Theorem 5.8, where the proof given relies heavily on arguments about measures. Another proof of this result will be given in Chapter IV (Corollary 5.5). This proof is based on the fact that if X c A is a thin complete code, then all words w E A* satisfy
-=
-=
+
( X * w X * ) + n X* #
0.
This implies Theorem 5.8, because according to this formula, X u w is not a code for w # X and thus X is a maximal code. 6. COMPOSITION
We now introduce a partial binary operation on codes called composition. This operation associates to two codes Y and Z satisfying a certain compatibility condition a third code denoted by Y 0 2. There is a twofold interest in this operation. First, it gives a useful method for constructing more complicated codes from simpler ones. Thus we will see that the composition of a prefix and a suffix code can result in a code that is neither prefix nor suffix. Second,and this constitutes the main interest for composition, the converse notion of decomposition allows us to study the structure of codes. If a code X decomposes into two codes Y and Z, then these codes are generally simpler. Let Z c A* and Y c B* be two codes with B = alph(Y). Then the codes Y and Z are composable if there is a bijection from B onto 2. If is such a bijection, then Y and Z are called composable through p. Then defines a morphism B* -P A* which is injective since Z is a code (Proposition 1.1). The set
x = p(Y) c z* c A*
(6.1)
is obtained by composition of Y and 2 (by means of p). We denote it by X=YO,Z
or
X=YOZ,
when the context permits it. Since p is injective, X and Y are related by bijection, and in particular CardX = Card Y. The words in X are obtained just by replacing, in the words of Y, each letter b by the word p(b)E 2. The injectivity of p, the Corollary 1.2 and (6.1) show the following result
PROPOSITION 6.1 If Y and 2 are two composable codes, then X = Y 0 Z is a code. [I
I . CODES
72
EXAMPLE 6.1 Let A = {a,b } , B = { c , d , e }and 2 = {a,baybb} c A*,
Y = {cc,d,dc,e,ec} c B*.
The code 2 is prefix, and Y is suffix. Further Card B = Card 2. Thus Y and 2 are composable, in particular by means of the morphism p: B* -+ A* defined by p(c) = a, P(d) = ba, P(e) = bb. Then X = Y 0 2 = {aa, baybaa, bb, bba}. This code X is neither prefix nor suffix. Now choose P': B* -+ A*, p'(c) = ba,
p'(d) = a,
P'(e) = bb.
Then X' = Y oa.2 = {baba,a, aba, bb, bbba}. This example shows that the composed code Y os2 depends essentially on the mapping 8. Let X c A* be a code, with A = alph(X). Since A is a code over itself and X = z(X), with I : A* A* the identity mapping, we have -+
x =X0,A. Let p: B*
-+
A* be a coding morphism for X . Then X = p ( B ) and thus X = BOsX.
These examples show that every code is obtained in at least two ways as a composition of codes. The two expressions X = X o A and X = B o X are exactly the particular cases obtained by replacing one of the two codes by the alphabet in the expression x =YOZ. Indeed, if Y = B, then 2 = P(B) = X ; if now Z = A , then B can be identified with A, and Y can be identified with X . Notice also the formula X = YosZ=>X"= Y"osZ
n22.
Indeed, Y" is a code (Corollary 1.3) and Y" 0 z = P(Y")= X".
PROPOSITION 6.2 Let X c C*, Y c B*, and 2 c A* be three codes, and assume that X and Yare composable through y and that Y and 2 are composable through P. Then ( X oyY )0 s 2 = x osoy( Y 0s 2).
6.
COMPOSITION
73
Proof We may suppose that C = alph(X), B = alph(Y). By hypothesis, the injective morphisms y:
C*+B*,
8: B * + A *
satisfy y ( C ) = Y,
Let 6: D*
P(B) = Z .
-,C* be a coding morphism for X; thus 6 ( D ) = X. Then D* d ,c*4 B*L A.
and &d(D) = p y ( X ) = X OsyPy(C) = X osy( Y ODZ), and also Pyd(D) B(rw4)= Y W ) 0s P(B) = (Xoy Y) 0 z. 0
=
Some of the properties of codes are preserved under composition.
PROPOSITION 6.3 Let Y and Z be composable codes, and let X
=
Y 0 Z.
1. If Y and Z are prefix (sufJix) codes, then X is a prefix (sufJix)code. 2. If Y and Z are complete, then X is complete. 3. If Y and Z are thin, then X is thin.
The proof of (3) uses Lemma 6.4 which cannot be established before Chapter IV, where more powerful tools will be available. LEMMA 6.4 Let Z be a thin complete code ouer A. For each word u E Z* there exists a word w E Z*uZ* having the following property. If mwn E Z*, then there exists a factorization w = sut with ms, tn E Z*. Proof of Proposition 6.3 Let Y c B*, Z c A*, and let P: B* injective morphism with P(B) = 2. Thus X = P( Y) = Y Og 2.
+ A*
be an
1. Assume Y and Z are prefix codes. Consider x,xu E X with u E A*. Since X c Z*, we have x , xu E Z* and since Z* is right unitary, this implies u E Z*. Let y = p- ' ( x ) ,u = p - ' ( u ) E B*. Then y, yu E Y and Y is prefix; thus u = 1 and consequently u = 1. This shows that X is prefix. The case of suffix codes is handled in the same way. 2. Let w E A*. The code 2 is complete, thus uwu E Z* for some u, u E A*. Let h = p- '(uwu) E B*. There exist, by the completeness of Y, two words il, U E B* with tihU E Y*. But then B(U)uwo/?(S)E X*. This proves the completenessof X. 3. If Z is not complete, then F(X)c F(Z*) # A* and X is thin. Assume now that 2 is complete. The code Y is thin. Consequently F(Y) # B*. Let P E B* - F(Y),and u = p(t7). Let w be the word associated to u in Lemma 6.4. Then w $ F(X). Indeed, assuming the contrary, there exist words m, n E A* such that
x = mwn E X c Z*.
74
I . CODES
In view of Lemma 6.4, x = msutn,
with ms, tn E Z* = p(B*).
Settingp = fl-'(ms),4 = j-'(tn),wehavepi&~Y.Thusii~F(Y),contrary to the assumption. This shows that w is not in X, and thus X is thin. 0 We now consider the second aspect of the composition operation, namely the decomposition of a code into simpler ones. For this, it is convenient to extend the notation alph in the following way: let Z c A* be a code, and X c A*. Then alph,(X) = { z E Z I 3u,v E Z* :uzu E X}. In other words, alph,(X) is the set of words in Z which appear at least once in a factorization of a word in X as a product of words in 2. Of course, alph, = alph. The following proposition describes the condition for the existence of a decomposition.
PROPOSITION 6.5 Let X, Z c A* be codes. There exists a code Y such that X=YOZ
ifs alph,(X) = Z . (6.2) The second condition in (6.2)means that all words in Z appear in at least one factorization of a word in X as product of words in 2. X c Z*
and
Proof Let X = Y OsZ, where p:B* +A* is an injective morphism, Y c B* and B = alph(Y). Then X = p(Y) c F(B*) = Z* and further p(B) = alphscB,(/?(Y)), that is, Z = alph,(X). Conversely, let 6: B* + A* be a coding morphism for 2, and set Y = p-'(X). Then X c B(B*) = Z* and b(Y) = X. By Corollary 1.2, Y is a code. Next alph( Y) = B since Z = alph,(X). Thus Y and Z are composable and X = Y0,Z. 0
We have already seen that there are two distinguished decompositions of a code X c A* as X = YoZ, namely X = BOX and X = X o A . They are obtained by taking Z = X and Z = A in Proposition 6.5 [and assuming A = alph(X)]. These decompositions are not interesting. We will call indecomposable a code which has no other decompositions. Formally, a code X c A* with A = alph(X) is called indecomposable if X = Y 0 2 and B = alph(Y) imply Y = B or Z = A. If X is decomposable, and if 2 is a code such that X = Y 0 Z, and Z # X, A, then we say that X decomposes ouer 2.
EXAMPLE 6.1 (continued) The code X decomposesover Z. On the contrary, the code Z = {a, ba, bb} is indecomposable. Indeed, let T be a code such that
6.
COMPOSITION
75
Z c T*, and suppose T # A. Necessarily, a E T. Thus b 4 T. But then ba, bb E T, whence Z c T. Now Z is a maximal code (Example 4.2), thus 2 = T.
PROPOSITION 6.6 For any jinite code X, there exist indecomposable codes Z1,.. .,2, such that
x = z1o..*oz,. To prove this proposition, we introduce a notation. Let X be a finite code, and let I(X) =
C (1x1 - 1) =
11x1 - Card(X). *EX
XPX
For each x E X, we have 1x1 2 1. Thus l(X) 2 0, and moreover I(X) = 0
iff
X is a subset of the alphabet.
PROPOSITION 6.7 If X,Z c A* and Y c B* are jinite codes such that X = Y 0 2, then I(X) 2 I(Y) I@).
+
Proof Let 8: B*
4
A* be the injective morphism such that
x = Y0,Z. From Card(X) = Card( Y) it follows that
By assumption B = alph(Y), whence x y E y ( y l b2 1 for all b in B. Further Ifl(b)I 2 1 for b E B by the injectivity of P. Thus
Proof of Proposition 6.6 The proof is by induction on I(X).If I(X) = 0, then X is composed of letters, and thus is indecomposable. If I(X) > 0 and X is decomposable,then X = Y 0 Z for some codes Y, 2. Further Y and Z are not formed of letters only, and thus 1( Y) > 0, I(Z) > 0. By Proposition 6.7, we have
76
I . CODES
Z(Y) < l ( X ) and l(2)< 1(X). Thus Y and Z are compositions of indecodposable codes. Thus X also is such a composition. 0 Proposition 6.6 shows the existence of a decomposition of codes. This decomposition needs not be unique. This is shown in EXAMPLE 6.2 Consider the codes X = {UU, ba, baa, bb, bba} and Y = {cc,d,dc,e,ec},
Z = {a,ba,bb}
of Example 6.1. As we have seen, X = Y 0 2. There is also a decomposition
x = Y'OyZ' with
Y' = {cc,d,cd,e,ce},
Z' = {aa,b, ba},
and
y:B* + A*
defined by y(c) = b, y(d) = aa, y(e) = ba.
The code Z is undecomposable, the code Z' is obtained from Z by interchanging a and b, and by taking then the reverse. These operations do not change indecomposability. EXAMPLE 6.3 This example shows that in decompositions of a code in indecomposable codes, even the number of components need not be unique. For X = {a3b},we have X = { c d } 0 {a2,ab}= { c d } 0 { u 2 , u } 0 {a,ab} and also
X
= {cd}0
( a 3 ,b } .
This gives two decompositions of length 3 and 2, respectively. The code X in Example 6.2 is neither prefix nor suffix, but is composed of such codes. We may ask whether any (finite) code can be obtained by composition of prefix and suffix codes. This is not the case, as shown in 6.4 The code X = { b ,ba, a2b,a3ba4}does not decompose over a EXAMPLE prefix or a suffix code. Assume the contrary. Then X c Z* for some prefix (or suffix) code Z # A. Thus Z* is right unitary (resp. left unitary). From b, ba E Z*, it follows that a E Z*, whence A = (a, b} c Z* and A = 2. Assuming Z* left unitary, b,
6.
COMPOSITION
77
a2b E Z* implies a’ E Z*. It follows that a 3 b E Z*, whence a 3 E Z* and finally a E Z*. Thus again Z = A. We now give a list of properties of codes which are inherited by the factors of a decomposition. Proposition 6.8 is in some sense dual to Proposition 6.3.
PROPOSITION 6.8 Let X,Y , Z be codes with X = Y O2. 1. I f X 2. l f X 3. lf X 4. If X
is prefix (sufix), then Y is prejx (sufix). is maximal, then Y and Z are maximal. is complete, then Z is complete. is thin, then Z is thin.
Proof We assume that X,Z c A*, Y c B*, p: B* + A* an injective morphism with P(B) = 2, p( Y ) = X. 1. Let y, yu E Y. Then p(y), p(y)p(u)E X,and since X is prefix, p(u) = 1. Now p is injective, whence u = 1. 2. If Y is not maximal, let Y’ = Y u y be a code for some y $ Y. Then p( Y’) = p( Y ) u B( y ) is a code which is distinct from X by the injectivity of /I Thus . X is not maximal. Assume now that Z is not maximal. Set 2’ = Z u z for some z 4 Z such that 2’ is a code. Extend B to B‘ = B u b ( b 4 B ) and define jover B’* by P(b) = z . Then is injective by Proposition 1.1 because 2’ is a code. Further Y’ = Y u b is a code, and consequently p(Y’) = X u z is a code, showing that X is not maximal. 3. is clear from X * c Z*. 4. Any word in Z is a factor of a word in X. Thus F ( Z ) c F ( X ) . By assumption, F ( X ) # A*. Thus F ( Z ) # A* and Z is thin. 0 PROPOSITION 6.9 Let X , Y ,Z be three codes such that X = Y 0 2. Then X is thin and complete o Y and Z are thin and complete.
Proof By Proposition 6.3, the code X is thin and complete, provided Y and Z are. Assume conversely that X is thin and complete. Proposition 6.8 shows that Z is thin and complete. In view of Theorem 5.8, X is a maximal code. By Proposition 6.8, Y is maximal, and thus Y is complete (Theorem 5.2). It remains to show that Y is thin. With the notations of the proof of Proposition 6.8, consider a word u $ F ( X ) . Since Z* is dense, sut E Z* for some words s , t E A*. Thus sut = p(w) for some w E B*. But now w is not completable in Y , since otherwise hwk E Y for some h,k E B*, giving p(h)sut B(k) E X , whence u E F ( X ) . Thus Y is thin. 0 By Proposition 6.9, for thin codes Y, 2, the code Y 0 Z is maximal iff Y and Z are maximal. We have no example showing that this becomes false without the assumption that Y and 2 are thin.
78
I . CODES
PROPOSITION 6.10 Let X be a maximal code over A. For any code Z c A*, the following equivalence holds: X decomposes over Z iff X* E Z*. I n particular, X is indecomposable iff X* is a maximal submonoid of A*. Proof If X decomposes over 2, then X* c Z*. Conversely, if X* c Y*, let 2 = alph,(X). Then X c Z*, and of course 2 = alphz(X). By Proposition 6.5, X decomposes over 2. In view of Proposition 6.8, the code 2 is maximal. By 2 c 2, we have 2 = 2. 0
EXAMPLE 6.5 Let A be an alphabet. We show that the uniform code A" decomposes over 2 iff Z = A" and m divides n. In particular, A" is indecomposable for n prime and for n = 1. Indeed, let A" = X = Y os2, where Y c B* and /3: B* + A*. The code X is maximal and biprefix, and thus Y also is maximal and biprefix and Z is maximal. Let y E Y be a word of maximal length, and set y = ub with b E B. Then Y u uB is prefix. Let indeed y' = ub', b' E B. Any proper left factor of y' is also a proper left factor of y, and therefore is not in Y u uB;next if y' is a left factor of some y" in Y u uB, then by the maximality of the length of y, we have ly'l = ly"I and y' = y". Thus Y u uB is a code. Hence Y u uB = Y, because Y is maximal. It follows that B(uB) = p(u) Z c X. Now X is a uniform code, thus all words in 2 have the same length, say m. Since Z is maximal, Z = A". It follows that n = m Iyl. 0 EXERCISES SECTION 1 1.1.
Let n 2 1 be an integer. Let I, J be two sets of nonnegative integers such that for i, i' E I and j,j' E J , i+j=i'+j'
modn
implies i = i', j = j'. Let Y = {a'ba'l i E I , j E J >
and X = Y u a". Show that X is a code.
SECTION 2 2.1. 2.2.
Show directly (i.e,,without using Theorem 2.8) that a set X = {x, y} is a code iff x and y are not powers of a single word. Let K be a field and A an alphabet. Denote by K ( A ) the subalgebra of K ( ( A ) ) formed by the series o E K ( ( A ) ) such that (6,w) = 0 for all
79
EXERCISES
but a finite number of words w E A*. Let X c A + be a code and fl: E* -+ A* be a coding morphism for X. Extend fl by linearity to a morphism from K ( E ) into K ( A ) . Show that bdefines an isomorphism between K ( B ) and the subalgebra of K ( A ) generated by the elements of x. 2.3.
Show that a submonoid N of a monoid M is stable iff for all m, n E M we have nm,n,mn E N
2.4. 2.5.
*2.6.
S , + , = [S,,-'S,, n S,,Sn-']*.
Set S(X)= u n z 0 S , . Show that S ( X ) is the free hull of X.Show that when X is recognizable, the free hull of X is recognizable. Let M be a submonoid of A* and let
X
2.8.
m EN.
Let M be a commutative monoid. Show that a submonoid of M is stable iff it is biunitary. For X c A + let Y be the base of the smallest right unitary submonoid containing X. (a) Show that Y c ( Y * ) - ' X . (b) Deduce that Card(Y) ICard(X), and give an example showing that equality might hold. Let X be a subset of A + . Define a sequence (S,Jnroof subsets of A* by setting So = X*,
2.7.
3
=(M
- 1) - ( M
- 1)2
be its minimal set of generators. Show that X is recognizable iff M is recognizable. Let M be a monoid. Show that M is free iff it satisfies the following conditions: (i) there is a morphism
1: M - N into the additive monoid N such that 1-'(0) = 1, (ii) for all x, y, z, t E M, we have x y = zt
iff there exists u E M such that xu = z, y = ut or x = zu, uy = t .
SECTION 3 3.1.
Let X be a subset of A + such that X n XX' = @. Define a relation E X* such that
p c A* x A* by (u, u) E p iff there exists x UXUEX,
ux # 1,
uu # 1,
x u # 1.
a0
I . CODES
Show that X is a code iff (1,l) 4 p + , where p + denotes the transitive closure of p. SECTION 4 4.1.
Let D be the Dyck code over A = {a, b } . (a) Show that the following equality holds
Q = aQ*b + b&*a with 0,= D n aA*b, D,,= D n bA*a. (b) Derive from the previous equality another proof of
d(t) = 1 4.2.
Jw,
where d(t) is the series defined in Example 4.5. Let n 2 1 be an integer and I, J be two subsets of {0,1,.. .,n - l } such that for each integer p in (0, 1, ...,n - l} there exist a unique pair (i, j) E I x J such that p=i+j
modn.
Let V = {i + j - n l i I~, j E J , i
+ j 2 n}.
For a set K of integers, let aK = {akI k E Kj.
Let X c {a, b}* be the set X = al(ba")*baJu a".
Show that X is a maximal code.
SECTION 5 Show that the set X = {a3,b,ab,ba2,aba2} is complete and that no proper subset of X is complete. Show that X is not a code. *5.2. Let p 2 5 be a prime number. Let I, J be two subsets of (0, 1,. ..,p - 2) such that for each integer q in (0, 1,. , .,p - 2) there exists a unique pair ( i , j )E I x J such that q = i + j . (a) Show that X = up u {a'bdl i E I , j E J } is a code. (b) Show that if Card(Z) 2 2 and Card@) 2 2, then X is not contained in any finite code. 5.3. Let M be a monoid. Let 9 be the family of subsets of M which are twosided ideals of M or empty. 5.1.
81
NOTES
(a) Show that there is a topology on M for which 9is the family of open sets. (b) Show that a subset P of M is dense in M with respect to this topology iff F ( P ) = M , i.e., if P is dense in the sense of the definition given in Section 5. 5.4. With the notations of Proposition 5.2, and I/ = A* - A*yA*, show successively that
A*
+ (VY)*(27*Y(UY)*Y.
= (YY)*Y= (VY)*(X*Y(UY)*)*Y= (VY)*_v
(Use the identity (c+ z)* = z*(oz*)* = (c*z)*o* for two power series c,T having no constant term). Derive directly from these equations the fact that Y is a code and that Y is complete. 5.5. Show that each recognizable code is contained in a maximal recognizable code. 5.6. Show that each thin code is contained in a maximal thin code. SECTION 6 6.1.
Let t,b: A* -,G be a morphism from A* onto a group G. Let H be a subgroup of G and let X the group code defined by X* = + - l ( H ) . Show that X is indecomposable iff H is a maximal subgroup of G.
NOTES
The concept of a code originated in the theory of communication initiated by C. Shannon in the late 1940s. In this framework, the development of coding theory lead to a detailed study of constant length codes in connection with problems of error detection and correction. An account of this research can be found in McWilliams and Sloane (1977) or Van Lindt (1982). A classical book on information and communication theory is Ash (1965). See also Csiszar and Korner (1981) and McEliece (1977). Variable-length codes were investigated in depth for the first time by Schutzenberger (1955) and also by Gilbert and Moore (1959). The direction followed by Schutzenberger consists in linking the theory of codes with classical noncommutative algebra. The results presented in this book represent this point of view. An early account of it can be found in Nivat ( 1966).
The notion of a stable submonoid appears for the first time in Schiitzenberger (1955) which contains Proposition 2.4. The same result is also given in Shevrin (1960), Cohn (1962) and Blum (1965). A detailed proof of Proposition 2.7 appears in Tilson (1972). The defect theorem (Theorem 2.8) has been proved in several formulations in Lentin (1972), Makanin (1976), and
82
I . CODES
Ehrenfeucht and Rozenberg (1978). Some generalizations are discussed in Berstel et al. (1979). For related questions see also Spehner (1976). The test for codes given in Section 3 goes back to Sardinas and Patterson (1953) and is in fact usually known as the Sardinas and Patterson algorithm. The proof of correctness is surprisinglyinvolved and has motivated a number of papers Bandyopadhyay (1963), Levenshtein (1964), Riley (1967), and De Luca (1976). The design of an efficient algorithm is described in Spehner (1976). See also Rodeh (1982) and Apostolico and Giancarlo (1984). The problem of testing whether a recognizable set is a code is a special case of a well-known problem in automata theory, namely testing whether a given rational expression is unambiguous. Standard decision procedures exist for this question (see Eilenberg, 1974 and Aho et al. 1975).These techniques will be used in Chapter IV. The connection between codes and rational expressions has been pointed out in Brzozowski (1967). Further, a characterization of those codes whose coding morphism preserves the star height of rational expressions is given in Hashiguchi and Honda (1976a). The results of Section 4 are well known in information theory. The full statement of the Kraft-McMillan theorem (McMillan, 1956) includes a converse of Corollary 4.3 which will be proved in Chapter VII (Proposition VII.3.1). The main results of Section 5 are from Schiitzenberger (1955). Our presentation is slightly more general. Proposition 5.2 and Exercise 5.5 are due to Ehrenfeucht and Rozenberg (1983). They answer a question of Restivo (1977).Theorem 5.12 appears in Boe et al. (1980). Example 5.1 1 is a special case of a construction due to Restivo (1977), Exercise 2.6 is from Berstel et al. (1979), Exercise 2.8 is known as Levi's lemma (Levi, 1944), Exercise 3.1 is from Spehner (1975). Exercise 5.2 is from Restivo (1977). It exhibits a class of codes which are not contained in any finite maximal code. Further results in this direction can be found in De Felice and Restivo (1984).
CHAPTER
I1
Prefix Codes
0. INTRODUCTION
Undoubtedly the prefix codes are the easiest to construct. The verification that a given set of words is a prefix code is straightforward. However, most of the interestingproblems on codes can be raised for prefix codes. In some sense, these codes form a family of models of codes: frequently, it is easier to gain intuition about prefix codes rather than general codes. However, we can observe that the reasoning behind prefix codes is often valid in the general case. For this reason we now present a chapter on prefix codes. In the first section, we comment on their definition and give some elementary properties. We also show how to draw the picture of a prefix code as a tree (the literal representation of prefix codes). In Section 2, a construction of the automata associated to prefix codes is given. These automata are deterministic, and we will see in Chapter IV how to extend their construction to general codes. The third section deals with maximal prefix codes. Characterizations in terms of completeness are given. Section 4 presents the usual operations on prefix codes. Most of them have an easy interpretation as operations on trees. An important family of prefix codes is introduced in Section 5. They have many combinatorial properties which illustrate the notions presented 83
84
11. PREFIX CODES
previously. The synchronization of prefix codes is defined in Section 6. In fact, this notion will be generalized to general codes in Chapter IV where the relationship with groups will be established. The notion of measure of a prefix code can be amplified by a definition of average length. This is done in Section 7, where a combinatorial equivalence of average length is given. The last section contains an important result. The deciphering delay is introduced to extend the notion of prefix code to more general codes. Prefix codes are codes with decipheringdelay zero. We give a combinatorial proof of the fact that €or a finite maximal code the decipheringdelay is either infinite or Fero, which means that in the latter case the code is prefix. 1. PREFIX CODES
This introductory section contains equivalent formulations of the definition of a prefix code together with the description of the tree associated to a prefix code. We then show how any prefix code induces in a natural way a factorization of the free monoid. Of course, all results in this chapter transpose to suffix codes by using the reverse operation. It is convenient to have a shorthand for the proper left factors (resp., proper right factors) of the words of a set X . For this we use X A - = X(A+)-'
and
A - X = (A')-'X.
A subset X of A* is prejix if X n X A + = 0.If X contains the empty word 1, then X = { 1). In the other cases, X is a code (Proposition 1.1.4). There is a series of equivalent definitions, all of which will be useful.
PROPOSITION 1.1 For any subset X of A*, the following conditions are equiualent:
(i) X n X A + = @ , (ii) X n X A - = 0, (iii) X A - , X , X A + are pairwise disjoint, (iv) if x, xu E X , then u = 1, (v) if xu = x'u' and x, x' E X , then x = x' and u = u'. 0 The following proposition can be considered as describing a way to construct prefix codes. It also shows a useful relationship between prefix codes and right ideals.
PROPOSITION 1.2 1. Let L be a subset of A*, and let
X = L - LA'.
I . PREFIX CODES
85
Then X is prefix, and it is a code fi
1 # L. Moreover
X A * = LA*,
(1.2)
that is, X and L generate the same right ideal. 2. Let X be a prefix set, and let M be a subset of A* such that XA* = MA*. Then X = M - MA'. In particular X c M , and X is the minimal set of generators of the right ideal M A * . Proof 1 . From X c L, it follows that XA' c L A + , whence X n XA' c X n L A + = @. Further 1 E X iff 1 E L . This proves the first statement. Next, we claim that L c XA*.
(1.3)
Indeed let u E L. If u E X,then u E XA*. Otherwise u E LA', whence u = u'w for some u' E L, w E A'., Arguing by induction on the length, we get that u' E XA*. Thus, u also is in XA*. From (1.3), it follows that LA* c XA*. The reverse inclusion is clear. This proves (1.2). 2. Let x be an element of X . Then x = mu for some m E M , u E A*. Similarly, m = x'u for some x' E X , u E A*. It follows that x = x'uu, whence uu = 1, since X is prefix. Thus X c M . Next (XA*)A = (MA*)A,showing that XA' = MA'. This implies that X c M - MA'. To show the converse inclusion, let m E M - M A + . Then m = xu for some x E X , u E A*. Assuming u # 1, it follows that m E X A + = MA', which is not the case. Thus, u = 1 and m E X.This completes the proof. 0 The set X = L - LA' is called the initial part of L or also the base of the right ideal LA*.
COROLLARY 1.3 Let X and Y be prejix subsets of A*. If X A * = YA*, then X=Y. 0 EXAMPLE1.1 Let A = ( a , b } and let L = A*aA* be the set of words containing at least one occurrence of the letter a. Then X = L - LA' = b*a.
EXAIWLE1.2 Let A = (a,b} and let X = A*ab - A*abA+. Clearly X is a prefix code. It is the set of words ending with ab that do not contain another occurence of the factor ab. Thus, X = b*a*ab. This code, as does the previous one, belongs to the family of semaphore codes that are studied in Section 5. We now give a useful graphic representation of codes, especially of prefix codes over an alphabet with 2 or 3 letters. It consists of associating a tree with
86
11. PREFIX CODES
each prefix code in such a way that the leaves of the tree represent the words in the code. First, we associate an infinite tree with the set A* of words over an alphabet A as follows. The alphabet is totally ordered, and words of equal length are ordered lexicographically Each node of the tree represents a word in A*. Words of small length are to the left of words of greater length, and words of equal length are disposed vertically according to lexical ordering. There is an edge from u to u iff u = ua for some letter a E A. The tree obtained in this way is the literal representation of A* (see Figs. 2.1 and 2.2).
.. ..
..
.. ..
.. Fig. 2.1 The literal representation of {a,b)*.
aa
FYg. 2.2 The literal repmentation of {o, b,c}*.
87
I . PREFIX CODES
To a given subset X of A* we associate a subtree of the literal representation of A* as follows. We keep just the nodes correspondingto the words in X and all the nodes on the paths from the root to these nodes. Nodes corresponding to words in X are marked if necessary. The tree obtained in this way is the literal representation of X . Figures 2.3-2.6 give several examples. a
Fig. 2.3 Literal representation of X = {a,ba, ban}.
Fig. 2.4 Literal representation of X = {oa,ab,baa, bb}.
Fig. 2.5 Literal representation of X
= {a,b, ca, cbba, cbcc].
Fig. 2.6 Literal representation of X = a%.
88
11. PREFIX CODES
It is easily seen that a code X is prefix iff in the literal representation of X , the nodes corresponding to words in X are all leaves of the tree. The advantage of the literal representation, compared to simple enumeration, lies in the easy readability. Contrary to what might seem to happen, it allows a compact representation of relatively big codes (see Fig. 2.7). After this digression, let us state the factorization theorem announced at the beginning of this section. 1.4 Let X be a prefix code over A, and let THEOREM
R = A* - XA*.
Then R is prefix closed and nonempty. Further,
x - 1 = R ( / j - l), l+&A=R+X,
A* = X*& Conversely, if R is a prefix-closed subset of A*, then X = R A - R is a prefix code. If R # 0,then it is the unique prefix code such that R = A* - XA*. Proof If a word w has no left factor in X, then each of the left factors of w shares this property. Thus, R is prefix closed. The set R is nonempty because X # (1). The product of X and A* is unambiguous in view of Proposition l.l(v). Thus, = XA* and
=*
= A* - XA* = A*
- XA* =(1- X)A*.
Fig. 2.7 A code with 26 elements.
(1.7)
89
I . PREFIX CODES
From this equation and = A*,
(1 we get, by multiplying (1.7) by.1 - .4,
R(1 - A ) = 1 -
x,
which is formula (1.4). This also gives
8-
=
1-
x,
from which (1.5) follows. Finally, note that
x* = (1 -
x)-1
by Proposition 6.1 of Chapter I. Multiplication of (1.7) by X * gives X*R
= X*(l
- X)A* = A*.
This proves (1.6). Conversely, let R be a prefix closed subset of A*. If R = 125, then X = R A - R = 521 is a prefix code; thus we may assume R nonempty. Let X = R A - R. Then X is prefix. Indeed if x E X , then x = ra for some r E R, a E A . Each proper left factor u of x is a left factor of r, thus, it is in R and therefore not in X.This shows that X n X A - = 125. With R being prefix-closed, 1 belongs to R and
x = 8.4 - g + 1. Indeed the product R A is unambiguous, and furthermore 1 $ RA. It successively follows from the formula that
X - 1 = R(A - l),
R = (1 - X)A* = A* - X_ A_ * = A* - X A * .
The last equality holds because Xis prefix. Assume finally that there is a prefix code Y such that R = A* - yA* = A* - X A * .
Then YA* = XA*, whence Y = X by Corollary 1.3. This proves uniqueness. 0 Note the followingcombinatorial interpretations of formulas (1.5) and (1.6). The first says that a word in R followed by a letter is either in R or in X and that each word in X is composed of a word in R followed by a letter. The second formula says that each word w E A* admits a unique factorization w = x~x~"'x,u,
xi,...,x, E X ,
u E R.
11. PREFIX CODES
Fig. 2.8 A prefix code.
Fig. 2.9 Another prefix code.
EXAMPLE 1.3 .Let X = {a,baa,bab,bb} c A + be the code represented in Fig. 2.8. Here R = { 1, b, ba) = X A - , and X - 1 = (1 + b + ba)(A- 1). The equality between R and X A - characterizes maximal prefix codes, as we will see in Section 3. EXAMPLE1.4 Let X = (b2)*{a2b,ba}, as given in Fig. 2.9. Here R = R, u R 2 , where R, = X A - = (b2)*(1 u a u b u a,) is the set of proper left factors of X,and R , = XA' - X - X A - = (b2)*(abA*u a3A*). Thus Eq. (1.4) now becomes - 1 = (b2)*(1 + a + b + a2 abA* + a34*)(4 - 1).
x
+
2. THE AUTOMATON OF A PREFIX CODE
The literal representation yields an easy method for verifying whether a word w is in X* for some fixed prefix code X.It suffices to follow the path starting at the root through the successive letters of w. Whenever a leaf is reached, the corresponding factor of w is split away and the procedure is restarted. We will consider several automata derived from the literal representation and relate them to the minimal automaton. The study which is initiated here will be generalized to arbitrary codes in Chapter IV. The particular case of prefix codes is interestingin itself because it is the origin of most of the general results of Chapter IV.
2. THE AUTOMATON OF A PREFIX CODE
9'
Recall (Chapter 0) that for any subset X c A*, we denote by d ( X ) the minimal deterministicautomaton recognizing X .
PROPOSUION 2.1 Let X be a subset of A*. The following conditions are equivalent: (i) X is prefix. (ii) The minimal automaton d ( X )either is empty or has a single Jinal state t and t * A = 0. (iii) There exists a deterministic automaton d = (Q,i, T ) recognizing X with T A = 0. Proof (i) * (ii)Supposethat Xis nonempty. Set d ( X ) = (Q,i,T ) .First, we claim that for q E T , we have { w E A* I q w E T } = { l}. Indeed let x E X and w E A* be words such that i x = q (remember that 4 E T )and q w E T . Then xw E X,whence w = 1. This shows the claim. Thus, two final states are not separable and from the minimality of d ( X ) ,it follows that d ( X ) has just one final state, say t. Assume that t A # 0,and that t a = p for some letter a E A and some state p. Since p is coaccessible, we have p u = t for some u E A*. Thus t au = t, whence au = 1, a contradiction. (ii) =+ (iii) clear. (iii) + (i) From T A = 0,it follows that T A + = 0.Thus, if x E X , and w E A', then i - x w = 0 and xw $ X . Thus X n XA+ = 0. 0
-
-
-
It is easy to construct an automaton for a prefix code by starting with the literal representation. This automaton, call it the literal automaton of a prefix code X,is the deterministic automaton d = ( X A - u X , 1, X) defined by ua if U U E X A -u X , u*a = 0 otherwise.
-
Since XA- u X is prefix-closed, we immediately see that 1 u E X iff u E X , that is L ( d ) = X . The pictorial representation of a literal automaton corresponds, of course, to the literal representation of the code.
EXAMPLE2.1 The code X = {ab,bab, bb} over A = {a,b} has the literal representation given in Fig. 2.10a and the literal automaton given in Fig. 2.10b. The literal automaton d of a prefix code X is trim but is not minimal in general. For infinite codes, it is always infinite. Let us consider two states of d . It is equivalent to consider the two left factors of words of X , say u and u, leading to these states. These two states are unseparable iff
u-'x = u-'x.
11. PREFIX CODES
Ibl
Fig. 2.10 (a) Literal representationof X, (b) Literal automaton of X.
Note that this equality means, on the literal representation of X that the two subtrees with roots u and u, respectively, are the same. This yields an easy procedure for the computation of the minimal automaton: first, all final states are labeled, say with label 0. If labels up to i are defined we consider subtrees such that all nodes except the roots are labeled. Then roots are labeled identically iff the (labeled)subtrees are isomorphic. Taking the labels as states, we obtain the minimal automaton. The procedure is described in Example 2.1-2.3.
EXAMPLE 2.1 (continued) The three terminal states are unseparable by Proposition 2.1. The states a and ba are unsebarable since a-'X = @a)-'X = b. No other relation exists, thus the minimal automaton is as given in Fig. 2.1 1.
W Fig. 2.11 The minimal automaton of X = {ab,bab,bb}.
2. THE AUTOMATON OF A PREFIX CODE
93
Fig. 2.12 A literal automaton.
Fe.2.13
Minimal automaton corresponding to Fig. 2.12.
EXAMPLE 2.2 The literal automaton of X = (b2)*(a2bu ba) is given in Fig. 2.12. Clearly the final states are equivalent, and also the predecessors of final states and their predecessors. On the main diagonal, however, the states are only equivalent with a step 2. This gives the minimal automaton of Fig. 2.13. EXAMPLE 2.3 In Fig. 2.14 the labeling procedure has been carried out for the 26 element code of Fig. 2.7. This gives the subsequent minimal automaton of Fig. 2.15. We now consider automata recognizing the submonoid X* generated by a prefix code X.Recall that X* is right unitary (Proposition 1.2.5).Proposition 2.2 is the analogue of Proposition 2.1.
11. PREFIX CODES
94
Fig. 2.14 The computation of a minimal automaton.
b
Fig. 2.15 A minimal automaton.
2. THE AUTOMATON OF A PREFIX CODE
95
PROPOSITION 2.2 Let P be a subset of A*; the following conditions are equivalent; (i) P is a right unitary submonoid. (ii) The minimal automaton d ( P )has a unique final state, namely the initial state. (iii) There exists a deterministic automaton recognizing P having the initial state as the unique $nu1 state. Proof (i)=. (ii) The States in d ( P )are the nonempty sets u-'P, for u E A*. Now if u E P, then u-'P = P because uv E P iff v E P. Thus, there is only one final state in d ( P ) ,namely P which is also the initial state. (ii) =$ (iii) clear. (iii) =-(i) Let d = (Q,i, i)be the automaton recognizing P. The set P then is a submonoid since the final state and the initial state are the same. Further let u, uv c P. Then i s u = i and i uv = i. This implies that i v = i because d is deterministic. Thus, v E P, showing that P is right unitary. 0 If d = (Q,i, T ) is any deterministic automaton over A, the stabilizer of a state q is the submonoid
Stab(q) = {w E A* I q w = 4).
PROPOSITION 2.3 The stabilizer of a state of a deterministic automaton is a right unitary submonoid. Every right unitary submonoid is the stabilizer of a state of some deterministic automaton. Proof
It is an immediate consequence of the proof of Proposition 2.2. 0
This proposition shows the importance of right unitary submonoids and of prefix codes in automata theory. Proposition 2.4 presents a method for deriving the minimal automaton d ( X * ) of X* from the minimal automata d ( X )of the prefix code X.
PROPOSITION 2.4 Let X be a nonempty prefix code over A, and let d ( X ) = (Q,i, t )be the minimal automaton of X . Then the minimal automaton of
X* is i, t ,t )
if
Stab(i) # 1,
if
Stab(i) = 1;
the action of d ( X * ) , denoted by 0, is given by qOa=q*a
for q # t ,
t Oa = i a.
96
11. PREFIX CODES
Proof Let W = (Q, t, t ) be the automaton obtained from d ( X ) , defining the action 0 by (2.3)and (2.4).Then clearly
L ( 9 )= { w l t 0 w = t } = x*. Let us verify that the automaton W is reduced. For this, consider two distinct states p and q. Since d ( X )is reduced, there is a word u in A* separating p and q, i.e., such that, say p * u = t, q . u # t. (2.5) It follows that p o u = t , and furthermore p 0 u # t for all u < u. If q o u # t, then u separates p and q in the automaton 93 also. Otherwise, there is a smallest left factor u of u such that q o u = t . For this u, we have q u = t. In view of (2.5), u # u. Thus, u c u. But then q 0 u = t and p 0 u # t, showing the p and q are separated by v. Each state in 9is coaccessiblebecause this is the case in d ( X ) .From 1 4 X, we have i # t. The state i is accessible in $iJ iff the set { w I t 0 w = i } is nonempty, thus iff Stab(i) # 1. If this holds, 9 is the minimal automaton of X*.Otherwise, the accessible part of 9J is its restriction to Q - i. 0
-
The automaton d ( X * ) always has the form given by (2.2) if X is finite. In this case, it is obtained. by identifying the initial and the final state. The classification of the prefix codes according to the form of the minimal automaton d ( X * ) goes through the notion of chain. A prefix code X is a chain if there exist disjoint nonempty sets 2 such that Y u 2 is prefix and
x = Y*Z. PROPOSITION2.5 Let X be a nonempty prefix code over A, and let d ( X ) = (Q, i, t ) be the minimal automaton of X . The following conditions are equivalent:
(i) Stab(i) # 1; (ii) X is a chain, (iii) there exists a word u E A + such that u - ' X = X .
Proof (i)+ (ii) By Proposition 2.3, Stab(i)is a right unitary submonoid. Its base, say Y, is a prefix code which is nonempty because Stab(i) # 1. Let 2 be the set of words defined as follows: z E 2 iff i - z = t and i - z ' # i for all nonempty left factors z' of z. From t * A = fa, it follows that 2 is a prefix code. Further Y n 2 = 0,by i # t. Finally X = Y*Z.It remains to verify that V = Y u 2 is prefix. A proper left factor of a word in 2 is neither in 2 nor in Y, the latter by definition. A proper left factor w of a word y in Y cannot be in 2, since otherwise i w = t whence i * y = 0.Thus V is prefix and X is a chain. 4
2.
THE AUTOMATON OF A PREFIX CODE
97
(ii) (iii) Assume that X = Y*Z with I/' = Y u Z prefix and Y n Z = 0. Consider a word u E Y. The code V being prefix, we have u-'Z = 0.Thus u-'x = u - ' ( y * z ) = u - ' y * z = y * z = x. (iii) =- (i) The automaton d ( X ) being minimal, the states of d ( X ) are in bijective correspondence with the nonempty sets u - 'X,where u runs over A*. The bijection is given by associating the state i . u to u - ' X . Thus, the equality u-'X = X expresses precisely that i * u= i. Consequently u E Stab(i). 0
EXAMPLE 2.1 (continued) The minimal automaton of X* is given in Fig. 2.16. The finite code X is not a chain.
Fig. 2.16 The minimal automaton of X * .
EXAMPLE 2.2 (continued) This code is a chain. The automaton d ( X * )is obtained without suppressing the initial state of d ( X ) .See Fig. 2.17.
Fig. 2.17 The minimal automaton of X*,with X = (b2)*(azbu ba).
EXAMPLE 2.4 Consider the code X = ba*b over A = { a , b } . Its minimal automaton is given in Fig. 2.18a. The stabilizer of the initial state is just 1. The minimal automaton d ( X * ) given in Fig. 2.18b is derived from formula (2.2).
98
11. PREFIX CODES
(a)
(b)
Fig. 2.18 (a) The minimal automaton of X = ba*b, and (b) of A'*.
A construction which is analogous to that of Proposition 2.4 allows us to define the literal automaton of X* for a prefix code X.It is the automaton d = ( X A - , 1,l) whose states are the proper left factors of words in X,and with the action given by ua if u a E X A - , u.a= 1 if U U E X , (2.6) 0 otherwise. This automaton is obtained from the literal automaton for X .by identifying all final states of the latter with the initial state 1. It is immediate that this automaton recognizes X * .
1
3. MAXIMAL PREFIX CODES
A subset X of A* is a maximal prefix set if it is prefix and if it is properly contained in no other prefix subset of A*, that is, if X c Y c A* and Y prefix imply X = Y. As for maximal codes, a reference to the underlying alphabet is necessary for the definition to make sense. The set { I } is a maximal prefix set. Every other maximal prefix set is a code. A maximal code which is prefix is always maximal prefix. The converse does not hold: there exist maximal prefix codes which are not maximal as codes. However, under mild assumptions, namely for thin codes, we will show that maximal prefix codes are maximal codes. The study of maximal prefix codes uses a'left-to-right oriented version of dense and complete codes. Let M be a monoid, and let N be a subset of M. An element m E M is rightcompletable in N if mw E N for some win M. It is equivalent to say that N meets the right ideal mM. A subset N is right dense if every m E M is right completable in N,i.e., if N meets all right ideals. The set N is right complete if the submonoid generated by N is right dense. The set N is right thin if it is not right dense. Of course, all these definition make sense if right is replaced by left.
3.
99
MAXIMAL PREFIX CODES
The following implicationshold for a subset N of a monoid M :
N right dense N right complete N thin
* =t-
=*
N dense N complete N right thin.
In the case of a free monoid A*, a subset N of A* is right dense iff every word in A* is a left factor of some word in N.Thus every (nonempty)left ideal is right dense. Similarily, N is right complete if every word w in A* can be written as
w = m,mz.-.m,p for some r 2 0, ml,. ..,m, E N,and p a left factor of some word in N.
PROPOSITION 3.1 For any subset X c A* the following conditions are equiualent. (i) XA* is right dense, (ii) A* = X A - u X u X A + , (iii) for all w E A*, there exist u, u E A*, x E X with wu = xu. Proof (i) =. (iii) Let w E A*. Since XA* is right dense, it meets the right ideal wA*. Thus w = xu for some u, u E A*, and x E X . (iii)+ (ii)If wu = xu, then w E X A -,w E X or w E X A + according to w < x, w = x, or w > x. (ii) (i) The set of left factors of XA* is X A - u X u XA’. 0 PROPOSI~ON 3.2 Lat X c A + be a subset that does not contain the empty word. Then XA* is right dense i$ X is right complete.
Proof Supposefirst that XA* is right dense and consider a word w E A*. If w E X A - u X , then wu E X for some u E A*. Otherwise w E X A + by Proposition 3.1. Thus, w = xw’ for some x E X , w’ E A + . Since x # 1, we have Jw’I < Iwl. Arguing by induction,w’u E X* for some u in A*. Thus, w is a left factor of some word in X*. Conversely, let W E A*, and assume that w u ~ X *for some U E A * . Multiplying if necessary by some word in X , we may assume that wu # 1. Then wu E X + c XA*. 0 Note that F’roposition 3.2 does not hold for X = (1). In this case, XA* = A* is right dense, but X* = { l } is, of course, not. THeOREru 3.3 Let X be a preJix subset of A*. The following conditions are equivalent:
(i) X is a maximal prefix set, (ii) XA* is right dense.
11. PREFIX CODES
I00
Further, if X # {I}, they are equioalent to (iii) X is right complete.
Observe that the equivalence of prefix maximality and right completeness given in this statement is stronger than the result for general codes (Theorem 1.5.10). In the general case, the restriction to thin codes is necessary. Proof By Proposition 3.2, conditions (ii) and (iii) are equivalent. Let us show that (i) and (ii) are equivalent. Let u E A + . The set X u u is prefix iff (X u u) n (X u u)A+ = @, thus, iff (u n X A + )u
(Xn u A + ) = 0,
or iff u 4 X A + and u 4 XA-.Denote by U the set of all words u such that X u u is prefix. Then
u = A* - (XA+u XA-).
(3.1)
Clearly X is maximal prefix iff X = U ; thus, by (3.1) and in view of Proposition 3.1, this is equivalent to X being right dense. 0 The following corollary appears to be useful.
COROLLARY 3.4 Let L c A + and let X = L - L A + . Then L is right complete &?a X is a maximal prefix code. Proof
L is right complete iff LA* is right dense (Proposition 3.2). From
XA* = LA* (Proposition 1.2)and Theorem 3.3, the statement follows. 0 We now give the statement corresponding to the first part of Theorem 1.4, but for maximal prefix codes. 3.5 Let X be a prefix code ouer A, and let P = XA- be the set of THEOREM proper left factors of words in X . Then X is maximal prefix iff one of the following equivalent conditions hold:
g - 1 = f(dj - l), 1 + P A = p + x, A* = x*p.
(3.2) (3.3) (3.4)
Proof Set R = A* - XA*. If X is maximal prefix, then XA* is right dense and R = P by Proposition 3.1. The conclusion then follows directly from Theorem 1.4. Conversely, if & - 1 = l'(A - l), then by Eq. (1.4)
p ( A - 1) = &(A - 1). Since A - 1 is invertible we get P = R, showing that XA* is right dense. 0
3.
MAXIMAL PREFIX CODES
I01
In the case of a finite maximal prefix code, Eq. (3.2) gives a factorization of - 1 into two polynomials. Formula (3.3) has an interpretation on the literal representation of a code X which makes the verification of maximality very easy: if p is a node which is not in X,then for each a E A, there must exist a node pa in the literal representation of X. The following statement corresponds to the other part of Theorem 1.4 and characterizes those prefix-closed sets which define maximal prefix codes.
PROPOSITION 3.6 Let R be a nonempty prefix-closed subset of A*, and let X = RA - R. Then X is a maximal prefix code i f f R contains no right ideal. If this is the case, R = X A - . Proof
By Theorem 1.4, X is prefix and R = A* - XA*.
From this, it follows that R contains no right ideal iff XA* meets all right ideals, i.e., iff XA* is right dense. Thus the equivalence follows from Theorem 3.3. The last observation is a consequence of A* = XA* u X A - . 0 We now come to the relation existing between maximal prefix codes and maximal codes which are prefix. THEOREM 3.7 Let X be a thin subset of A'. The following conditions are equivalent: (i) X is a maximal prefix code, (ii) X is prefix and a maximal code, (iii) X is right complete and a code. Proof (ii) =r (i) is clear. (i) =. (iii) follows from Theorem 3.3. It remains to prove(iii) =.(ii). Let Y = X - XA'. By Proposition 1.2 YA* = XA*. Thus Y is right complete. Consequently Y is complete. The set Y is also thin, since Y c X. Thus Y is a maximal code by Theorem 1.5.7. From the inclusion Y c X,we have X =. Y. 0
EXAMPLE 3.1 This example shows that Theorem 3.7 does not hold without the assumption that the code is thin. Let X = {ubalUII u E A*} over A = {a,b } be the reversal of the code given in Example 1.4.6. It is a maximal code which is right dense, whence right complete. However, X is not prefix. From Corollary 3.4, it follows that Y = X - XA' is a maximal prefix code. Of course, Y # X, and thus, Y is not maximal.
II. PREFIX CODES
I02
PROPOSI~ON 3.8 Let X be a thin subset of A'. The following conditions are equivalent: (i) X is a maximal prejx code. (ii) X is prefx, and there exists a positive Bernoulli distribution K such that .(X) = 1. (iii) X is prefx, and n(X) = 1 for all positive Bernoulli distributions II. (iv) X is right complete, and there exists a positive Bernoulli distribution such that x ( X ) = 1. (v) X is right complete, and K ( X )= 1 for all positue Bernoulli distributions IL.
It is an immediate consequence of Theorem 3.7 and of Theorem
Proof 1.5.10. 0
In the previous section, we gave a description of prefix codes by means of the bases of the stabilizers in a deterministic automaton. Now we consider maximal prefix codes. Let us introduce the following definition. A state q of a deterministic automaton d = (Q,i, T ) over A is recurrent if for all u E A*, there is a word u E A* such that q uu = q. This implies in particular that q u # 0 for all u in A*. PRoposrnO~3.9
Let X be aprejx codeouer A. The following conditions are
equivalent. (i) (ii) (iii) (iv) (v)
X is maximal prefix. The minimal automaton of X* is complete. All states of the minimal automaton of X* are recurrent. The initial state of the minimal automaton of X* is recurrent. X* is the stabilizer of a recurrent state in some deterministic automaton.
Proof (i) =-(ii)Let .ai(X*) = (Q,i, i) be the minimal automaton of XI.Let q E Q, a E A. There is some word u E A* such that i u = q. The code X being right. complete, uau E X* for some word u. Thus i = i uau = (q a) v, showing that q a # 521. Thus .ai(X*) is complete. (ii) * (iii) Let q E Q,u E A*; then q' = q u Z 0 since d ( X * ) is complete. d ( X * ) being minimal, q' is coaccessible, and q is accessible. Thus q' u = q, for some u E A*, showing that q is recurrent.
-
(iii) (iv) * (v) is clear. (v) =$ (i) Let d = (Q,i, T ) be a deterministic automaton and q E Q be a recurrent state such that X* = Staqq). For all u E A* there is a word u E A* with q uu = q, thus uu E X*.This shows that X is right complete. The set X being prefix, the result follows from Theorem 3.3. 0
4.
‘03
OPERATIONS ON PREFIX CODES
4. OPERATIONS ON PREFIX CODES
Prefix codes are closed under some simple operations. We start with a general result which will be used several times.
PROPOSITION 4.1 Let X , ( partition of X . Set
be nonempty subsets of A* and let (Xi)ie,be a
z=UX& iEI
1. Zf X and the r;’s are prefix (maximal prefix), then Z is prejix (maximal prefix). 2. If 2 is prefix, then all yi are prefix. 3. Zf X is prefix and Z is maximal prefix, then X and the y;’s are maximal prefix. Proof
1. Assume that z, zu E 2. Then
zu = x’y‘ z = xy, or some i,j E I , x E Xi, y E yi, x’ E X,, y’ E 5. From
xyu = x’y’ it follows that x = x’, because X is prefix, whence i = j and y = y’. Thus, u = 1 and Z is prefix. Assume now that X A * and the &A* are right dense. Let w E A*. Then ww‘ = xu for some w’, u E A*, x E X . Let x belong to Xi. Since &A* is right dense, uu’ E &A* for some u’ E A*. Thus ww’u‘ E X,&A* whence ww’v’ E ZA*. Thus Z is maximal prefix. 2. Let y, yu E & and x E Xi. Then xy, xyu E 2, implying that u = 1. 3. From ZA* c X A * we get that X A * is right dense. Consequently X is maximal prefix. To show that &A* is right dense, let w E A*. For any x E Xi, xw is right-completable in ZA*. Thus, xw = zw’ for some z E 2. Setting z = x‘y’ with x’ E X,, y’ E yi gives xw = x’y’w’.The code X being prefix, we get x = x‘, whence w = y’w‘, showing that w is in &A*. U For Card(1) = 1, we obtain, in particular, 4.2 If X and Y are prefix codes (maximal prefix),then X Y is a COROLLARY prefix code (maximal prefix). 0
The converse of this corollary holds only under rather restrictive conditions and will be given in Proposition 4.10. COROLLARY 4.3 Lat X c A’, and n 2 1. Then X is (maximal)prefix iff X” is (maximal)prefix.
11. PREFIX CODES
104
Proof By Corollary 4.2, X"is maximal prefix for a maximal prefix code X. Conversely, setting Z = X" = X"-'X,it follows from Proposition 4.1(2) that X is prefix. Writing Z = XX"-',we see by Proposition 4.1(3) that X (and xn-l)are maximal prefix if Z is. 0 Corollary 4.3 is a special case of Proposition 4.8, to be proved later.
COROLLARY 4.4 Let X and Y be prejx codes, and let X = Xlu X, be a partition. Then Z = Xlu X, Y is a prefix code and Z is maximal prefix ifl X and Yare maximal prefix. Proof
With Y' = { l}, we have Z = XIY' u X, Y; The result follows from
is prefix and Z is maximal prefix if X and Y are.
0
There is a special case of this corollary which deserves attention. It constitutes an interesting operation on codes viewed as trees. COROLLARY 4.5 Let X and Y be prefix codes, and x E X . Then 2 = (X- x ) u XY is prefix and Z is maximal prefix fi X and Y are. 0 The operation performed on X and Y is sketched in Fig. 2.19. We now turn to the converse operation. 2 = (X -x)U X Y
Fig. 2.19 Combining codes X and Y.
PROPOSITION 4.6 Let Z be a prefix code, and let p E Z A - . Then Yp= p - ' 2 and X = Z - pY,, u { p } (4.1) are prefix sets. Further if Z is maximal prefix, then Ypand X are maximal prefix also. The opration described in (4.1) can be drawn as shown in Fig. 2.20. Proposition 4.6 is a special case of the followingresult. PROPOSITION 4.7 Let Z be a prefix code, and let Q be a prefix subset of Z A -. For each p E Z A - , the set Y,, = p - '2 is a prefix code;further /
\
4.
'05
OPERATIONS ON PREFIX CODES
x = (Z- PY,, u P
Fig. 2.20 Separating Z and Y,.
is a prefix set. If Z is maximal prefix, then X and the Yp (p E Q ) are maximal prefix.
Proof
Set Xo = Z
-
upEppYp,Yo = { l}, Xp = { p}; then
z = XOY, u (J XPYP. P ~ Q
Thus, to derive the result from Proposition 4.1, it suffices to show that X is prefix. Let x, xu E X with u E A +.These words cannot both be in the prefix set Z nor can they both be in the prefix set Q.Since Q c Z A -,we have x E Q,xu E 2. Thus u E Y, and xu is not in X. 0 Propositions 4.1 and 4.7 can be used to enumerate some maximal prefix sets. Let us illustrate the computation in the case of A = { a , b } . If 2 is maximal prefix and 2 # 1, then both Y =b-'2 X = a-'Z, are maximal prefix and Z = aX v by. (4.2) Conversely, if X and Y are maximal prefix, then so is 2. Thus, Eq. (4.2) defines a bijection from maximal prefix codes onto pairs of maximal prefix sets. Further Card(2) = Card(X) + Card(Y). Let a, be the number of maximal prefix sets with n elements. Then by Eq. (4.2),for n 2 2,
These numbers are related to the Catalan numbers already encountered in Section 1.4 (see Exercise 4.1): a,+'
='"(').n + l
n
I 06
11. PREFIX CODES
PROPOSTION 4.8 Let Y,Z be composable codes and X = Y 0 Z.Then X is a maximal prefix and thin code i$ Y and Z are maximal prefix and thin codes. Proof Assume first that X is thin and maximal prefix. Then X is right complete by Theorem 3.3. Thus X is thin and complete. By Proposition 1.6.9, both Y and Z are thin and complete. Further Y is prefix (Proposition 1.6.8(i)). Thus Y (being thin, prefix, and complete)is a maximal prefix code. Next X is right dense and X c Z*. Thus 2 is right dense. Consequently 2 is a right complete, thin code. By Theorem 3.7,Z is maximal prefix. Conversely, Y and Z being prefix, X is prefix by Proposition 1.6.3, and Y,Z being both thin and complete,Xis also thin and complete by Proposition 1.6.9. Thus X is a maximal prefix code. 0
PROPOSITION 4.9 Let Z be a prefix code ouer A, and let Z = X u Y be a partition. Then T = X* Y is a prefix code, and further T is maximal prefix ifl Z is a maximal prefix code. hoof Let B be an alphabet bijectively associated to 2, and let B = C u D be the partition of B induced by the partition Z = X u Y.Then
T - C*DOZ. The code C* D clearly is prefix. Thus, T is prefix by Proposition 1.6.3. Next, T* = 1 u Z* Y showing that T is right complete iff Z is right complete. The second part of the statement thus results from Theorem 3.3. 0 Note that the codes of this proposition are the chains of Section 2. We conclude this section by the proof of a converse to Corollary 4.2. This result will be of use later (Section 8). PROPOSITION 4.10 Let X and Y be finite nonempty subsets of A* such that the product XY is unambiguous.If XY is a maximal prefix code, then X and Y are maximal pre$x codes.
The following example shows that the conclusion fails for infinite codes. However, it is not known whether the hypothesis of unambiguity is necessary.
EXAMPLE 4.2 Consider X = { 1, a} and Y = (a2)*bover A = (a, b}. Here X is not prefix, and Y is not maximal prefix. However, XY = a*b is maximal prefix and the product is unambiguous. Proof Let Z = XY and n = max{lyl I y E Y}.The proof is by induction on n. For n = 0, we have Y = { 1) and Z = X.Thus, the conclusion clearly holds. Assume n 2 1 and set
I
T = { y E Y Iyl = n } ,
Q = {q E YA - I qA n T # 0).
5.
SEMAPHORE CODES
107
By construction, T = QA. In fact T = QA. Indeed, let q E Q, a E A and let x E X be a word of maximal length. Then xq is a left factor of a word in 2, and xqa is right-completable in ZA*. The code 2 being prefix, no proper left factor of xqa is in 2. Consequently xqau = x’y’
for some x’ E X,y’ E Y,and u E A*. Now n = 1qal 2 ly’l, and 1x1 2 Ix’I. Thus x = XI, y’ = qa, u = 1. consequently qa E Y and T = QA.
Now let Y’ =(Y - T)u Q,
Z‘=XY’. We verify that Z‘ is prefix. Assume the contrary. Then xy‘u = x’”’
for some x, x’ E X, y’, y” E Y’, u # 1. Let a be the first letter of u. Then either y’ or y’a is in Y.Similarly either y” or y”b (for any b in A ) is in Y. Assume y’ E Y.Then xy’ E Z is a proper left factor of x’y” or x‘yl’b, one of them being in 2. This contradicts the fact that Z is prefix. Thus y’a E Y.As before, xy’a is not a proper left factor of x’y” or xry% Thus necessarily u = a and y” E Y, and we have xy’a = x’y”
with y’a, y” E Y. The unambiguity of the product X Y shows that x = x’, y’a = y”. But then y” # Y’. This yields the contradiction.
To see that Z’ is maximal prefix, observe that Z c 2’u Z’A. Thus ZA* c Z’A* and the result follows from Theorem 3.3. Finally, it is easily seen that the product XY‘ is unambiguous: if xy‘ = x’y’’ with x, x’ E X,y’, y“ E Y’, then either y’, y” E Y - T or y’, y” E Q, the third case being ruled out by the prefix character of Z. Of course,max{lyl I y E Y‘} = n - 1. By theinduction hypothesis,Xand Y are maximal prefix. Since Y = (Y’- Q)u QA, the set Y is maximal prefix by Corollary 4.4. 0 It is also possible to give a completely different proof of Proposition 4.10 using the fact that, under the hypotheses of the Proposition, we have n:(X)n(Y) = 1 for all Bernoulli distributions n: (see Exercise VIII.4.2). 5. SEMAPHORE CODES
This section contains a detailed study of semaphore codes which constitute
an interesting subclass of the prefix codes. This investigation also illustrates the techniques introduced in the preceding sections.
I 08
11. PREFIX CODES
PROPOSITION 5.1 For any nonempty subset S of A + , the set X = A*S
- A*SA+
(5.1)
is a maximal prefix code.
Proof The set L = A*S is a left ideal, and thus, is right dense. Consequently, L is right complete, and by Corollary 3.4, the set X = L - L A + is maximal prefix. 0 A code X of the form given in Eq. (5.1) is called a semaphore code, the set S being a set of semaphores for X . The terminology stems from the following observation:a word is in X iff it ends with a semaphore,but none of its proper left factors ends with a semaphore. Thus, reading a word from left to right, the first appearance of a semaphore gives a “signal” indicating that what has been read up to now is in the code X . EXAMPLE 5.1 Let A = {a,b} and, S = {a}. Then X = A*a - A*aA+ whence X = b*a. Note that we also have X = A*a+ - A*a+A + showing that a semaphorecode admits several sets of semaphores(see also Proposition 5.7). EXAMPLE 5.2 For A = {a,b} and S = {aa,ab}, we have A*S = A*aA. Thus A*S - A*SA+ = b*aA. The following proposition characterizes semaphore codes among prefix codes.
PROPOSITION 5.2 Let X c A’. Then X is a semaphore code iff X is prefix and A*X c XA*. (54 Proof Let X = A*S - A*SA+ be a semaphore code, Then X is prefix and it remains to show (5.2). Let w E A*X. Since w E A*S, w has afactor in S. Let w’ be the shortest left factor of w which is in A*S. Then w’ is in X . Consequently, w E XA*. Conversely, assume that a prefix code X satisfies (5.2). Set M = XA*. In view of Proposition 1.2, and by the fact that X is prefix, we have X =M -MAt.
Equation (5.2) implies that A*M = A*XA* c XA* = M , thus, M = A* M and
X = A*M
- A*MA+. O
EXAMPLE 5.3 The code Y = {a’, aba, ab’, b} is a maximal prefix code over A. However, Y is not a semaphore code, since ab E A*Y but ab # YA*.
5.
'09
SEMAPHORE CODES
A semaphore code is maximal prefix, thus, right complete. The following proposition describes those right complete sets which are semaphore codes. PROPOSITION5.3 Let X c A + . Then X is a semaphore code ig X is right complete and X n A*XA+ = 0. (5.3) Proof A semaphore code is maximal prefix, thus also right complete. Further, by (5.2) A*XA" c X A + thus X n A * X A + c X n X A + = 0, showing Eq. (5.3). Conversely, if a set X satisfies (5.3), then X is prefix. To show that X is semaphore, we verify that (5.2) holds. Let w = ux E A*X with u E A*, x E X . The code X being right complete, we have uxu = x'yu for some x' E X , y E X*,u E A*. Now Eq. (5.3) shows that ux is not a proper left factor of x'. Thus ux E x'A*. 0 COROLLARY 5.4 Let X c A+ be a semaphore.code and let P = X A - . Then PX c X P u x2. Proof (See Fig. 2.21) Let p E P, x E X . By Eq. (5.2), px = yu for some y E X , u E A*. The code X is prefix, thus IpI < Iyl. Consequently, u is a right factor of x, and by (5.3), u 4 X A + . The code X is maximal prefix, therefore UEXA-uX. 0 V
X
Fig. 2.21 Proof of Corollary 5.4.
Formula (5.3) expresses a property of semaphore codes which is stronger than the prefix condition: for a semaphorecode X , and two elements x, x' E X , the only possible way for x to occur as a factor in x' is to be a right factor of x'. We now use this fact to characterize semaphore codes among maximal prefix codes.
PROPOSITION 5.5 Let X c A + , and let P = X A - be the set of proper le$t factors of words in X . Then X is a semaphore code fi X is a maximal prefix code and P is sufix-closed.
I I0
11. PREFIX CODES
Of course, P is always prefix closed. Thus P is suffix closed iff it contains the factors of its elements.
Proof Let X be a semaphore code. Then X is a maximal prefix code (Proposition 5.1). Next, let p = uq E P with u,q E A*. Let u E A + be a word such that pu E X . Then q 4 X A * , since otherwise p~ = uqv E X n A * X A + , violating Proposition 5.3. Thus q E X A - = P. Conversely, assume that X is maximal prefix and that X n A * X A + # 0. Let x E X n A * X A + . Then x = ux'u for some u E A*, x' E X , u E A + . It follows that ux' E P and, P being suffix-closed, also x' E P which is impossible. Thus X is a semaphore code by Proposition 5.3. 0 Another consequence of Proposition 5.3 is
PRop0srnO~5.6 Any semaphore code is thin.
Proof By Formula (5.3),no word in X A * is a factor of a word in X . 0
COROLLARY 5.1 Any semaphore code is a maximal code. Proof A semaphore code is a maximal prefix code and thin by Propositions 5.1 and 5.6. Thus by Theorem 3.7, such a code is maximal code. 0 Now we determine the sets of semaphores giving the same semaphorecode.
PRoPos~no~ 5.8 Two nonempty subsets S and T of A + defne the same semaphore code ifl A*SA* = A* T A * . For each semaphore code X , there exists a unique minimal set of semaphores, namely T = X - A'X. . Proof Let X = A*S - A*SA+, Y = A * T - A* T A + . By Proposition 1.2, we have XA* = A*SA*, YA* = A*TA*, and by Corollary 1.3, X = Y iff A*SA* = A* T A * . Next, let X = A*S - A*S A + be a semaphore code. By the definition of T = X - A'X, we may apply to T the dual of Proposition 1.2. Thus, A * T = A * X . Since A*TA* = A*XA* = A*SA*, the set T is indeed a set of semaphores for X . Finally, let us verify that T c S. Let t E T; then t = usu for some U , U E A*, s E S, and s = u't'u' for some u',u' E A*, t' E T. Thus, t = uu't'u'u. Note that T c X . Thus, formula (5.3) applies, showing that u'u = 1. Since T is a suffix code, we have uu' = 1. Thus, t = s E S. 0 We now study some operations on semaphore codes.
PROPOSITION 5.9 If X and Yare semaphore codes, then X Y is a semaphore code. Conversely, if X Y is a semaphore code and if X is a prefx code, then X is a semaphore code.
5.
SEMAPHORE CODES
111
Y'
X'
X
V
Fig. 2.22 Proof of Proposition 5.9.
Proof If X,Y are semaphore codes, then by Corollary 4.2, X Y is a prefix code. Further by Proposition 5.2. A*XY c XA*Y c XYA*. thus X Y is a semaphore code. Assume now that XY is a semaphore code, and that X is a prefix code. We show that A*X c XA*. For this, let w = ux E A*X,with u E A*, x E X,and let y be a word in Y of minimal length. Then
wy = uxy = x'y'u' for some x' E X , y' E Y,u' E A* (see Fig. 2.22). By the choice of y, we have IYI5 IY'I I ly'u'l, thus, lux1 2 Ix'l, showing that ux E X A * . 0 The following example shows that if X Y is a semaphore code, then Y need not be semaphore, even if it is maximal prefix. 5.4 Over A = {a,b}, let X = a*b, and Y = {a2,aba, ab', b). Then EXAMPLE X is a semaphore code, and Y is a maximal prefix code. However, Y is not semaphore (Example 5.3). On the other hand the code Z = XY is semaphore.
Indeed, Z j s maximal prefix, and the set
P =ZA-
= a*{l,b,ba,bab)
is suffix-closed. The conclusion follows from Proposition 5.4 (see Fig. 2.23).
Fig. 223 The code a*b{03,aba,ab2,b}.
I I2
iff
11. PREFIX CODES
COROLLARY 5.10 For any X c A + and n 2 1, the set X is a semaphore code X" is a semaphore code.
Proof If X"is a semaphore core, then X is a prefix by Corollary 4.3 and X is a semaphore code by Proposition 5.9. The converse follows directly from Proposition 5.9. 0
EXAMPLE5.5 The code X = {a,baa, baba, bab2,b'} represented in Fig. 2.24 is a maximal prefix code but not semaphore. Indeed, the word a has an inner occurrence in bab2, contradicting formula (5.3). However, X decomposes into two semaphores codes
X=YoZ with Y = {c,dc,d2,de,e}and Z = {a,ba, b 2 } .
Fig. 2.24
The code X.
Given a semaphore code
X
= A*S - A*SA+,
it is natural to consider
Y = SA* - A+SA*. The code Y is a maximal suffix code; its reverse = A*S - A*SA+ is a semaphore code with semaphores 3. The following result shows a strong relation between X and Y. PROPOSITION 5.1 1 Let S c A'. There exists a bijection /3 from X = A*S A*SA+ onto Y = SA* - A+SA* such that, for each x E X , /3(x) is a conjugate of x.
Proof First, consider J = A*SA*. Then J is a two-sided ideal, and further
X
= J - JA',
Y =J
- A'J.
Indeed, J = JA* = (A*S)A*. Thus, A*S and J generate the same right ideal. By Proposition 1.2, J - J A + = X . The same arguments hold for Y.
5.
“3
SEMAPHORE CODES
Now we define, for each x E X, D(x) = { d E A + I there is some g E A* with x = gd and dg E J}.
Thus, D(x) is composed of nonempty right factors of x. Further D(x) is nonempty since x is in D(x). Thus, each D(x) contains some shortest element. This will be used to define j3 as follows. For x E X, (5.4)
B(x) = dg,
where d is the shortest word in D(x) and g is such that (5.5)
x = gd.
Thus, P(x) is a conjugate of x, and P(x) E J. We show that / ? ( x ) E J - A + J = Y. Assume the contrary. Then
P(x) = dg = ~j
(5.6)
for some u E A+, j E J. Next g is a proper left factor of x. Consequently, g # J, since J = J A * = XA*, and thus, any word in J has a left factor in X. This shows that 191 < l j l , since otherwise g would belong to the ideal generated by j , thus g E J. It follows from this and from (5.6) that (dl > lul, thus, d = ud’ for some d’ E A*. Moreover d‘ E D(x), since d’(gu) = j u E J and ( g u ) d = gd = x E X. This yields a contradiction by the fact that d‘ is strictly shorter than d. Thus, B(x) E y.
Consider the converse mapping y from Y into X defined by considering for y in Y
C(y)= { e E A + l y
= eh and
he E J }
and by setting y(y) = he, with e E G(y)of minimal length. If y = @(x)= dg is given by (5.4) and (5.5) and if y ( y ) = he with e E G ( y ) , eh = y, then dg = P(x) = eh.
(5.7)
Note that gd E J. Thus, d E G(y).Consequently, Id1 2 lei. Now the word e is not a proper left factor of d. Otherwise, setting d = eu, ug = h in (5.7) with u E A + , we get geu = gd = x,
uge = he E J ,
showing that u E D(x) and contradicting the minimality of Id[. Thus d = e, g = h, and y( /?(x)) = x. An analogous proof shows that /?(y(y)) = y for y in Y. Thus, fl and y are reciprocal bijections from X onto Y. 0
XI. PREFIX CODES
TABLE 2.1
The X - Y Correspondance ~~~~~
~
X
D
Y
aa aba
a, aa a,ba,aba b,bb,abb ba 6,bb
aab bab ba bb
abb ba bb
00
EXAMPLE5.6 Let us illustrate the construction of Proposition 5.11 by considering, over A = {a,b}, the set of semaphores S = {a2,ba, b2}.Then X = A*S Y = SA*
- A*SA+ = {a2,ba,b2,aba,ab2}, - A+SA* = {a2,a2b,ba, bab, b2}.
Table 2.1 lists on each row an element x E X , the correspondingset D(x)and the element P(x) E Y. Proposition 5.1 1 shows that any semaphore code can be transformed into a suffix code by a bijection which conjugates words. This property does not hold for arbitrary prefix codes, as shown by
EXAMPLE5.7 Let X = {ab,ba,c,ac,bca}. Assume that there exists a bijection P which transforms X into a suffix code Y by conjugating the words in X . Then Y necessarily contains c, and ab, ba. Further Y contains ca (with c and ac, Y would not be sufh!). All the words conjugateto bca now have a right factor equal to one of c, ab, ba, ca. Thus, Y is not s&. In fact, X cannot be completed into a semaphorecode, since c is a factor of bca. We end this section with the following result which shows that biprefix codes are not usually semaphore codes.
PROPOSITION 5.12 Let X be a biprefix Semaphore code. Then X = A" for some n 2 1.
Proof It is sufficient to show that X c A" for some n. Let x, y E X . For each right factor q of x, we have q y E A*X c XA*. Thus there is, in view of Proposition 5.3, a left factor p of y such that q p E X . In this way we define a mapping from the set of right factors of x into the set of left factors of y. The set X being sufiix, the mapping is injective; it follows that 1x1 5 Iy 1. Interchangingx and y, we get Iyl 5 1x1. Thus, all words in X have the same length. 0
6.
SYNCHRONOUS CODES
I
15
For semaphore codes, the above result is a particular case of the theorem of synchronization of semaphores to be stated in the next section. For biprefix codes, it is an easy consequence of Theorem 111.4.2.
6. SYNCHRONOUS CODES
Let X be a maximal prefix code over A, and let x be a word. The word x is said to synchronize a word u E A* if ux E X*. The word x E A + is called synchronizing for X if it synchronizes every word in A*, ie., iff A*x c x*. (6.1) It follows from (6.1) that a synchronizingword x is in X* and further that x y (with y E X * ) is synchronizing if x is synchronizing. A maximal prefix code X is synchronous iff there exists a word which is synchronizing. Otherwise the code is called asynchronous.
EXAMPLE 6.1 The code X = b*a is synchronous. Indeed, a is a synchronizing word, since A*a c X*. EXAMPLE 6.2 A biprefix code X over A is asynchronous if X # A. Assume indeed that x E X * is synchronizing. For any u E A*, we have ux E X*. The monoid X * being left unitary, it follows that u E X*. Thus A* = X*. The terminology is derived from the following observation: let w be a word which has to be factored into words of some prefix code X.The appearance, in the middle of the word w, of some synchronizingword x, i.e., the existence of a factorization w = #XU
implies that ux is in X * . Thus we may start the decoding at the beginning of the word v. Since X* is right unitary, we have indeed w E X * iff u E X*. That means that the whole word is in X* iff the final part can be decoded. Note that any code X over A satisfying (6.1) is maximal prefix. Indeed, let y , yu E X . Then ux E X*, and ~ ( u x )(yu)x , are two X factorizations which are distinct iff u # 1. Thus u = 1. Next, (6.1) shows that X is right complete. Any synchronous code is thin. Indeed, if x is a synchronizingword for a code X , then x 2 is not a factor of a word in X, since otherwise uxxu E X for some u, u E A*. From ux E X + ,it would follow that X is not prefix. The fact that a code X is synchronous is well reflected by the automata recognizing X.Let us give a definition. Let d = (Q,i, T )
I
16
11. PREFIX CODES
be a deterministic automaton on A. The rank of a word x fined by rankJx) = Card(Q x). It is an intenger or
E A*
in d is de-
+ co.Clearly rankd(uxv) Irank,(x).
PROPOSITION 6.1 Let X be a maximal prefix code over A, and let x E X*. The following conditions are equivalent: (i) x is synchronizing for X . (ii) For the minimal automaton d(X*), we have rank,(,,,(x) = 1 (iii) There exists a deterministic automaton d recognizing X* such that rank,(x) = 1. Prooj’ (i) (ii) Let d ( X * ) = (Q,i,i). Let q E Q, and let u E A* with i u = q. From ux E X*, it follows that q x = i. Thus Q x = { i } , showing that rank,(,*,(x) = 1. (ii) (iii) is clear. (iii) * (i) Let d = (Q,i, T )and let qo = Q x. Then qo E T. We verify that x is synchronizing. Let u E A*, and set q = is u. From q . x = qo, we have UXEX*. 0
-
-
PROPOSITION 6.2 Let X be a thin maximal preJix code over A, and let P = X A - . Then X is synchronous ifl for all p E P, there exists x E X* such that px E x*. Note that the existence of a unique word synchronizingall left factors is not required in the hypotheses of the proposition. Proof The condition is clearly necessary. It is also sufficient. Let w E A* be such that w is not a factor of a word in X. Let K = ( p l yp z ,. ..,p.} be the set of right factors of w which are in P. The set K is not empty since 1 E K. Define a sequence xl,. . .,x , of words in X* as follows: x 1 is a word in X* such that plxl E X*. If x l , . .., xi- are defined, there exist, because X is right complete, words y E X * , p E P with p i x , “‘xi-l = yp.
Then x , is defined to be a word in X* such that pxi E X*. It follows that for i = 1, ...,n, The word z = wxl x z
(6.2) pix1 “ ‘ X i - l X I EX*. x, is synchronizing for X. Indeed let u E A *. Then uw = y’p’
6.
SYNCHRONOUS CODES
117
for some y' E X* and p' E P. The word p' is right factor of w, since otherwise w would be a factor of a word in X.Thus, p' = pifor some pi E K.Using (6.2),we obtain
x*. 0
uz = y'(p,x, . * * x i ) ( x i + i * * *Ex " )
PROPOSITION 6.3 Let X , Y,Z be maximal prejx codes with X = Yo Z . Then X is synchronous if Y and Z are synchronous. Proof
Let Y c B*, X,Z c A*, and p: B*
+ A*
be such that
x = Yo& First, assume that Y and Z are synchronous, and let y E Y*, z E Z* be synchronizing words. Then B*y c Y* and A*x c Z*, whence A*ZS(Y) c Z*P(Y) = B(B*Y) c B(Y*) =
x*,
showing that zB( y ) is a synchronizing word for X. Conversely, assume that A*x c X * for some x E X * . Then x E Z* and X* c Z*; thus, x is also synchronizingfor 2. Next, let y = B-'(x) E Y*. Then B(B*y) = z * x c A*x c
x* = B(Y*).
The mapping p being injective, it follows that B*y c Y*. Consequently, Y is synchronous. 0 EXAMPLE 6.3 The code X = (A2 - b2) u b2A2 is asynchronous, since it decomposes over the code A 2 which is asynchronous (Example 6.2). It is also directly clear that a word x E X* can never synchronize words of odd length. EXAMPLE 6.4 For any maximal prefix code Z and n 2 2, the code X = Z" is asynchronous. Indeed, such a code has the form X = B" 0 Z for some alphabet B, and B" is synchronous only for n = 1 (Example 6.2).
We now give a result on prefix codes which will be generalized when other techniques will be available (Theorem 111.3.6). The present proof is elementary. Recall from Chapter I that for a finite code X , the order of a letter a is the integer n such that a" is in X . The existence of the order of a results from Proposition 1.5.9. Note that for a finite maximal prefix code, it is an immediate consequence of the inclusion a f c X * P , with P = X A - . THEOREM 6.4 Let X c A + be a Jinite maximal prefix code. If the orders of the letters a E A are relatively prime, then X is synchronous. Proof Let P = X A - and let d = (P, 1,l) be the literal automaton of X*. This automaton is complete since X is maximal prefix. Recall that its action is
I 18
11. PREFIX CODES
given by p * a=
if p a € P, if EX.
pa 1
For all w E A*, define Q(w) = P w.
Then for w, w' E A*, Q(W'W)
c
Card Q(w'w) 5 Card Q(w').
Q(w),
(6.3)
Observe that for all W EA*, Card(Q(w)) = rank, (w). Let u E A* be a word such that Card(Q(u))is minimal. The code X being right complete, there exists u E A* such that w = uu E X+.By (6.3),Card(Q(w)) is minimal. Further w E X + implies (6.4) We will show that Card(Q(w))= 1. This proves the theorem in view of Proposition 6.1. Let a E A be a fixed letter, and let n be the positive integer such that a" E X. We define two sets of integers I and K by 1 E Q(w).
I
I = {i E N Q(w)a' n X #
a},
K = { ~ E { O..., , n - l}lakwEX*}. First, we show that Card I = Card Q(w).
(6.5)
Indeed, consider a word p E Q(w) (cP). There is an integer i such that pa' E X, since X is finite and maximal. This integer is unique since otherwise X would not be prefix. Thus there is a mapping which associates to each p in Q(w) the integer i such that pa' E X. This is clearly a surjective mapping onto 1. We verify that it is also injective. Assume the contrary. Then pa' E X and p'a' E X for p , p' E Q(w), p # p'. This implies Card(Q(wa')) < Card(Q(w)), contradicting the minimality of Card(Q(w)). Thus the mapping is bijective. This proves (6.5). Next set m = max{i k 1 i E I, k E K}.
+
Clearlym 5 maxl
+ maxK 5 m a x l + n - 1. Let R = {m,m+ 1,...,m + n - l}.
We shall find a bijection from I x K onto R. For this, let r E R and for each P E Q(w), let V ( P ) = p ' a'w.
6.
1 19
SYNCHRONOUS CODES
Then v(~)=(~.u').w P *Ew = Q ( w ) .
Thus v(Q(w))c Q(w)and v(Q(w))= Q(w)by the minimality of Q(w).Thus v is a bijection from Q(w) onto itself. It follows by (6.4) that there exists a unique p , E Q(w)such that p,arw E X * . Let i, be the unique integer such that p r d r E X. Then i, E I, whence i, 5 m Ir. Set
r = i, with I
E
+ I n + k,
(6.6)
N and 0 I k, < n. This uniquely defines k, and we have
p,w = (p,a'r)(a")"ak~w). Since p,air E X and X * is right unitary, we have (a")'(ukrw)E X* and also akrwE X*. Thus, k, E K . The preceding construction defines a mapping
r w(i,,k,) (6.7) first by determining i,, then by computing k, by means of (6.6).This mapping is injective. Indeed, if r # r', then either i, # ir,, or it follows from (6.6) and from r f r' mod n that k, # k,,. We now show that the mapping (6.7) is surjective. Let (i, k) E I x K, and let I E N be such that R -+ I x K ,
r =i
+ In + k E R.
By definition of I, there is a (unique) q E Q(w) such that qa' E X,and by the definition of K, we have qa'w
E
x.
Thus, q = p,, i = i,, k = k,, showing the surjectivity. It follows from the bijection that
-
n = Card@) = Card(1) Card(K). This in turn implies, by (6.5), that Card Q(w)divides the integer n. Thus Card Q(w) divides the order of each letter in the alphabet. Since these orders are relatively prime, necessarily Card(Q(w)) = 1. The proof is complete. 0 complete. 0 We will prove later (Section IV.7) the following important theorem. THEOREM 6.5 Let X be a semaphore code. Then there exists a synchronous semaphore code Z and an integer d such that
x = zd. This result admits Proposition 5.12 as a special case. Consider indeed a biprefix semaphore code X c A +. Then according to Theorem 6.5, we have
I20
11. PREFIX CODES
TABLE2.2
The Transitions of d ( X * ) e
l
2
3
4
5
a b
2 4
3 6
1 7
1 5
3 1
6 8
7 9
4
8 3
1
9 .
5
1 1
X = Zd with Z synchronous. The code X being biprefix, Z is also biprefix (Proposition 4.9); but a biprefix synchronous code is trivial by Example 6.2. Thus, Z = A and X = Ad. Theorem 6.5 describes in a simple manner the structure of asynchronous semaphore codes. Indeed, if X = Zd with Z synchronous, then X is asynchronous iff d 2 2 (see also Example 6.4). We may ask whether such a description exists for general maximal prefix codes: is it true that an indecomposable maximal prefix code X is either biprefix or synchronous? Unfortunately, it is not the case, even when X is finite, as shown by EXAMPLE 6.5 Let A = {a, b}, and let X be the prefix code with automaton d ( X ) = (Q,l,l) whose transitions are given in Table 2.2. The automaton d ( X * )is complete, thus X is maximal prefix. In fact, X is finite; it is given in Fig. 2.25.
P
Fig. 2.25 An asynchronous indecomposable code.
7.
I21
AVERAGE LENGTH
Fig. 2.26
To show that X is asynchronous, observe that the action of the letters a and b preserves globally the sets of states
{ L Z 31, (1,4951, {4,6, 71, {1,8,9} as shown in Fig. 2.26. This implies that X is asynchronous. Assume indeed that x E X * is a synchronizing word. Then by definition A*x c X * , whence q x = 1 for all states in q E Q. Thus for each three element subset I , we would have I x = { l}. Further X is not biprefix since b3, a b 4 e X . Finally, the inspection of Fig. 2.25 shows that X is indecomposable.
-
-
7. AVERAGE LENGTH The results of Chapter I concerning the measure of a code apply of course to prefix codes. However, for these codes, considerable extensions exist in two directions. First, the properties proved in Chapter I hold for measures which are much more general than those defined by Bernoulli distributions. Second, there exists a remarkable combinatorial interpretation of the average length of a prefix code by means of the measure of its proper left factors (Proposition 7.2). A function a: A* -+]0,1] is a (positive) cylindric measure if the two following conditions are satisfied: n(1) =
1
and for all w E A*, a(w) =
1 a(wa).
acA
(7.2)
I22
11. PREFIX CODES
The function R is extended to subsets of A * by setting, for L c A*, R(L) =
c
n(u).
UEL
Thus, (7.2) may be written as n(w) = n(wA).Note that this implies, in view of (7.1), that x(A) = 1. More generally, for n 2 0 1,
R(A") =
since n(An+') =
c
A(WA)
C
=
wsAn
A(W)
= R(A").
weAn
A positive Bernoulli distribution is of course a cylindric measure. The converse is false. Example 7.1 shows that cylindric measures are quite general.
EXAMPLE 7.1 Let A = {a,b}, and let (a,,),,2obe a sequence of positive real numbers such that the series a,, converges and
zzo
by Po = 1 and for n 2 1,
Define a sequence
/3,
n- 1
C a*.
= 1-
i=O
Then by construction 0 < p, < 1 (n 2 l),
a,,
+
Bn+l
= /3,
1(n 2 0).
We define a cylindric measure on A* by setting for n 2 0,
a(b"a)= a,,,
x(b")= 8,
and for w = b"au
with n 2 0 and u E A + , x(w) = a,2-'4.
It is easily verified that R is indeed a cylindric measure. Let X = b*a. The real numbers a,,, /3, are reported on the literal representation of X (Fig. 2.27). Note that n(X)= C a, = a. nrO
EXAMPLE 7.2 Let
R:
A* +]O,
13 be a cylindric measure, and let u E A*.
7.
AVERAGE LENGTH
Fig. 2.27 Some values of the cylindric measure.
Define a function p: A* + 30,1] by
Then p is a cylindric measure since a(1) = 1 and
PROPOSITION 7.1 Let II be a cylindric measure on A*. 1. For any prejix code X , we have
.(X) I 1. 2. For any jinite maximal prefix code, we have
.(X)
=
1.
For Bernoulli distributions, this follows from Theorems 1.4.2 and 1.5.10and from the fact that a finite set is thin. Proof We first show 2. If Card@) = 1, or X = A, then the result is clear. Otherwise, let x E X be a word of maximal length, and let t E A*, a E A be such that x = ta. Then by the maximality of x, t A c X. If t = 1, then X = A. Thus, t # 1. The set Y = (X- t A ) u t is a maximal prefix code (Proposition 4.6). Next, Y has strictly fewer elements than X;this comes from Card(A) 2 2. Further
K ( Y ) = .(X) - .@A)
+ a(t) = K ( X ) .
This shows that n(X) = 1 by induction of the cardinality.
'14
11. PREFIX CODES
To prove statement 1, let X be an arbitrary prefix code and let
x, = {x E x 11x1 5 n}. According to what we just proved, we have n(X,) 5 1. Thus, n(X) = supn(X,) I1. 0 nTO
EXAMPLE 7.1 (continued). The code X = b*a is maximal prefix. Nevertheless, n(X)= a < 1. This shows that the second part of Proposition 7.1 does not hold for infinite codes. In addition, since any number a €10, 1[ can be written in the form given by (7.3), the cylindric measure of the infinite maximal prefix code X can take any value in the interval 10, I]. Given a prefix code X c A' and a cylindric measure K on A* such that n(X) = 1, the average length of X (relatively to n) is defined by
It is a nonnegative real number or infinite. The context always indicates which is the underlying cylindric measure. We therefore omit the reference to it in the notation. The quantity A(X) is in fact the mean of the random variable assigning to each x E X its length 1x1. PROPOSITION 7.2 Let X be a prefix code and let P = XA-. Further, let n be a cylindric measure such that n(X) = 1. Then A(X) = n(P).
Proof
We start the proof by showing that each p
E
P satisfies
n(pA* n X) = n(p).
(7.4)
Consider indeed the function p: A* --t ]0,1] defined by P(W) = NPw)/n(P)* In view of Example 7.2, it is a cylindric measure. On the other hand PA* n X = p(p-'X), and by Proposition 4.6, the set p- 'X is a prefix code. Proposition 7.1 therefore implies that p(p-'X) 5 1. From P(P-'x) = 4PA* n X M P ) it follows that n(p) 2 n(pA* n X).
(7.5)
7.
125
AVERAGE LENGTH
Next let Y = (X
- (PA* n X))u p .
By the same Proposition 4.6, the set Y is a prefix code; according to Proposition 7.1, n ( Y )I1. Thus, n ( X ) - n(pA* n X ) + n(p)I1. By assumption, n ( X ) = 1. Consequently n(p)In(pA* n X ) . Together with ( 7 3 , this yields (7.4). Now, we observe the following identity concerning formal power series
Indeed, the multiplicity of a word x E X on the right-hand side of (7.6) is the number of its left factors in P. This number is precisely its length. It follows from (7.6) that
The left-hand side is A(X), and by (7.4), we obtain A(X) =
1 n(p)= n(P).
0
PEP
For a finite maximal prefix code, the cylindrical measure equals 1. Thus, COROLLARY 7.3 Let X be afinite maximal prefix code and P = X A - . For any cylindric measure n on A*, the following holds: A(X) = n(P). 0
For a Bernoulli distribution, the finiteness condition can be replaced by the condition to be thin. COROLLARY 7.4 Let X be a thin maximal prefix code, and P = X A - . For any positive' Bernoulli distribution n on A*, we have
n(x)= n(P). Further, the average length A(X) isfinite. Proof The code X being maximal, Theorem 1.5.1 1 shows that n(X)= 1; thus, the equality A(X) = n(P)follows from Proposition 7.2. Moreover, P is thin since each factor of a word in P is also a factor of a word in X. By Proposition 1.5.6, n(P) is finite. 0
I 26
11. PREFIX CODES
We shall see in Chapter VI that the average length is still finite in the more general case of thin maximal codes.
7.3 Let A = {a,b} and X = a*b. For any positive Bernoulli EXAMPLE distribution a, let a(a) = p, n(b) = q. Then
q x ) = n(a*) = l/q. EXAMPLE 7.4 Let D be the Dyck code over A = {a, b} (see Example 1.4.5). We have seen that for a Bernoulli distribution given by .(a) = p , n(b) = q, the following formula holds: n(D) = 1 - Ip - 41. Further, setting d, = a(D n A"), we have by formula (1.4.14),
It follows that, for p = q = 3, we have A(D)= 1 and
This series diverges since, according to Stirling's formula,
Thus, the average length of D is infinite for p = q = 4. The next example concerns the computation of the average length of semaphore codes. We start with an interesting identity. PROPOSITION 7.5 Let X c A + be a semaphore code, P = X A - and let S be the minimal set for which X = A*S - A*SA+. For s, t E S , let
I
X , = X n A*s and R,,, = { w E A* sw E A*t and IwI
-= Itl}.
Thenfor all t E S,
(7.7) Proof First, we observe that each product X,R, is unambiguous, since X , is prefix. Further any two terms of the sum are disjoint, since X = U X , is prefix. Thus, it suffices to show that Pt =
U X,R,. saS
7.
AVERAGE LENGTH t
W
X
Fig. 2.28 Factorizations of pt.
First let p E P, and let x be the shortest left factor of pt, which is in A* S. Then x E X and pt = xw
for some w E A*. Next x E X,for some s E S. Set x = us. The word p being in P, we have IpI < 1x1, whence IwI < (ti(see Fig. 2.28). Now p cannot be a proper left factor of u, since otherwise s would be a proper factor of t, contradicting Proposition 5.7 and the minimality of S. Thus, u is a left factor of p and sw E A*t, showing that w E Rst. Conversely, let x E X,and w E R,, for some s, t E S. Then x = us and sw = It for a proper left factor 1 of s. Then ul is a proper left factor of us = x; thus, ul E P and xw = ult E Pt. 0 COROLLARY 7.6 With the notations of Proposition 7.5, we have for any Bernoulli distribution n, the following system of equations: STS
1 n(X,) = 1.
0
SES
For the case of a finite set S, the system (7.8) is a set of 1 + Card@) linear equations in the 1 + Card@) unknown variables n(X,) and A(X).The sets R,, being finite, the coefficients n(R,,)are easily computed. This yields the desired expression of A(X). In the special case where S is a singleton, we get
I
7.7 Let s E A', let X = A*s - A*sA+ and R = { w E A* COROLLARY sw E A*s and 1wI < Isl}. Then for any positive Bernoulli distribution 'IC, we have l ( X ) = x ( R ) / n ( ~ ) .0
EXAMPLE 7.5 Let A = {a, b} and consider s = aba. The corresponding set R is R = {l,ba}. If n(a) = p and n(b) = q = 1 - p , then for X = A*aba A*abaA+,we get
n(x)= -.1 + P4 P24
I 28
11. PREFIX CODES
Now choose s' = baa. The corresponding R' is the set R' = {I). Thus, for X = A*baa - A*baaA', we have 1 A ( X ) = -7j 4P For p = q = $, this gives A ( X ) = 10, A(X') = 8. This is an interesting paradox: we have to wait longer for the first appearance of aba than for the first appearance of baa! 8. DECIPHERING DELAY
Let X be a subset of A'. Then X is said to have finite deciphering delay if there is an integer d 2 0 such that VX,X' E X, Vy E X d , VU E A*,
xyu
E x'X*
x = x'.
(8.1)
If (8.1) holds for some integer d, then it holds for all d' 2 d. If X has finite decipheringdelay, then the smallest integer d satisfying (8.1)is the deciphering delay of X . This notion is clearly oriented from left to right; it is straightforward to define a dual notion (working from right to left). The terminology is justified by the following consideration: let w E A* be a word having two left factors in X', and such that the shorter one is in X' 'd. If (8.1)holds, then the two X-factorizations start with the same word in X. Thus, the "delay" between the moment when, reading from left to right, a possible factor of an X-factorization is discovered, and the moment when these factors are definitively valid, is bounded. It follows from the definition that the sets with delay d = 0 are the prefix codes. This is the reason why prefix codes are also called instantaneous codes. In this sense, codes with finite delay are a natural generalization of prefix codes.
PROPOSITION 8.1
A subset X of A', which has a finite deciphering delay, is a
code.
Proof Let d be the deciphering delay of X. Assume that X is not a code. Then there is an equality w = X ' X Z " ' X , = y,y,..*y,,
x1
#y,
with n, m 2 1, xl,. . .,x,, yl,. . .,y, E X. Let z E X. Then wzd E y,X*. By (8.1), we have x1 = y , . Thus, X is a code. 0
EXAMPLE8.1 The suffix code X delay. Indeed, for all d y = ba # b.
= {aa, ba, b} 2 0, the word b(aa)dE X' 'd
has an infinite deciphering is a left factor of ~ ( U Uwith ) ~
8.
DECIPHERING DELAY
129
We now study maximal codes with finite deciphering delay. The following result is similar to Proposition 1.52. However, it is less general and we do not know of a simple construction to embed a code with finite deciphering delay into a complete one. PROPOSITION 8.2 Let X be a subset of A + which has finite deciphering delay. I f y E A + is an unbordered word such that X*yA* n X * = 0,
then Y = X u y has finite deciphering delay. Proof Consider the set I/ = X * y . It is a prefix code. Indeed, assume that v = x y and v‘ = x‘y with x, x’ E X * , and v < v’. Then necessarily v I x‘ since y is unbordered. But then x’ E X*yA*, a contradiction. Note also that V + A * n X * = $3
since V + A * c VA*. 0 Let d be the deciphering delay of X and let e =d
+ Jyl.
We show that the deciphering delay of Y is at most e. For this, let us corisider a relation w = y l y 2 ” . y e + l U = v;y;...y:,
,,
with y,, ... , y e + y;, .. .,y; E Y , u E A* and, arguing by contradiction, assume that y , # y’,. First, let us verify that one of y,, . . ., y e + is equal to y. Assume the contrary. Then y, . . * y d +E, X d + ’ . Let 4 be the smallest integer such that (Fig. 2.29) yl*“Yd+l
I Y’,”*yb.
The delay of X being d, and y, # yi, one among y’, ,. . .,y; must be equal to v2 Ydtl
Vf,
Fig. 2.29
Yet1
11. PREFIX CODES
130
y. We cannot have y; = y for an index i < q, since otherwise y , - * - y d + E V + A * n X*. Thus, yb = y and y ; ...yb E V . Note that fl*'*yb-1
Yl'**yd+l*
Next (yd+2.-.ye+l( 2 e - d = Iyl. It follows that Y;*-Yb ~ Y l . ' . Y e + l But then y , ye+ E X* n X*yA*, which is impossible. This shows the claim, namely, that one of yl, . ..,ye+ is equal to y. It follows that w has a left factor y1y2 y, in V with y,, . .. ,y p- E X and y p = y. By the hypothesis, one of y;, . . .,y; must be equal to y. Thus w has also a left factor y;y; * * yb in V with y', ,.. .,yb- E X and yb = y. The code V being prefix, we have Y l Y 2 '.Y p - 1 = Y;Y; * * * Yb- 1* Since X is a code, this and the assumption yl # y; imply that p = q = 1. But then y p = y = yq. This yields the final contradiction. 0
-
,
,
--,
,
Proposition 8.2 has the following interesting consequence. 8.3 Let X be a thin subset of A + .If X has finite deciphering delay, THEOREM then the following conditions are equivalent
(i) X is a maximal code, (ii) X is maximal in the family of codes with finite deciphering delay.
Proof The case where A has just one letter is clear. Thus, we suppose that Card(A) 2 2. It sufficesto prove (ii) * (i).For this, it is enough to show that X is complete. Assume the contrary and consider a word u which is not a factor of a word in X*.According to Proposition 0.3.6,there exists u E A* such that y = uv is unbordered. But then A*yA* n X * = 0 and by Proposition 8.2, X u y has finite deciphering delay. This yields the contradiction. 0
We now state and prove the main result of this section. THEOREM 8.4 Any finite maximal code with finite deciphering delay is prefix. In an equivalent manner, a maximal finite code either is prefix or has infinite deciphering delay. The proof'of the theorem is rather long. It requires new concepts which will be illustrated in a different way in Chapter VI. Let X be a subset of A'. A words E A* is simplifying (for X ) if for all x E X*, V E A*, XSVEX* * SVEX*.
8.
'3'
DECIPHERING DELAY
The set of simplifying words is denoted by S ( X ) or S. It is a right ideal. Further X* is right unitary iff 1 E S, thus, iff S = A*. A word p is extendable (for X ) if, for all u E A*, there exists u E A* such that puu E X * . Clearly, an extendable word is right completable. The set of extendable words is denoted by E ( X ) or E. As for S, it is a right ideal. Further, X is right complete iff 1 E E; thus, iff E = A*. Of course the notions of simplifying and extendable words are left-to-right oriented,just as the notion of deciphering delay.
8.5 Let X c A + be a code. If both E and S are nonempty, then PROPOSITION E = S. Proof Let us show first the inclusion S c E . Let s E S, p E E . Note that pt E X * for some word t and that pt still is extendable.Thus, we may assume that p E E n X*. Consider any word u E A*. Since p E E, the word psu can be completed: there is a word u E A + such that psuu E X * . But p is in X* and s is simplifying. Thus, suu E X * , showing that s is extendable. Conversely, let s E S, p E E. To show that p is simplifying, let x E X * , u E A* such that xpu E X * . Since the word pus is right completable, we have pusw for some w E A*. But then xpusw E X*'also and since s is simplifying, we have sw E X * . Thus, finally, the four words x , x(pu),( p u ) (sw),and sw are in X * . The set X* is stable, thus pu E X * . This shows that p is simplifying. 0 E X*
Let X c A + be a code and let w E A*. A right context of w is a word u E A* such that there exist x l , ...,x, E X with 1. wu = X 1 X 2 " ' X "
2. u is a proper right factor of x,. The set of right contexts of w is denoted by C,(w).This set is nonempty iff w is right-completable in X*. Further 1 E C,(w)iff w E X * . Recall that if S ( X ) # 0,then it is a right ideal. Its initial part U=S-SA+ is prefix and UA* = S .
PROPOSITION 8.6 Let X be a code such that S = E # 121 and let U = S S A + . For all w E A*, we have 1. The set C,(w)U is prefix. 2. The product C,(w)U is unambiguous. 3. Zf w E S,then C,(w)U is maximal prefix.
11. PREFIX CODES
132
Proof
We first verify the following property:
if uuz = u'u' for u, u' E C,(w),u, u' E U , and z E A*, then u = u', u = u', z = 1
(*)
Indeed, first note that u E E. Thus, there exists t E A* such that uzt E X*.Then (wu)(uzt)= (wu')(u't). (8.2) Each one of the first three parenthesized words is in X*.Now the fourth word, namely u't, is also in X*,because u' is simplifying. The set X being a code, the word in (8.2) has a unique factorization in words in X , starting with wu, and also with wu'. It follows that u = u'y or. u' = uy for some y E X*.This implies that u = u' as follows: assume, for instance, that u = u'y, and set wu = X ~ X 2 " ' X n , wu' = x;*.*x;, y = y, y,, with x,,. ..,x,, x i , . . .,&, yI,. ..,y, E X.Then (x,J > Iu( and assuming p > 0, we have on the one hand (Fig. 2.30) a ' .
l ~ p5 l
IYI 5 IvI < IXnI,
and on the other hand, by X1X2"'Xn
= x;*-x;y,*-y,,
we have x, = y,. Thus p = 0, y = 1, and u = u'. Going back to (8.2), this gives uz = u'. Now U is prefix. Consequently z = 1 and u = u'. This proves property
(*I.
It follows immediately from (*).that C,(w)U is prefix, and also, taking z = 1, that the product C,(w)V is unambiguous. This proves 1 and 2. To prove 3, we show that C,(w)S is right dense. For this, consider a word t E A*. The word
V
W
-
-
Fig. 2.30 Factorization of wu = wu'y.
wt is right completable, since w E E. Thus, wtt' E X* for some t' E A*. Thus, it' is in w-'X*. Consequently tt' = uy for some u E C,(w), y E X * . Now observe that w E E, and consequently also yw E E. Thus, tt'w = uyw E C,(w)S. This shows that C,(w)S is right complete. From C,(w)S = C,(w)UA* it follows then by Theorem 3.3 that the prefix set C,(w)U is maximal prefix. 0
To be able to use these propositions in the proof of the theorem, we verify that the hypothesis of the propositions are satisfied: we show that S and E are nonempty. PROPOSITION 8.7 Let X be a code with jinite deciphering delay. Then
X dc S(X). Proof Let x E X d , let further x l , x 2 , .. .,x p E X and u E A*, be such that x 1 x 2 * * ~ x PExXu .Thus X,X2"'XPXU
=y,y,***y,
for some y , , . . .,y, E X. From the fact that X has delay d , it follows that xl = y 1 , x 2 = y 2,...,x p = y p , whence q 2 p and x u = y , + , . . . y , . Thus, X D E X*. This shows that x is simplifying. 0 PROPOSITION 8.8 Let X be a maximal code with jinite deciphering delay d. Then Xd c E(X). Proof The case of a one letter alphabet is clear. Thus, assume that Card(A) 2 2. Let x E Xd and u E A*. By Proposition 0.3.6, there is a word u E A* such that y = xuu is unbordered. This implies that X*yA* n X* # 0.
Indeed, otherwise X u y would be a code by Proposition 8.2, contradicting the maximality of X. Consequently, there exist z E X * , w E A* such that zyw E X*. By Proposition 8.7, x is simplifying; thus, zyw = zxuuw E X* implies xuuw E X*. This shows that x is extendable. 0 Proof of Theorem 8.4. Let X be a maximal finite code with finite deciphering delay d. According to Propositions 8.7 and 8.8, both S ( X ) and E(X) are nonempty. Thus by Proposition 8.5, they are equal. Set .S = S(X) = E(X).
Then Xd c S, further S is a right ideal, and the prefix set
U
= S - SA'
satisfies S = UA".
11. PREFIX CODES
I34
We claim that U is a finite set. Indeed, set
6 = d maxlxl X€X
and let us verify that a word in U has length 5 6 . For this, lets E S with Is( > 6. The words tieing extendable, there is a word w E A* such that sw E X*.By the choice of 6, the word sw is a product of at least d + 1 words in X,and s has a proper left factor, say s', in X d . From X d c S,we have s E SA'; thus, s 4 U. This proves the claim. Now, we fix a word x E X d ,and consider the set C,(x) of right contexts of x. The set C,(x) is finite since each element of C,(x) is a right factor of some word in the finite set X. By Proposition 8.6(3), the set 2 = C,(x)U is a maximal prefix set, since x E X d c S.Further, Z is the unambiguous product of the finite sets C,(x) and U.By Proposition 4.10,both C,(x) and U are maximal prefix sets. Since 1 E C,(x), we have C,(x) = { l}. Thus, we have shown that C,(x) = { l} for x E X d . This implies as follows that X is prefix. Assume that y, y' E X and yt = y' for some t E A*. Let x = y d . Then x t = ydt = yd-'y' and It1 < (y'l show that t E C,(x). Since x E X d , we have t = 1.Thus, X is a prefix code. 0 The following examples show that Theorem 8.4 is optimal in several directions, EXAMPLE 8.2 The suffix code X = {aa,ba, b} is a finite maximal code and has infinite deciphering delay. EXAMPLE 8.3 The code {ab,abb, baab} has deciphering delay 1. It is neither prefix nor maximal: indeed, the word bbab, for instance, can be added to it. EXAMPLE 8.4 The code X = ba* is maximal and suffix. It has deciphering delay 1. It is not prefix, but it is infinite.
EXERCISES SECTION 1 1.1. Let A be a finite alphabet, and let P be a prefix-closed subset of A*. Show that Pis infinite iff there exists an infinite sequence(pn)" of elements in
P such that Pz < P3 < " ' * 1.2. Let A be a finite alphabet and let X c A + be a prefix code. Set R = A* - XA*. Show that for all n 2 1, A" = ( R n A") u (XA* n A"), (*I P1
'35
EXERCISES
where the union is disjoint. Let k = Card(A)and a,, = Card(X n A") for n 2 1. Derive from (*) that
u,k-" I 1. nz 1
(This gives an elementary proof of Corollary 1.4.3 for prefix codes. See also Proposition 7.1.) SECTION 2 2.1.
Let X c A + be a prefix code. Let P = XA- and let
d
= (P, 1,l)
be the literal automaton of X*.Consider an automaton d = (Q, i, i)
which is deterministic, trim, and such that X* = Stab(i).Show that there is a function p:
P+Q
with p(1) = i and such that for a E A, P(P ' 4 = P(P)
(1.
SECTION 3 3.1.
Let X c A + be a finite maximal prefix code and P = XA-. Show that Card(X) - 1 = Card(P)(Card(A)- 1).
3.2. Let A be an alphabet, and let M(A) be the monoid of prefix subsets of A* equipped with the induced product. Show that M(A) is a free monoid and that the set of maximal (resp., recognizable) prefix sets is a free submonoid of M(A). (Use Exercise 1.2.2. and set y ( X ) = minxex1x1). SECTION 4 4.1.
Let A = {a,b}. Associate to each maximal prefix set 2 c A*, a word y ( 2 ) E A* as follows:
Y(m
=1
and if 2 = aX u by, Y(Z)= aY(X)bY(Y)* Let D c A + be the Dyck code and D, = D n aA*. Show that y is a bijection of the set of maximal prefix sets onto DZ and further that I y ( 2 ) l = 2Card(Z) - 2.
136
11. PREFIX CODES
4.2.
Derive from this that the number of maximal prefix sets with n elements is Card@: n A'"-') = (l/n)(?--?) (cf. Example 1.4.5). Let X and Y be two prefix codes over A, and P = A* - X A * ,
Q = A* - YA*.
Set R=PnQ.
Show that there exists a unique prefix code Z = X A Y such that
Z = R A - R. Show that Z = ( X n Q ) u (X n Y )u (P n Y). 4.3.
Show that if X and Y are maximal prefix sets, then so is Z. Let A be a finite alphabet. Show that the family of recognizable maximal prefix codes is the least family 9of subset of A* such that (i) A E 9, (ii) if X , Y E 4 and if X = X I u X , is a partition in recognizable sets X I , X , , then
z = x , VXZYE9. (iii) if X E 4 and if X = X, u X, is a partition in recognizable sets, then
z = x:x, E 9. SECTION 5 5.1.
Let X c A* be a prefix code. Show that the following conditions are equivalent. (i) A*X = X + . (ii) X is a semaphore code, and the minimal set of semaphores S=X-A+X
satisfies SA* n A*S = SA*S u S .
Note that for a code X = A*w - A*wA+,
the conditions are satisfied provided w is unbordered
137
EXERCISES
5.2.
Let J c A + be a two-sided ideal. For each x E J , denote by llxll the greatest integer n such that x E J"
andset IIxII = O f o r x # J . Show that, for all x, y E A* llxll
+ IlYll G
IIXYII G llxll
+ IlYll + 1
SECTION 6 Let X c A + be a finite maximal prefix code. Show that if X contains a letter a E A, then there is an integer n 2 1 such that a" is synchronizing. 6.2. Let X c A* be a synchronous prefix code. Assume that the automaton d ( X * ) has n states. Show that there exists a synchronizing word of length at most n3. 6.1.
SECTION 7 7.1.
Let X c A* be a maximal prefix code, and let a: X + ]0,1] be a function such that C a(x) = 1. xsx
7.2.
Show that there is a cylindric measure on A* such that a(x) = a(x) for x E X. Show that, moreover, n may be chosen such that ~ ( x y= ) n(x) n(y)for all x, y E X * . Let X c A + be a code and let a: X +]O, 11 be a function such that
c
.(X) = 1.
xcx
Define the entropy of X (relatively to a) to be
H(X)= -
c Wlog,
n(x),
xsx
where k = Card(A). Set A ( X ) = Show that
cxsX IxIa(x).
H(X)I A(X) and that the equality holds iff n(x) = k-1"'
for x E X.
Show that if X is finite and has n elements, then H(X)I log,n.
138
11. PREFIX CODES
7.3.
Let B be a finite set and let A: B + R, be a function. Also, let A = {a,b}. For every function a: B 4 A* set
We consider injective functions a such that a(B)is prefix, and we look for such a function with A(a) minimal. Such a function is called a Hugman encoding of (By A). Show that the following algorithm allows us to obtain a Huffman two elements of B such that n(cl), n(c2)5 n(c) for all c in B - {c, ,c2}. Let
B' = B - { c ~ , c Z } u { d } with d # B and define A': B' R, by n'(c) = A(C) for all c E B' - {d}and A'(4 = 4c1) n(c2). Let a' be a Huffman encoding of (B', A ' ) and let a be the function from B into A* defined by
+
a(c) = a'(c)
for c E B - {cl ,cz},
a(cz)= a'(d)b. a(cl) = a'(& Show that a is a Huffman encoding of (By n). SECTION 8 8.1.
For a set X c A', define, as in Section 1.3, a sequence (U,Jnro of subsets of A* by setting
U'
=
x-'x - 1,
un,
= x-'U"
u
u,'x,
n 2 1.
Show that X has finite deciphering delay iff all sets U,,are empty for sufficiently large n. 8.2. Let Y and Z be composable codes with finite decipheringdelay d( Y)and d ( 2 ) . Show that X = Y o Z has finite delay d(X)5 d(Y)+ d ( Z ) .(Hint: show that for y E Xd(r),z E Xd''), we have yz E S(X).) 8.3. Let X = {x, y} be a two-element code, Show that the deciphering delay of X is at most one. 8.4. Let X c A* be a finite code. (a) Show that there exists a smallest submonoid M c X* such that M is generated by a code with finite deciphering delay. (b) Let Y c A* be the base of the submonoid whose existence is asserted in (a). Show by a proof analogous to that of Proposition 1.2.10 that
Y c x(Y*)-'n (Y*)-'X*
NOTES
‘39
Deduce from this if X does not have finite deciphering delay, Card(Y) I Card(X) - 1. NOTES
The results of the first four sections belong to folklore, and they are known to readers familiar with automata theory or with trees. Semaphore codes were introduced in Schutzenberger(1964) under the name of f codes. All the results presented in Section 5 can be found in that paper which also contains Theorem 6.5. and Proposition 7.5. The notion of synchronous prefix code has been extensively studied in the context of automata theory. Let us mention Cerny’s problem which can be formulated as followsin our context: given a synchronous prefix code X whose minimal automaton d ( X * )has n states, what upper bound can be given to the length of the shortest synchronizingword as a function of n? See Exercise 6.2, Moore (1956), Cerny (1964), and Pin (1978). Example 6.5 is obtained by a construction of Perrin (1977a) (see Exercise VII1.4.1). The synchronization properties of a special class of prefix codes called inclusion codes have been studied by Bobrow and Hakimi (1969) and Boe (1972). The results of Section 7 are given in another terminology in Feller (1957). The pair formed by a prefix code X and a cylindric measure x such that n(xy) = n ( x ) x ( y )for all x, y E X* defines what Feller calls a recurrent event. The notion of decipheringdelay appears at the very beginning of the theory of codes (Gilbert and Moore, 1959; Levenshtein, 1964). Theorem 8.4 is due to Schutzenberger (1966). It was conjectured in Gilbert and Moore (1959). An incomplete proof appears in Markov (1962). A proof of a result which is more general than Theorem 8.4 has been given in Schutzenberger (1966). A characterisation of the coding morphism for a code with finite deciphering delay is given in Choffrut (1979). The monoid of prefix subsets defined in Exercise 3.2 has been further studied by Lassez (1973). The description of the Huffman algorithm (Exercise 7.3) is commented on in Knuth (1973) which also contains other interesting algorithms on trees. Exercise 8.4 is from Berstel et al. (1979). An analogous result is proved in Salomaa (1981). Let us mention the following result which has not been reported here: For a three-element code X = {x, y,z}, there exists at most one right infinite word with two distinct X-factorizations (Karhumaki, 1983).
CHAPTER
I11
Biprefix Codes
0. INTRODUCTION
The object of this chapter is to describe the structure of maximal biprefix codes. This family of codes has quite remarkable properties and can be described in a rather satisfactory manner. As in the rest of this book, we will work here within the family of thin codes. As we will see, this family contains all the usual examples, and most of the fundamental properties extend to this family when they hold in the simple (i.e., finite or recognizable) case. To each thin maximal biprefix code, two basic parameters will be associated: its degree and its kernel. The degree is a positive integer which is, as we will see in Chapter IV, the degree of a permutation group associated with the code. The kernel is the set of code words which are proper factors of some code word. We shall prove that these two parameters characterize a thin maximal biprefix code. In the first section,we introduce the notion of a purse of a word with respect to a biprefix code. It allows us to define an integer-valued function called the indicator of a biprefix code. This function will be quite useful in the sequel. In the second section, we give a series of equivalent conditions for a thin code to be maximal biprefix. The fact that thin maximal biprefix codes are extremal objects is reflected in the observation that a subset of their properties ‘40
'4'
I. PARSES
suffices to characterize them completely. We also give a transformation (called internal transformation)which preserves the family of maximal biprefix codes. Section 3 contains the definition of the degree of a thin maximal biprefix code. It is defined as the number of interpretations of a word which is not a factor of a code word. This number is independent of the word chosen. This fact will be used to prove most of the fundamental properties of biprefix codes. We will prove that the degree is invariant under internal transformation. In the fourth section, a construction of the thin maximal biprefix code having a given degree and kernel is described. We also describe the deriued code of a thin maximal biprefix code. It is a code whose degree is one less than the degree of the original code. Both constructions are consequences of a fundamental result (Theorem 4.3) which characterizes those sets of words which can be completed in a finite maximal biprefix code without modification of the kernel. Section 5 is devoted to the study of finite maximal biprefix codes. It is shown that for a fixed degree and a fixed size of the alphabet, there exists only a finite number of such codes. Further it is proved that, on this finite set, the internal transformation acts transitively. 1.
PARSES
A biprefix code is a subset X of A' which is both prefix and suffix. In other words, we have XA'
r\
X =
a,
A'X n X = 0.
(1.1)
An X-parse (or simply a parse) of a word w E A* is a triple (u,x,u) (see Fig, 3.1) such that w = uxu and VEA*-A*X,
XEX*,
UEA*-XA*.
An interpretation of w E A* is a triple (u,x, u) such that w = uxu and UEA-X,
XEX*,
UEXA-.
Since the code X is biprefix, we have A - X c A* - A*X, and X A - c A* - X A * , thus any interpretation of w is also a parse of w.
... V
X
Fig. 3.1 An X-parse of w.
U
111. BIPREFIX CODES
‘4‘ Y V 0
r
S
0
0
Fig. 3.2 A parse of w passing through the point (r,s).
A point in a word w E A* is a pair (r,s) E A* x A* such that w = rs. A word w thus has IwI 1 points. A parse (0, x, u) of w is said to pass through the point (r,s) provided x = yz for some y, z E X* such that r = uy, s = zu (see Fig. 3.2).
+
PROPOSITION 1.1 Let X c A be a biprefix code. For each point of a word w E A*, there is one and only one parse passing through this point. +
Proof Let (r, s) be a point of w E A*. The code X being prefix, there is a unique z E X*, and a unique u E A* - XA* such that s = zu (Theorem 11.1.4). Since X is suffix, we have r = uy for a unique u E A* - A*X and a unique y E X*. Clearly (0, yz, u) is a parse of w passing through (r,s). The uniqueness follows from the uniqueness of the factorizations of s and r. 0
PROPOSITION1.2 Let X c A + be a biprejix code. For any w E A*, there are bijections between the following sets: 1. the set of parses of w, 2. the set of left factors of w which have no right factor in X, 3. the set of right factors of w which haw no left factor in X.
Proof Set V = A* - A*X, U = A* - XA*. For each parse (u,x,u) of w, the word u is in V and is a left factor of w. Thus u is in the set described in 2. Conversely, if w = uw’ and u E V, set w’ = xu with x E X* and u E U (this is possible since X is prefix). Then (u,x,u) is a parse. The uniqueness of the factorization w’ = xu shows that the mapping (0, x, u) Hu is a bijection from the set of parses on the set described in 3. 0 Let X be a biprefix code over A. The indicator of X is the formal power series L, (or simply L )which associates to any word w the number (L,w) of X-parses of w. Setting U = A* - XA*, Y = A* - A*X, we have the result
-m*_v
L= Note that XA* = u*since X is prefix, and & X
(1.2) = A*X since X is suffix. = A*(1 - X).Substituting this in
Thus = A* - XA* = (1 - X)A* and y (1.2), we obtain L = A*(1 - 1()A*.
(1.3)
I. PARSES
'43
This can also be written as L = -VA* = A*_U.
(1.4)
Note that this is a compact formulation of Proposition 1.2. From formula (1.3), we obtain a convenient expression for the number of parses of a word w E A*: (L,w ) = IWI
+ 1 - @*&A*, w).
(1.5) The term (A*XA*,w ) equals the number of occurrences of words in X as factors of w. Thus we see from (1.5) that for any biprefix codes X , Y the following implication holds: YCX * LxILy. (1.6) (Recall that the notation L, IL , means that ( L x ,w ) I( L y ,w ) for all w in A*).
PROPOSITION 1.3 Let X c A + be a biprejx code, let U = A* V = A* - A*X, and let L be the indicator of X . Then
-v = L(1 - A), _U = (1 - A)L, 1 - g = (1 - A)L(l - A).
- XA*,
(1.7)
(1.8) Proof Formula (1.7) follows from (1.4), and (1.8) is an immediate consequence of (1.3). 0
PROPOSITION 1.4 Let X c A + be a biprejx code and let L be its indicator. Then for all w E A* 0 I ( L ,w) - 15
JWI.
(1.9)
In particular, (L, 1) = 1. Further, for all u, u, w E A*, (L,v ) I(L,uuw).
(1.10)
Proof For a given word w, there are at most J w J+ 1 and at least one (namely, the empty word) left factors of w which have no right factor in X . Thus (1.9) is a consequence of Proposition 1.2. Next any parse of u can be extended to a parse of uuw. This parse of uvw is uniquely determined by the parse of u (Proposition 1.1). This shows (1.10). 0
EXAMPLE1.1 The indicator L of the biprefix code X = 0 satisfies (L, w ) = IwI
+ 1 for all w E A*.
EXAMPLE1.2 For the biprefix code X = A , the indicator has value (L,w ) = 1 for all w E A*. The following proposition gives a characterization of formal power series which are indicators.
111. BIPREFIX CODES
'44
PROPOSITION 1.5 A formal power series L E Z ( ( A ) ) is the indicator of a biprefix code iff it satisfies the following conditions: (i) For all a E A, w E A*, 0 I (L,aw) - (L,w) I 1,
(1.11)
0 I (L,wa) - (L,w) I1.
(1.12)
(ii) For all a, b E A and w E A*,
+
(L,aw) (L,wb) 2 (L,w) + (L,awb).
(1.3)
(iii) (L, 1) = 1. Proof Assume that L is the indicator of some biprefix code X.It follows from formula (1.7) that the coefficients of the series L(l - 4) and (1 - A)L are 0 or 1. For a word w E A* and a letter a E A, we have (L(1 - A), wa) = (L,wa) - (L,w). Thus, (1.12)holds. The same holds for (1.11). Finally, formula (1.8)gives for the empty word, the equality (L, 1) = 1, and for a, b E A , w E A*,
-(g,awb) = (L,awb) - (L,U W ) - (L,wb) + (L,w), showing (1.13). Conversely, assume that L satisfies the three conditions. Set S = (1 - 4 ) L . Then (S, 1) = (L,1) = 1. Next for a E A, w E A*, we have (S,aw) = (L,aw) - (L,w).
By (1.1l),0 I (S,aw) I 1, showing that S is the characteristic series of some set U containing the empty word 1. Next, if a, b E A, w E A*, then by (1.13) (S,U W ) = (L,uw)- (L,W ) 2 (L,awb) - (L,wb) = (S,awb).
Thus, awb E U implies aw E U,showing that U is prefix-closed. According to Theorem 11.1.4, the set X = UA - U is a prefix code and 1 - 3 = U(1 -4). Symmetrically, the series T = L( 1 - 4) is the characteristic series of some nonempty suffix-closed set V, the set Y = A Y - Y is a suffix code and 1 -Y=(l--d)y, Finally 1 - g = _u(1- 4) = (1 - A)L(l- 4) = (1 - A)Y = 1 - 1. Thus, X = Y and X is biprefix with indicator L. 0 2. MAXIMAL BIPREFIX CODES
A code X c A 'is a maximal biprefix code if, for any biprefix code Y c A ', the inclusion X c Y implies that X = Y. As in the preceding chapter, it is convenient to note that the set { 1} is a maximal biprefix set without being a
-
2. MAXIMAL BIPREFIX CODES
'45
code. We start by giving a series of equivalent conditions for a thin code to be maximal biprefix.
PROPOSITION 2.1 Let X be a thin subset of A + . The following conditions are equivalent: (i) (ii) (iii) (iv) (iv') (v)
is a maximal code and biprefix. is a maximal biprefix code. is a maximal prefix code and a maximal sufix code. is a prefix left complete code. is a suffix right complete code. X is a left complete and right complete code. X X X X X
Proof (i) => (ii) is clear. (ii) =s (iii). If X is maximal prefix, then by Theorem 11.3.7, X is a maximal code, therefore X is maximal suffix. Similarly,if X is maximal suffix, it is maximal prefix. Thus, assume that X is neither maximal prefix nor maximal suffix. Let y, z E X be such that X u y is prefix and X u z is suffix. Then X u yz is biprefix. However, yz 4 X (since otherwise X u y would not be prefix). This contradicts (ii). (iii) * (iv') is a consequence of Theorem 11.3.3 stating that a maximal prefix code is right-complete (similarly for the implication (iii) * (iv)). (iv) (v) The code X is complete and thin. Thus, it is maximal. This shows that it is maximal prefix, which in turn implies that it is right complete. (v) * (i) A complete, thin code is maximal. By Theorem 11.3.7 a rightcomplete thin code is prefix. Similarly, X is suffix. 0 A code which is both maximal prefix and maximal suffix is always maximal biprefix, and the converse holds, as we have seen, for thin codes. However, this may become false for codes that are not thin (see Example 2.3).
EXAMPLE 2.1 A group code is a biprefix and a maximal code (Section 1.2). EXAMPLE 2.2 Let A
X
= {a,b }
and
= {a3,a2ba,a2b2,ab,ba2,baba,bab2,b2a,b3}.
By inspection of the literal representation (Fig. 3.3), X is seen to be a maximal prefix code. The reverse code 8 is also maximal prefix (Fig. 3.4). Thus X is a maximal biprefix code. Observe that 8 is equal to the set obtained from X by interchanging a and b (reflectionwith respect to the horizontal axis). This is an exceptional fact, which will be explained later (Example 5.1).
EXAMPLE 2.3 Let A = {a,b } and X = {wabl"l I w E A * } (see Examples 1.4.6 and 11.3.1).It is a maximal, right-dense code which is suffix
111. BIPREFIX CODES
Fig. 3.4 The literal representation of 1.
but not prefix. The set
Y=X-XA+ is maximal prefix and suffix but not maximal suffix since Y 9 X.Thus, Y is also maximal biprefix, satisfying condition (ii) in Proposition 2.1 without satisfying condition (iii). The following result gives a different characterization of maximal biprefix codes within the family of thin codes. PROPOSITION 2.2 A thin code X is maximal biprefix i$ for all w E A*, there exists an integer n 2 1 such that w' E X*.
Proof Assume that for all w E A*, we have w" in X* for some n 2 1. Then X clearly is right-complete and left-complete. Thus, X is maximal biprefix by
Proposition 2.1.
'47
2. MAXIMAL BIPREFIX CODES
Conversely, let X be a maximal biprefix code, and let w E A*. Consider a word u E &X),i.e., which is not a factor of a word in X. The code X being right-complete, for all i 2 1 there exists a word vi such that wiuq E x*.
Since u E F ( X ) , there exists a left factor si of u such that wisi E X * . Let k, m with k c m be two integers such that sk = s,. Then setting n = m - k, we have W k S k E X*,wms, = WnWkSk E X*. Since X* is left-unitary, this implies that w" E X * . 0 We now describe an operation which makes it possible to construct maximal biprefix codes by successive transformations.
PROPOSITION 2.3 Let X be a code which is maximal pre$x and maximal sufiix, and let w E A*. Set
G = XW-',
D = w-'X,
Go = (wD)w-', G1
=G
- Go,
Do = w-'(Gw),
(2-1 )
D, = D - Do.
If G, # 0 and D, # 0, then the set Y = ( X u w u G,(wDX)D,)
- (Gw u wD)
(2.2)
is a maximal pref;x and maximal sufiix code. Further, -Y =
3 + (1 - g W ( 1
- DQ,).
(2.3)
Proof If D, # 0, then D is nonempty. Further 1 # D, since otherwise w E X, and X being biprefix, this implies G = D = { I } , and Do = { l } and finally D, = 0, a contradiction. Thus, w is a proper left factor of a word in X, and by Proposition 11.4.6, the sets D and
Y1 = ( X u W ) - WD
are maximal prefix codes. Next, Gw = X n A*w, also C o w = W D n A*w; similarly for D and Do. Thus, wA* n A*w n X = Gw n wD = wDo = C o w .
Now note that G = Go u G , . From this and (2.4), we get GW u W D = C o w u G,w u wD = wDO v G i w u W D = G,w u wD,
(2.4)
111. BIPREFIX CODES
148
since Do c D. Similarly Gw u W D = Gw u wDl.
Thus
Y = (Y1 u GI WD,*D1)- GI W . Since D = Dl u Do is a maximal prefix code and D, # 0,the set D!D, is a maximal prefix code (Proposition 11.4.9). This and the fact that Y,is maximal prefix imply, according to Proposition 11.4.4, that Y is maximal prefix. Symmetrically, it may be shown successively that Yz = (X u w ) - WGand Y = (Y, - wD,) u G1G,*wDl are maximal suffix codes. From (2.4), we obtain by induction that G,*w = wD,*. Thus, Y’ = Y and consequently Y is also maximal suffix. To prove (2.3), set d =8 (1 G)w(l - Qo*Ql) Then d = w - Gw - W Q , * Q l + GwQ,*D1,
+ +
x+
d
=g
+ w - Gw -
WQfQl+
~iJWQO*Ql+
G,wQ,*D,.
Since Gow = w e o , we obtain o=
x + w - GW -
=g
WQ,*Dl
+ wQoQ,*Di+
G~wQ,*D~
+ w - G w - WQ, + G,wQ,*Q,.
The sets Glw, D o , D1are prefix, and Do # 1 (since otherwise w E X).Thus, the products in the above expression are unambiguous. Next it follows from (2.4) that G,w n wD = 0. Consequently GW u WD= G,w
+ wQ.
Thus o=
X + w + G1wD,*D, - GW u WD= 1. 0
The code Y is said to be obtained from X by internal transformation (with respect to w).
EXAMPLE2.4 Let A = {a,b}, and consider the uniform code X = A’. Let w = a. Then G = D = A and Go = Do = { a } . Consequently, the code Y defined by formula (2.2) is
Y = a u bulb. Note that Y is a group code as is X.
* 49
2. MAXIMAL BIPREFIX CODES
From formula (2.2), it is clear that for a finite code X,the code Y is finite iff Do = 0.This case deserves particular attention. PROFQSITION 2.4 Let X be a jinite maximal biprejix code and let w E A*. Set
G = XW-', D = w-'X. If G # 0,D # fa and Gw n W D = 0,then Y = (X u w u GwD) - ( G w u wD)
(2.5) (2.6)
is a finite maximal biprefix code, and
-Y = & + (c; - l)w(D - 1).
(2.7) Conversely, let Y be a finite maximal biprejix code. Let w E Y be a word such that there exists a maximal prefix code D, and a maximal sufix code G with GwD c Y. Then
X = ( Y - w - GwD) u (Gw u wD)
(2.8)
is a finite maximal biprejix code, and further (2.5),(2.6), and (2.7)hold. Proof If Gw n W D = 0,then we have, with the notations of Proposition 2.3, Go = Do = 0 by formula (2.4). Then (2.2) simplifies into (2.6). Formula (2.7) is a direct consequence of formula (2.3). Conversely, let us first show that X is a maximal prefix code. Set 2 = ( Y - W ) u wD.
Since Y is maximal prefix by Proposition 2.1. and since D is maximal prefix and w E Y, Corollary 11.4.5. implies that the set 2 is a maximal prefix code. Next observe that
X
= (2 - GwD) u Gw.
The set Q = Gw is contained in Z A - , since Gw c (X- w ) A - . Next Q is prefix: assume indeed that gw = g'wt for some g , g' E G,t E A*. Let d be a word in D of maximal length. The set D being maximal prefix, either td E D A - , or td E DA' or finally td E D. The two first cases are ruled out by the property of Y to be prefix. Thus, td E D, and since d has maximal length, we get t = 1 . This proves the claim. Further, for all g E G,we haveD = (gw)- '2. Indeed, the inclusion gwD c 2 implies D c ( g w ) - ' Z , and D being a maximal prefix code, the equality follows. In view of Proposition 11.4.7, the set X consequently is a maximal prefix code. Symmetrically, it may be shown that X is maximal suffix. Since X is finite, it is maximal biprefix.
150
111. BIPREFIX CODES
It remains to show that Y is obtained from X by internal transformation. First, the inclusion Gw c X follows from (2.8), implying G c Xw-l,and G being a maximal suffix code, this enforces the equality
G = XW-'. Symmetrically D = w-lX. Moreover, G # 0, D # 0, because they are maximal codes. Let us show that
Gw n wD = 0. If gw = wd for some g E G,d E D, then ggw
= gwd E GwD c Y.Thus w, ggw E Y; this is impossible, since Y is suffix. From w E Ywe get the result that Gw n Y = 0 ;otherwise Y would not be suffix. Similarly wD n Y = 0,because Y is prefix. Then as a result of (2.8), X - (Gw u wD)= Y - (w u GwD),implying (2.6). 0
EXAMPLE2.5 Let A = {a,b } and X = A3.Consider the word w = ab. Then = A and Gw n WD = 0.Thus Proposition 2.4 yields a finite code Y. This code is obtained by dropping in Fig. 3.5 the dotted lines and by adjoining the heavy lines. The result is the maximal biprefix code of Example 2.2.
G =D
Fig. 3.5 An internal transformation.
3. DEGREE
In this section, we examine the indicator of thin maximal biprefix codes. For these biprefix codes, some simplifications occur. Let X c A + be a biprefix code, set U = A* - XA*,V = A* - A*X and let L = J"*g be the indicator of X. If X is a maximal prefix code, then U = P where P = X A - is the set of proper left factors of words in X.In the same way, for a maximal suffix code, we have V = S where S = A-X is the set of proper
3.
‘5’
DEGREE
right factors of words in X . It follows that if X is maximal prefix and maximal suffix, each parse of a word is an interpretation. Then we have L = S$*p = SA* = A*P. _ _
(3.1) This basic formula will be used frequently. It means that the number of parses of a word is equal to the number of its right factors which are in P , or equivalently the number of its left factors which are in S. Let X be a subset of A + . Denote by H ( X ) = A - X A - = { w E A* I A + w A + n X #
125)
the set of internal factors of words in X . Let R ( X ) = A*
- H(X).
Clearly, each internal factor is a factor of a word in X . The converse may be false. The set H ( X ) and the set F ( X ) = {w EA*IA*wA* n X #
125}
of factors of words in X are related by F(X)= H(X)uX A - u A - X uX and for F ( X ) = A* - F ( X ) , A + H ( X ) A +c F ( X ) c H ( X ) . These relations show that R ( X ) is nonempty iff F ( X ) is nonempty; thus X is thin iff R(X)# 0. THEOREM 3.1 Let X c A + be a biprejix code. Then X is a thin maximal code i$ its indicator L is bounded. In this case, H ( X ) = { W E A* I (L,W ) = d } ,
(3.2)
where d is defined as d = max{(L, w) I w E A * } . Proof Let X be a thin maximal biprefix code. Let w E R ( X ) and w‘ E A*. According to formula (3.1), (L,ww’) = @A*, ww’). Thus the number of parses of ww’ is equal to the number of left factors of ww’ which are in S = A - X . Since w E R ( X ) ,it follows that no such left factor in S is strictly longer than w. Thus all these left factors are left factors of w.Again using formula (3.1), this shows that (L,ww’) = (L,w).
Now by Proposition 1.4, we have (L, ww’) 2 (L, w’). Thus we get (L,w’) 5 (L, w )
152
111. BIPREFIX CODES
showing that L is bounded on A* by its value for a word in A(X). This shows also that L is constant on R(X). Thus
R(X)c { w E A* [ ( L w, ) = d}. To show the converse inclusion, consider an internal factor w E H(x). Then there exist p, s E A + such that w' = pws E X.This implies that
(L,w') 2 (L,w) + 1. Indeed, each parse of w can be extended in a parse of w', and w' has an additional parse, namely (1,w', 1). This shows that for an internal factor w, the number (L, w ) is strictly less than the maximal value d. Thus formula (3.2)is proved. Assume now conversely that X is a biprefix code with bounded indicator L, let d = max{(L,w ) I w E A*} and let u E A* be a word such that (L,v) = d . We use formula (1.3)which can be rewritten as
&A*
= A*
+ ( A - 1)L.
Let w E A + be any nonempty word, and set w = au, with a E A, u E A*. Then
(XA*, wu) = (A* + (4 - 1)L,auu) = 1 + (L,uu) - (L,m u ) . By Proposition 1.4, both (L,uu) and (L,auu)are greater than or equal to (L,u). By the choice of u, we have (L, uu) = (L,auu) = d. Thus (&A*, wu) = 1. Thus we have proved that for all w E A + , wu E X A * . This shows that X is right complete. This shows also that X is thin. Indeed, we have u E R(X)since for all g , d E A + we have go E XA* and therefore gvd $ X . Thus X is a thin maximal prefix code. Symmetrically,it can be shown that X is maximal suffix. This gives the result by Proposition 2.1. 0 Let X be a thin maximal biprefix code, and let L be its indicator. The degree of X , noted d ( X ) or simply d, is the number
d ( X ) = max{(L,w ) I w E A*} According to Theorem 3.1, the degree d is the number of parses of any word which is not an internal factor of X.Before going on, let us illustrate the notion of degree with several examples.
EXAMPLE 3.1 Let cp be a morphism of A* onto a group G,and let G' be a subgroup of G. Let X be the group code for which X* = q-'(G'). We have seen that X is a maximal biprefix code, and that X is thin iff G'has finite index in G (Example 1.5.11). The degree of X is equal to the index of G' in G. Indeed let w E R(X)be a word which is not an internal factor of X,and consider the function $ which
3.
‘53
DEGREE
associates, to each word u E A*, the unique word p E P = X A - such that uw E X * p . Each p obtained in such a way is a proper right factor of w. The set $(A*) is the set of right factors of w in P. Since w E A(X),we have Card $(A*) = d ( X ) . Next, we have for u, u E A*,
$(u) = $(u)o G’cp(u)= G‘cp(~). Indeed, if $(u) = $(u) = p, then uw, uw E X * p , and consequently cp(u), q ( u ) E G’cp(p)cp(w)-’.Conversely, if G’cp(u) = G’cp(u), let r E A* be a word such that uwr E X * . Then cp(uwr)E G’cp(u)cp(wr)c G’, whence uwr E X * . Thus
$04 =
This shows that the index of G’ in G is d ( X ) . By Proposition 0.8.1, d ( X ) is also equal to the degree of the permutation group corresponding to the action of G on the cosets of G’, as defined in Section 0.8. EXAMPLE 3.2 The only maximal biprefix code with degree 1 over A is
X
= A.
3.3 Any maximal biprefix code of degree 2 over an alphabet A EXAMPLE has the form
X
= C u BC*B,
(3.3)
where A is the disjoint union of B and C, with B # 0. Indeed, let C = A n X and E = A - C. Each b E B has two parses, namely (1,1, b) and (b, 1,l).Thus, a word which is an internal factor of a word x E X cannot contain a letter in B, since otherwise x would have at least three parses. Thus, the set H of internal factors of X satisfies H c C*. Next consider a word x in X . Either it is a letter, and then it is in C, or otherwise it has the form x = aub with a, b E A and u E H c C*. X being biprefix, neither a nor b is in C. Thus X c C u EC*E. The maximality of X implies the equality. This shows that any maximal biprefix code of degree 2 is a group code. Indeed, the code given by (3.3) is obtained by considering the morphism from A* onto 2 / 2 2 defined by q ( B ) = {I}, cp(C) = (0). EXAMPLE 3.4 Consider the set
Y = {a”b”ln2 l}. It is a biprefix code which is not