Combinatorics on Words (eBook)

Front Cover 1
Combinatorics on Words: Progress and Perspectives 4
Copyright Page 5
Table of Contents 6
CONTRIBUTORS 8
PREFACE 10
ACKNOWLEDGMENTS 11
PART I: THUE SYSTEMS AND THUE SEQUENCES 12
CHAPTER 1. THUE SYSTEMS AND THE CHURCH-ROSSER PROPERTY: REPLACEMENT SYSTEMS, SPECIFICATION OF FORMAL LANGUAGES, AND PRESENTATIONS OF MONOIDS 12
1. INTRODUCTION 12
2. ABSTRACT REDUCTION SYSTEMS 14
3. STRINGS AND THUE SYSTEMS 20
4. THUE SYSTEMS THAT ARE CHURCH-ROSSER 25
5. SPECIFICATION OF FORMAL LANGUAGES 30
6. INFINITE SYSTEMS 34
7. MONOIDS WITH CHURCH-ROSSER PRESENTATIONS 37
8. ONE-RULE THUE SYSTEMS 41
9. OTHER VIEWS 43
ACKNOWLEDGMENT 46
REFERENCES 47
CHAPTER 2. ON RICH WORDS 50
0. INTRODUCTION 50
1. PRELIMINARIES 52
2. FRAISSE-EHRENFEUCHT GAMES 58
3· AUTOMATA 60
4. THE MONADIC SECOND ORDER THEORY OF RICH WORDS 64
5. END MODEL COMPLETENESS 67
REFERENCES 71
CHAPTER 3. TESTS SUR LES MORPHISMES FAIBLEMENT SANS CARRE 74
1. TERMINOLOGIE 75
2. CARACTERISATIONS DES MORPHISMES SANS CARRE 76
3. MORPHISMES PROLONGEABLES 79
4. SUR UN ALPHABET A TROIS LETTRES 81
5. MORPHISMES UNIFORMES ET CONJECTURE DE BERSTEL 88
6. CAS GENERAL 93
7. SYSTEMS PDOL 97
REFERENCES 98
CHAPTER 4. IRREDUCIBLE BINARY SEQUENCES 102
1. HISTORICAL NOTES 103
2. PRELIMINARIES 104
3. ALGORITHMS AND MAIN RESULTS 105
4. APPLICATIONS 109
5. REFERENCES 110
CHAPTER 5. ON THE STRUCTURE AND EXTENDIBILITY OF SQUARE-FREE WORDS 112
ABSTRACT 112
SECTION I INTRODUCTION 112
SECTION II PRELIMINARIES 113
SECTION III TREES 114
SECTION IV BLOCK LENGTH INEQUALITY 117
SECTION V PROOF OF 
120 
SECTION VI PROOF OF THEOREM 3.2. 127
SECTION VII STRUCTURE AND EXTENDIBILITY 
128 
REFERENCES 129
PART II: CODES AND LANGUAGES 130
CHAPTER 6. OVERLAPPING OF WORDS IN RATIONAL LANGUAGES 130
1. INTRODUCTION 130
2. A GRAPH CONSTRUCTION ON A RATIONAL LANGUAGE 131
3· RELATIONS ON THE WORDS OF A RATIONAL LANGUAGE 136
4. THE FREE SUBMONOID GENERATED BY A RATIONAL LANGUAGE 138
5. FINAL REMARKS 140
Acknowledgement 141
REFERENCES 141
CHAPTER 7. CODES CIRCULAIRES 144
1. INTRODUCTION 144
2. CODES CIRCULAIRES 146
3. CODES LIMITES 153
4. DISTRIBUTION PAR LONGUEURS 157
5. FACTORISATION DES MONOIDES LIBRES 169
6. 
174 
CHAPTER 8. POLYNOMIALLY BOUNDED DOL SYSTEMS YIELD CODES 178
ABSTRACT 178
1. INTRODUCTION 179
2. THE TERMINATING CASE 180
3. THE NON-TERMINATING CYCLING CASE 181
4. THE NON-CYCLING POLYNOMIALLY BOUNDED CASE 182
ACKNOWLEDGMENT 184
REFERENCES 184
CHAPTER 9. SOME PROBLEMS RELATED TO THE ENCODING OF PREFIX CODES 186
1. BASIC NOTIONS AND 
187 
2. CODES WHOSE TRANSFORMATION MONOIDS DIVIDE A WREATH PRODUCT 190
3. ENCODING AND DIVISION OF TRANSFORMATION MONOIDS 193
4. ENCODINGS AND DIVISIONS OF WREATH-PRODUCTS 197
REFERENCES 203
CHAPTER 10. CONCATENATION HIERARCHIES DECIDABILITY RESULTS AND PROBLEMS 206
ABSTRACT 206
0. INTRODUCTION 208
1. VARIETIES 210
2. CLASSICAL EXAMPLES OF VARIETIES 217
3. BRZOZOWSKTS HIERARCHY AND STRAUBING'S HIERARCHY 224
4. TREE-LIKE CONCATENATION HIERARCHIES 228
REFERENCES 237
PART III: COMBINATORICS AND ENUMERATION 240
CHAPTER 11. A GENERAL EXPRESSION FOR ABELIAN IDENTITIES 240
1. INTRODUCTION 240
2. TERMINOLOGY 241
3. THE FOATA-FUCHS ENCODING OF MAPPINGS 242
4. THE r STIRLING NUMBERS AND POLYNOMIALS 245
5. ABELIAN IDENTITIES 247
6. AN OPEN QUESTION 253
Acknowledgement 253
Appendix A. Analytic proof of corollary 7 254
REFERENCES 255
CHAPTER 12. ON SOME COMBINATORIAL PROPERTIES OF METRICS OVER THE FREE MONOID 258
ABSTRACT 258
1. PRELIMINARIES 259
2. THE P-DISTANCE 261
3. THE F-DISTANCE 263
REFERENCES 265
CHAPTER 13. AN ENUMERATIVE INTERPRETATION OF THE SCHOLTZ CONSTRUCTION FOR COMMA-FREE CODES 268
ABSTRACT 268
0. INTRODUCTION 269
1. COMMA-FREE CODES 269
2. THE SCHOLTZ CONSTRUCTION 271
3. AN ENUMERATIVE INTERPRETATION 275
4. THE EASTMAN CONSTRUCTION 281
5. A COMPARISON OF THE EASTMAN AND SCHOLTZ CONSTRUCTIONS 285
6. REFERENCES 288
CHAPTER 14. THE BURNSIDE PROBLEM FOR SEMIGROUPS OF MATRICES 290
1. INTRODUCTION 290
2. BROWN'S THEOREM ON LOCALLY FINITE SEMIGROUPS 293
3. SEMIGROUPS OF MATRICES OVER A FIELD 297
4. SlRSOVS THEOREM AND SUBSEMIGROUPS OF PI - RINGS 301
5. OPEN PROBLEMS 304
REFERENCES 305
CHAPTER 15. SUBWORD COUNTING AND NILPOTENT GROUPS 308
ABSTRACT 308
RESUME 308
1. INTRODUCTION 308
2. MORPHISMS FROM FREE MONOIDS TO NILPOTENT GROUPS 309
3. LANGUAGES RECOGNIZED BY NILPOTENT GROUPS 312
4. REPRESENTATION OF NILPOTENT GROUPS BY GROUPS OF MATRICES 313
5. CONCLUSION 315
6. REFERENCES 315
PART IV: AUTOMATA AND GRAMMARS 318
CHAPTER 16. AMBIGUITY TYPES OF FORMAL GRAMMARS 318
1. COMPUTER SCIENCE MOTIVATION AND NOTATION 318
2. THE DEFINITION OF m-AMBIGUITY 321
3. A GRAMMAR HOMOMORPHISM 331
4. AVOIDING 1-AMBIGUITY 335
5. INHERENT AMBIGUITY AND PROBLEMS 338
6. REFERENCES 341
CHAPTER 17. FINITE LANGUAGES AND THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC STRUCTURES 344
ABSTRACT 344
1. INTRODUCTION 344
2. ALGEBRAIC NOTATIONS AND PRELIMINARIES 347
3. FUNDAMENTAL RESULTS 351
4. EXTENSIONS 357
5. TERM-REWRITE RULES 363
Acknowledgement 365
6. BIBLIOGRAPHY 365
CHAPTER 18. BRACKET-CONTEXT TREE FUNCTIONS 368
1. INTRODUCTION 368
2. PRELIMINARY DEFINITIONS 369
3· BRACKET-CONTEXT SELECTORS 373
4. B–c 
379 
5. EXTENSIONS 381
6. CONCLUSIONS 388
BIBLIOGRAPHY 391
APPENDIX 393
CHAPTER 19. UNIVERSAL TRAVERSAL SEQUENCES, GRAPH TRAVERSAL AND GRAPH IDENTIFICATION 398
INTRODUCTION 398
GENERAL TRAVERSAL PROBLEM 399
GRAPH IDENTIFICATION 405
FAMILIES OF GRAPHS AND THEIR RELATION TO AUTOMATA 408
RESULTS FOR LESS POWERFUL AUTOMATA 410
REFERENCES 416