Parallelism and concurrency in high-level replacement systems.

*(English)*Zbl 0749.68045Summary: High-level replacement systems are formulated in an axiomatic algebraic framework based on categories and pushouts. This approach generalizes the well-known algebraic approach to graph grammars and several other types of replacement systems, especially the replacement of algebraic specifications which was recently introduced for a rule-based approach to modular system design.

Basic notions like productions, derivations, parallel and sequential independence are introduced for high-level replacement systems leading to Church-Rosser, Parallelism and Concurrency Theorems previously shown in the literature for special cases only. In the general case of high-level replacement systems specific conditions, called HLR1- and HLR2- conditions, are formulated in order to obtain these results.

Several examples of high-level replacement systems are discussed and classified w.r.t. HLR1- and HLR2-conditions showing which of the results are valid in each case.

Basic notions like productions, derivations, parallel and sequential independence are introduced for high-level replacement systems leading to Church-Rosser, Parallelism and Concurrency Theorems previously shown in the literature for special cases only. In the general case of high-level replacement systems specific conditions, called HLR1- and HLR2- conditions, are formulated in order to obtain these results.

Several examples of high-level replacement systems are discussed and classified w.r.t. HLR1- and HLR2-conditions showing which of the results are valid in each case.

##### MSC:

68Q42 | Grammars and rewriting systems |

68Q65 | Abstract data types; algebraic specification |

18A30 | Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.) |

##### Keywords:

algebraic specification grammars; graph grammars; replacement systems; Church-Rosser; Parallelism; Concurrency
PDF
BibTeX
XML
Cite

\textit{H. Ehrig} et al., Math. Struct. Comput. Sci. 1, No. 3, 361--404 (1991; Zbl 0749.68045)

Full Text:
DOI

##### References:

[1] | Kreowski, Springer Lecture Notes in Computer Science 56 pp 275– (1977) |

[2] | MacLane, Categories for the Working Mathematician (1972) |

[3] | Ehrig, Fundamenta Informaticae IX pp 13– (1986) |

[4] | DOI: 10.1007/BFb0025714 |

[5] | Corradini, Proc. CAAP’91. Springer Lecture Notes in Computer Science 493 pp 275– (1991) |

[6] | DOI: 10.1007/BFb0025713 |

[7] | Arbib, Arrows, Structures and Functors (1975) |

[8] | Herrlich, Category Theory (1973) |

[9] | DOI: 10.1016/0304-3975(80)90016-X · Zbl 0449.68036 |

[10] | DOI: 10.1007/BFb0014968 |

[11] | DOI: 10.1007/BFb0000094 |

[12] | Ehrig, Springer EATCS Monographs on Theoretical Computer Science 6 (1985) |

[13] | DOI: 10.1007/BF01752403 · Zbl 0491.68035 |

[14] | DOI: 10.1007/BF00288659 · Zbl 0329.68061 |

[15] | Parisi-Presicce, Proc. 3rd Int. Workshop on Graph Grammars. Springer Lecture Notes in Computer Science 291 pp 496– (1987) · Zbl 0643.68124 |

[16] | DOI: 10.1007/BFb0035788 |

[17] | Meseguer, Proc. Logics in Comp. Sci. 88 (1988) |

[18] | DOI: 10.1002/mana.19790910111 · Zbl 0431.68069 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.