COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Combinatorics on Words - 1st Edition - ISBN: 9780121988203, 9781483264684

Combinatorics on Words

1st Edition

Progress and Perspectives

0.0 star rating Write a review
Editor: Larry J. Cummings
eBook ISBN: 9781483264684
Imprint: Academic Press
Published Date: 28th January 1983
Page Count: 416
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


Combinatorics on Words: Progress and Perspectives covers the proceedings of an international meeting by the same title, held at the University of Waterloo, Canada on August 16-22, 1982. This meeting highlights the diverse aspects of combinatorics on words, including the Thue systems, topological dynamics, combinatorial group theory, combinatorics, number theory, and computer science.

This book is organized into four parts encompassing 19 chapters. The first part describes the Thue systems with the Church-Rosser property. A Thue system will be called “Church-Rosser” if two strings are congruent with respect to that system if and only if they have a common descendant, that is, a string that can be obtained applying only rewriting rules that reduce length. The next part deals with the problems related to the encoding of codes and the overlapping of words in rational languages. This part also explores the features of polynomially bounded DOL systems yield codes. These topics are followed by discussions of some combinatorial properties of metrics over the free monoid and the burnside problem of semigroups of matrices. The last part considers the ambiguity types of formal grammars, finite languages, computational complexity of algebraic structures, and the Bracket-context tree functions.

This book will be of value to mathematicians and advance undergraduate and graduate students.

Table of Contents




Thue 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 Carré

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

Some Problems Related to the Encoding of Prefix 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


No. of pages:
© Academic Press 1983
28th January 1983
Academic Press
eBook ISBN:

About the Editor

Larry J. Cummings

Ratings and Reviews