Theory of Codes (Pure and Applied Mathematics 117)

Theory of Codes......Page 4
Copyright Page......Page 5
Contents......Page 8
Preface......Page 12
1 Notation......Page 16
2 Monoids......Page 17
3 Words......Page 19
4 Automata......Page 25
5 Ideals in a Monoid......Page 33
6 Semirings and Matrices......Page 41
7 Formal Series......Page 44
8 Permutation Groups......Page 47
9 Notes......Page 51
1 Definitions......Page 52
2 Codes and Submonoids......Page 57
3 A Test for Codes......Page 65
4 Measure of a Code......Page 69
5 Complete Sets......Page 76
6 Composition......Page 86
7 Exercises......Page 93
8 Notes......Page 96
0 Introduction......Page 98
1 Prefix Codes......Page 99
2 The Automaton of a Prefix Code......Page 105
3 Maximal Prefix Codes......Page 113
4 Operations on Prefix Codes......Page 118
5 Semaphore Codes......Page 122
6 Synchronous Codes......Page 130
7 Average Length......Page 136
8 Deciphering Delay......Page 143
9 Exercises......Page 149
10 Notes......Page 154
0 Introduction......Page 155
1 Parses......Page 156
2 Maximal Biprefix Codes......Page 159
3 Degree......Page 165
4 Kernel......Page 178
5 Finite Maximal Biprefix Codes......Page 183
6 Exercises......Page 190
7 Notes......Page 193
0 Introduction......Page 195
1 Automata......Page 197
2 Flower Automaton......Page 204
3 Monoids of Unambiguous Relations......Page 217
4 Rank and Minimal Ideal......Page 232
5 Very Thin Codes......Page 239
6 Group and Degree of a Code......Page 249
7 Synchronization of Semaphores......Page 263
8 Exercises......Page 270
9 Notes......Page 275
0 Introduction......Page 276
1 Group Codes......Page 277
2 Automata of Biprefix Codes......Page 279
3 Depth......Page 284
4 Groups of Finite Biprefix Codes......Page 286
5 Examples......Page 294
6 Exercises......Page 300
7 Notes......Page 303
1 Densities......Page 305
2 Probabilities over a Monoid......Page 311
3 Contexts......Page 324
4 Exercises......Page 333
5 Notes......Page 335
0 Introduction......Page 336
1 Circular Codes......Page 337
2 Limited Codes......Page 344
3 Length Distributions......Page 352
4 Factorizations of Free Monoids......Page 366
5 Finite Factorizations......Page 379
6 Exercises......Page 389
7 Notes......Page 392
0 Introduction......Page 394
1 Factorizing Codes......Page 395
2 Determinants......Page 397
3 State Space......Page 400
4 Evaluation of the Polynomials......Page 409
5 Proof of the Theorem......Page 413
6 Commutative Equivalence......Page 419
7 Complete Reducibility......Page 423
8 Exercises......Page 433
9 Notes......Page 437
References......Page 439
Index......Page 444