View Related Documents

Abstract

Conditional equations have been studied for their use in the specification of abstract data types and as a computational paradigm that combines logic and function programming in a clean way. In this paper we examine different formulations of conditional equations as rewrite systems, compare their expressive power and give sufficient conditions for rewrite systems to have the ldquoconfluencerdquo property. We then examine a restriction of these systems using a ldquodecreasingrdquo ordering. With this restriction, most of the basic notions (like rewriting and computing normal forms) are decidable, the ldquocritical pairrdquo lemma holds, and some formulations preserve canonicity.
This research was supported in part by the National Science Foundation under Grant DCR 85-13417. The second author is also partly supported by the Grant of the Committee on Aid to Research Activity of Faculty of Engineering and Computer Science (Concordia University), Fonds pour la Formation de Chercheurs et l'Aide a la Recherche (Quebec) and the Natural Science and Engineering Research Council (Canada).

Fulltext Preview

Image of the first page of the fulltext document