TY - GEN
T1 - Compiling concurrent rewriting onto the rewrite rule machine
AU - Aida, Hitoshi
AU - Goguen, Joseph
AU - Meseguer, Jose
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
PY - 1991
Y1 - 1991
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33749379751&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749379751&partnerID=8YFLogxK
U2 - 10.1007/3-540-54317-1_101
DO - 10.1007/3-540-54317-1_101
M3 - Conference contribution
AN - SCOPUS:33749379751
SN - 9783540543176
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 332
BT - Conditional and Typed Rewriting Systems - 2nd International CTRS Workshop, Proceedings
A2 - Kaplan, Stephane
A2 - Okada, Mitsuhiro
PB - Springer
T2 - 2nd International Workshop on Conditional and Typed Rewriting Systems, CTRS 1990
Y2 - 11 June 1990 through 14 June 1990
ER -