Abstract
In the present paper we generalize the well-known PARALLELISM THEOREM for graph derivations to the AMALGAMATION THEOREM. In this theorem the assumption of ‘parallel independence’ is dropped. For each pair of productions together with a relational production (allowing productions to be associated with each other) we construct a single ‘amalgamated’ production. The AMALGAMATION THEOREM states that graph derivations which respect the given associations can be amalgamated to a single derivation via the ‘amalgamated’ production.
The amalgamation mechanism can be used to handle synchronization phenomena. The amalgamation concept is applied to synchronization of graph manipulations in a simplified railway control system as well as in GDS, a graph grammar formalism for distributed systems.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M.A. Arbib, E.G. Manes: Arrows, Structures, and Functors, Academic Press, New York
P. Boehm, H. Fonio, A. Habel: On Amalgamation of Graph Manipulations; in preparation
V. Claus, H. Ehrig, G. Rozenberg, (eds.): Graph Grammars and Their Application to Computer Science and Biology, LNCS 73 (1979)
A. Corradini, P. Degano, U. Montanari: Specifying Highly Concurrent Data Structure Manipulation; Comp. Sci. Dept., Univ. of Pisa, Pisa, April 1984
I. Castellani, U. Montanari: Graph Grammars for Distributed Systems, LNCS 153, 20–38 (1983)
P. Degano, U. Montanari: A Model of Distributed Systems Based on Graph Rewriting, Note Cnet 111, Comp. Sci. Dept., Univ. of Pisa, Pisa 1983, submitted for publication
H. Ehrig: Introduction to the Algebraic Theory of Graph Grammars, LNCS 73 (1979), 1–69
— Aspects of Concurrency in Graph Grammars, LNCS 153 (1983), 58–81
H. Ehrig, A. Habel, B.K. Rosen: Concurrent Transformations of Structures: From Graphs to Relational Data Structures; TU Berlin, FB 20, Technical Report No. 83-01, January 1983
H. Ehrig, H.-J. Kreowski: Applications of Graph Grammar Theory to Consistency, Synchronization and Scheduling in Data Base Systems, Inform. Syst., Vol. 5, pp. 225–238, Pergamon Press Ltd., 1980
H. Ehrig, M. Nagl, G. Rozenberg (eds.): Graph Grammars and Their Application to Computer Science, LNCS 153 (1983)
H. Ehrig, M. Pfender, H.J. Schneider: Graph-Grammars: An Algebraic Approach, Proc. of the IEEE Conf. on Automata and Switching Theory, Iowa City 1973, pp. 167–180
H. Ehrig, B.K. Rosen: Parallelism and Concurrency of Graph Manipulations, Theoret. Comp. Sci. 11 (1980), pp. 247–275
— Decomposition of Graph Grammar Productions and Derivations, LNCS 73 (1979), pp. 192–205
H.-R. Fonio: Amalgamation of Graph Transformations with Application to Synchronization in Distributed Systems, to appear as Techn. Report, TU Berlin, FB 20
A. Habel: Concurrency in Graph-Grammatiken, TU Berlin, FB 20, Technical Report No. 80–11, March 1980
C.A.R. Hoare, S.D. Brookes, A.W. Roscoe: A Theory of Communicating Sequential Processes, Techn. Monograph PRG-16, Progr. Research Group, Oxford Univ., 1981
D. Janssens, H.-J. Kreowski, G. Rozenberg, H. Ehrig: Concurrency of Node-label Controlled Graph Transformations, Techn. Report No. 82-38, Univ. of Antwerp, U.I.A. (1982)
H.T. Kung: The Structures of Parallel Algorithms, Advances in Computers, Vol. 19, 65–108, Academic Press Inc. 1980
B. Mahr, A. Wilharm: Graph Grammars as a Tool for Description in Computer Processed Control: A Case Stude, Proc. 8th Conf. on Graphtheoretic Concepts in Comp. Sci. (WG'82), 165–176 (1982)
R. Milner: Calculi for Synchrony and Asynchrony, Theoret. Comp. Sci. 25 (1983), pp. 267–310
M. Nagl: A Tutorial and Bibliographical Survey on Graph Grammars, LNCS 73 (1979), 70–126
C.A. Petri: Concurrency, Proc. Net Theory and Applications, LNCS 84 (1980), 251–260
B.K. Rosen: Deriving Graphs from Graphs by Applying a Production, Acta Informatica, 4 (1975), pp. 337–357
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boehm, P., Fonio, HR., Habel, A. (1985). Amalgamation of graph transformations with applications to synchronization. In: Ehrig, H., Floyd, C., Nivat, M., Thatcher, J. (eds) Mathematical Foundations of Software Development. CAAP 1985. Lecture Notes in Computer Science, vol 185. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15198-2_17
Download citation
DOI: https://doi.org/10.1007/3-540-15198-2_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15198-2
Online ISBN: 978-3-540-39302-3
eBook Packages: Springer Book Archive