Accession Number:

ADA159673

Title:

A Survey of Properties of Relations Which Have the Confluence Property.

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1985-06-01

Pagination or Media Count:

62.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE