Cummings L.J. (ed.) Combinatorics on Words. Progress and Perspectives

Издательство Academic Press, 1983, -401 pp.An international meeting devoted to the theme of Combinatorics on Words was held at the University of Waterloo, Canada during the week of August 16-22, 1982. There were 10 invited speakers and 23 contributed papers.
Robert McNaughton has written that "the phenomenon underlying the call to this conference is the emergence of a theory of words as distinguished from theories having to do with sets of words" Combinatorics on Words has arisen in such diverse areas of mathematics as logic (Thue systems), topological dynamics (the work of Morse and Hedlund), combinatorial group theory (the Burnside problem), combinatorics (enumeration), number theory (Vander Waerden's theorem), and computer science (automata and formal languages).
The Norwegian mathematician Axel Thue wrote three papers devoted to the subject of infinite words which were published in the earlier part of this century in a journal which was not widely circulated. His results were subsequently rediscovered many times. The papers of Earl Fife and Robert Shelton describe their recent work, which is very much in the spirit of Thue's original papers. That the logical concerns expressed by Thue in his paper of 1914 have been extended considerably is shown in the major survey by Ronald Book which is the initial article in this volume.
Unlike Thue, Marcel Schiitzenberger has directly influenced the research of many mathematicians during his prolific career. He is the founder of a school of algebraic coding theory that is typified by the papers appearing in the Codes and Languages section of this volume. The study of words and their properties leads naturally to questions of enumeration, as is evident in the papers on Combinatorics and Enumeration. Some of these could have been easily included in the Codes and Languages section as well. The papers on Automata and Grammars are of more direct interest to computer scientists.
The fact that Combinatorics on Words has arisen in such diverse areas is testimony to the vitality of the subject and indicates that it is worthy of independent study.True Systems and Thue Sequences
Thue Systems and the Church - Rosser Property: Replacement Systems. Specification of Formal Languages, and Presentations of Monoids
On Rich Words
Tests Sur Les Morphismes Faiblement Sans Carre
Irreducible Binary Sequences
On the Structure and Extendibility of Square-Free Words
Codes and Languages
Overlapping of Words in Rational Languages
Codes Circulaires
Polynomially Bounded DOL Systems Yield Codes
Concatenation Hierarchies: Decidability Results and Problems
Combinatorics and Enumeration
A General Expression for Abelian Identities
On Some Combinatorial Properties of Metrics over the free Monoid
An Enumerative Interpretation of the Scholtz Construction for Comma-free Codes
The Burnside Problem for Semigroups of Matrices
Subword Counting and Nilpotent Groups
Automata and Grammars
Ambiguity Types of formal Grammars
Finite Languages and the Computational Complexity of Algebraic Structures
Bracket-Context Tree Functions
Universal Traversal Sequences. Graph Traversal and Graph Identification