HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

The Rewriting Calculus - Part I

Horatiu Cirstea 1 Claude Kirchner 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The rho-calculus integrates in a uniform and simple setting first-order rewriting, lambda-calculus and non-deterministic computations. Its abstraction mechanism is based on the rewrite rule formation and its main evaluation rule is based on matching modulo a theory T. In this first part, the calculus is motivated and its syntax and evaluation rules for any theory T are presented. In the syntactic case, i.e. when T is the empty theory, we study its basic properties for the untyped case. We first show how it uniformly encodes lambda-calculus as well as first-order rewriting derivations. Then we provide sufficient conditions for ensuring confluence of the calculus.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:46:31 PM
Last modification on : Friday, February 4, 2022 - 3:22:00 AM

Links full text




Horatiu Cirstea, Claude Kirchner. The Rewriting Calculus - Part I. Logic Journal of the IGPL, Oxford University Press (OUP), 2001, 9 (3), pp.339-375. ⟨10.1093/jigpal/9.3.339⟩. ⟨inria-00100531⟩



Record views