Compiling concurrent rewriting onto the rewrite rule machine

Hitoshi Aida, Joseph Goguen, Jose Meseguer

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


Following a brief review of the of the Rewrite Rule Machine’s concurrent rewriting model of computation, this paper describes a technique for transforming rule sets which eliminates non-left linear and conditional rules. By Theorem 1, this transformation preserves termination and result; it is used as a first phase of compilation. After a brief review of RRM architecture, the second phase of compilation is described, which transforms unconditional left linear rule sets into ensemble micro code. By Theorem 2, this transformation preserves the time complexity of a set of rewrite rules executed in parallel. The paper concludes with a discussion of the ensemble controller’s role.

Original languageEnglish (US)
Title of host publicationConditional and Typed Rewriting Systems - 2nd International CTRS Workshop, Proceedings
EditorsStephane Kaplan, Mitsuhiro Okada
Number of pages13
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
  • Computer Science(all)


Dive into the research topics of 'Compiling concurrent rewriting onto the rewrite rule machine'. Together they form a unique fingerprint.

Cite this