Conditional rewriting logic: Deduction, models and concurrency

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Term rewriting has so far been understood almost exclusively as a technique for equational reasoning. This paper proposes a much broader interpretation in which term rewriting can be used both as a semantic foundation and as a programming paradigm in areas such as reactive systems, concurrency theory and object-oriented programming that do not fit naturally within the functional world of equational logic. The interpretation proposed views conditional rewriting as a logic in its own right, with its own proof theory and with a very general model theory of wide applicability. The logic is sound and complete and admits initial models. Equational logic appears as a special refinement of the general framework; this supports a natural unification of the functional and concurrent programming paradigms with a purely declarative style. Throughout the paper, the concurrent nature of term rewriting is emphasized; the role of rewriting as a unified model of concurrency is also discussed.

Original languageEnglish (US)
Title of host publicationConditional and Typed Rewriting Systems - 2nd International CTRS Workshop, Proceedings
EditorsStephane Kaplan, Mitsuhiro Okada
Number of pages28
ISBN (Print)9783540543176
StatePublished - 1991
Externally publishedYes
Event2nd International Workshop on Conditional and Typed Rewriting Systems, CTRS 1990 - Montreal, Canada
Duration: Jun 11 1990Jun 14 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume516 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd International Workshop on Conditional and Typed Rewriting Systems, CTRS 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Conditional rewriting logic: Deduction, models and concurrency'. Together they form a unique fingerprint.

Cite this