Compiling concurrent rewriting onto the rewrite rule machine

Hitoshi Aida, Joseph Goguen, Jose Meseguer

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

Abstract

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
PublisherSpringer-Verlag
Pages320-332
Number of pages13
ISBN (Print)9783540543176
DOIs
StatePublished - Jan 1 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

Other

Other2nd International Workshop on Conditional and Typed Rewriting Systems, CTRS 1990
CountryCanada
CityMontreal
Period6/11/906/14/90

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Aida, H., Goguen, J., & Meseguer, J. (1991). Compiling concurrent rewriting onto the rewrite rule machine. In S. Kaplan, & M. Okada (Eds.), Conditional and Typed Rewriting Systems - 2nd International CTRS Workshop, Proceedings (pp. 320-332). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 516 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-54317-1_101