A simple proof of a generalized Church-Rosser theorem

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read

My Reading Lists:

Create a new list

Check-In

×Close
Add an optional check-in date. Check-in dates are used to track yearly reading goals.
Today

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read


Download Options

Buy this book

Last edited by CoverBot
May 20, 2020 | History

A simple proof of a generalized Church-Rosser theorem

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read

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.

Publish Date
Language
English
Pages
15

Buy this book

Previews available in: English

Edition Availability
Cover of: A simple proof of a generalized Church-Rosser theorem

Add another edition?

Book Details


Published in

Monterey, California

Edition Notes

Title from cover.

"Prepared for: Chief of Naval Research"--Cover.

"June 1984"--Cover.

"NPS52-84-007"--Cover.

Author(s) key words: Church-Rosser, theorem, abstract calculus, tree transformation, term rewriting, functional programming, logic programming, equational programming, production systems, tree, nondeterministic algorithm, normal form, lambda calculus.

Includes bibliographical references (p. 13-14).

"Approved for public release; distribution unlimited"--Cover.

Technical report; 1984.

aq/aq cc:9116 02/25/98

kmc/kmc 10/28/09.

The Physical Object

Pagination
15 p. ;
Number of pages
15

ID Numbers

Open Library
OL25498532M
Internet Archive
simpleproofofgen00macl
OCLC/WorldCat
460637431

Community Reviews (0)

Feedback?
No community reviews have been submitted for this work.

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
May 20, 2020 Edited by CoverBot Added new cover
July 25, 2014 Created by ImportBot Imported from Internet Archive item record.