A Survey of Properties of Relations Which Have the Confluence Property.
Abstract
The confluence property arises in a number of areas of Computer Science; from its origins in the lambda-calculus to its use in the theory of abstract data types and term rewriting systems. Its abstract properties and its application to a number of problems, such as algebraic specifications of abstract data types and term rewriting systems, are surveyed here. In the first chapter, surveys the historical work that brought the Church-Rosser property into the literature. The second chapter introduces the idea of confluence and its relation to the Church-Rosser property. The rest of this chapter is on theorems related to confluence. The third chapter, discusses the algebraic specification of abstract data types, which provides the background to move into the study of term rewriting systems, which is the second part of the third chapter. The last chapter, discusses an algorithm for showing that a given axiom set (as rewrite rules) is confluent. This procedure is called the Knuth-Bendix completion algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1985
- Accession Number
- ADA159673
Entities
People
- U. Ozkan
Organizations
- Naval Postgraduate School