String-Rewriting Systems

The book represents an attempt by the authors to gather together the most fundamental results on string-rewriting systems. The goal is to explain these results in such a way that they can be understood and used in studies relating to more general rewriting, automated deduction, and algorithmic problems of algebraic structures. The authors have concentrated on presenting basic material that ought to be a prerequisite for understanding more specialized material. The monograph opens with the preliminaries of string-rewriting systems followed by length as the basis for reduction. Monadic string-rewriting systems is covered as well as length-reducing non-monadic string-writing systems. The book closes with the subjects of algebraic protocols and algebraic properties. When the reader has mastered the material in the core of the book (Chapters 1-4), then that person should be equipped to explore the ever-growing body of literature in the field of string-rewriting systems. Both authors have been active in the field of string-rewriting systems and have lectured on the subject in several universities. Lecture notes have been produced and distributed. This monograph is a result of revising and rewriting those notes. This monograph is written for independent study by researchers in theoretical computer science or in the foundation of artificial intelligence. This book is not intended as a textbook, but it certainly could be used as a textbook in computer science. It could be used for a course entitled "Rewriting Systems," or "String Rewriting," or "Foundations of Artificial Intelligence."