String-rewriting systems

Abstract

In this chapter we introduce the string-rewriting systems and study their basic properties. Such systems are the primary subject of this work. We provide formal definitions of string-rewriting systems and their induced reduction relations and Thue congruences. Some of the basic ideas that occur in the study of term-rewriting systems are considered. We rely on Section 1.4 for basic definitions and notation for strings, and we rely on Section 1.1 for basic definitions and results on notions such as reduction, confluence, the Church-Rosser property, and so forth.