Concurrent term rewriting as a model of computation

Joseph Goguen, Claude Kirchner, José Meseguer

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


A new model of computation, concurrent term rewriting, is proposed as a bridge between a class of easily programmed ultra high level languages and advanced massively concurrent architectures. At the highest level of abstraction, this model views computation as replacing selected subterms by others, at multiple sites concurrently. In this view, concurrent term rewriting provides a standard of correctness, and the choice between using trees or graphs to represent terms is a matter of convenience and efficiency. After introducing the basic concepts and properties of concurrent term rewriting, we discuss some basic implementation issues. A second, more concrete model of computation, called partitioned concurrent term rewriting, takes account of the fact that a (possibly very large) term may be partitioned into fragments that reside on different processors, with each processor concurrently rewriting its own fragment. A number of implementation and optimization issues are also discussed, including overlapping rewrites, rule ordering, compilation, and flow analysis. Concurrent E-strategies are introduced as a flexible control mechanism to optimize performance and facilitate systems programming tasks. All mathematical definitions are gathered in one appendix, while another describes the OBJ language used in examples.

Original languageEnglish (US)
Title of host publicationGraph Reduction - Proceedings of a Workshop
EditorsRobert M. Keller, Joseph H. Fasel
Number of pages41
ISBN (Print)9783540184201
StatePublished - 1987
Externally publishedYes
EventInternational Workshop on Graph Reduction, 1986 - Santa Fe, United States
Duration: Sep 29 1986Oct 1 1986

Publication series

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


OtherInternational Workshop on Graph Reduction, 1986
Country/TerritoryUnited States
CitySanta Fe

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Concurrent term rewriting as a model of computation'. Together they form a unique fingerprint.

Cite this