TY - GEN
T1 - Compiling concurrent rewriting onto the rewrite rule machine
AU - Aida, Hitoshi
AU - Goguen, Joseph
AU - Meseguer, Jose
N1 - *Supported by Office of Naval Research Contracts N00014-86-C-0450 and N00014-90-C-0210, and NSF Grants CCR-8707155 and CCR-9007010. lDepartment of Electrical Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113 Japan; work done at SRI International IOxford University, Programming Research Group, Oxford OX1 3QD, United Kingdom.
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 - https://www.scopus.com/pages/publications/33749379751
UR - https://www.scopus.com/pages/publications/33749379751#tab=citedBy
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 -