A simple proof of a generalized Church-Rosser theorem
simpleproofofgen00macl.pdf (1.080Mb)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
NPS Report Number
NPS52-84-007Related items
Showing items related by title, author, creator and subject.
-
Symmetry of physical laws Part I. Symmetry in space-time and balance theorems
(American Physical Society, 1955-01);In default of the theorem of "detailed balance": Pi;=P;i, with regard to elementary transition probabilities, several "balance" theorems are introduced and proved on the basis of symmetry of physical laws in space-time. ... -
The Helmholtz theorem
(Monterey, California. Naval Postgraduate School, 2004-07-31); NPS-AM-04-007The Helmoltz theorem is rederived with rigorous vector analysis. The theorem is valid everywhere within any arbitrary mathematical boundary. Applications of the theorem to hydrodynamics are discussed. Keywords: Numerical ... -
Group Priority Scheduling
(1997-04);For many applications, the end-to-end delay of an application-specific data unit is a more important performance measure than the end-to-end delays of individual packets within a network. From this observation, we propose ...
