×

zbMATH — the first resource for mathematics

Parallelism and concurrency in high-level replacement systems. (English) Zbl 0749.68045
Summary: 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.

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.)
PDF BibTeX XML Cite
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.