Publication:
A simple proof of a generalized Church-Rosser theorem

Loading...
Thumbnail Image
Authors
MacLennan, Bruce J.
Subjects
Church-Rosser, theorem, abstract calculus, tree transformation, term rewriting, functional programming, logic programming, equational programming, production systems, tree, nondeterministic algorithm, normal form, lambda calculus.
Advisors
Date of Issue
1984-06
Date
1984-06
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Abstract calculi (tree transformation systems, term rewriting systems) express computational processes by transformation rules operating on abstract structures (trees). They have applications to functional programming, logic programming, equational programming, productions systems and language processors. We present proof of the Church-Rosser Theorem for a wide, useful class of abstract calculi. This theorem implies that terminating reductions always yield a unique reduced form in these calculi, which has the practical result that transformation rules can be safely applied in any order, or even in parallel. Although this result has previously been established for certain classes of abstract calculi, our proof is much simpler than previous proofs because it is an adaption of Rosser's new (1982) proof of the Church-Rosser Theorem for the lambda calculus
Type
Technical Report
Description
Series/Report No
Department
Computer Science
Identifiers
NPS Report Number
NPS52-84-007
Sponsors
Prepared for: Chief of Naval Research
Funder
Format
15 p. ; 28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections