Abstract
The Berlin approach to graph transformation, which uses double pushout derivations in the category of graphs and total graph morphisms, is modified using single pushout derivations in the category of graphs and partial graph morphisms. It is shown that the single pushout approach generalizes the classical approach in the sense that all double pushout derivations correspond to single pushout transformations but not vice versa.
The chances which lie in the extended expressive power are exhibited in the following. We show that some complex proofs within the framework of double pushout derivations become much simpler in the new context. Moreover, the simple derivation structure allows to consider asynchronous derivations which might provide an adequate model for distributed computations.
Finally, the approach is generalized in order to be applicable to more general algebraic structures. We characterize these so-called graph structures as categories of algebras w.r.t. signatures containing unary operator symbols only. Many representations of graphs and hypergraphs known from the literature turn out to be special graph structures such that the theoretical framework introduced in this paper can be applied to all of those objects.
This work has been partly supported by the ESPRIT Basic Research Working Group No. 3299 “Computing by Graph Transformation (GRA2)”.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
6. References
P. Boehm, H. Fonio, A. Habel: Amalgamation of Graph Transformation: A Synchronization Mechanisms, in: JCSS 34, 307–408 (1987).
P. Degano, U. Montanari: A Model of Distributed Systems Based on Graph Rewriting, in: Journal of the ACM 34 (2), 411–449 (1987).
H. Ehrig, P. Boehm, U. Hummert, M. Löwe: Distributed Parallelism of Graph Transformations, in: Graph-Theoretical Concepts in Computer Science WG'87, Springer, LNCS 314, 1–19 (1988).
H. Ehrig, A. Habel: Graph Grammars with Application Conditions, in: G. Rozenberg, A. Salomaa (eds.): The Book of L, Springer, 87–100 (1985).
H. Ehrig: Introduction to the Algebraic Theory of Graph Grammars (a Survey), in: Graph Grammars and Their Application to Computer Science and Biology, Springer, LNCS 73, 1–69 (1979).
H. Ehrig, A. Habel, H.-J. Kreowski, F. Parisi-Presicce: High-level Replacement Systems, Techn. Report, submitted to the Fourth International Workshop on Graph Grammars and Their Application to Computer Science, Bremen, March 1990.
H. Ehrig, B. Mahr: Fundamentals of Algebraic Specifications 1, Springer, Berlin (1985).
A. Habel: Hyperedge Replacement: Grammars and Languages, Dissertation, University Bremen (1989).
B. Hoffmann, D. Plump: Jungle Evaluation for Efficient Term Rewriting, in: Algebraic and Logic Programming, Akademie Verlag, Berlin (DDR), 191–203 (1988).
R. Kennaway: On “On Graph Rewriting”, in: Theoretical Computer Science 52, 37–58 (1987).
H.-J. Kreowski, A. Wilharm: Is Parallelism already concurrency? Part 2: Non-sequential Processes in Graph Grammars, in: Graph Grammars and Their Application to Computer Science, Springer, LNCS 291, 361–377 (1987).
M. Löwe: Implementing Algebraic Specifications by Graph Transformation Systems, Techn. Report 89/26, Technical University of Berlin (1989), to appear in EIK.
M. Löwe: Algebraic Approach to Graph Transformation Based on Single Pushout Derivations, Techn. Report No. 90/5, Technical University of Berlin (1990).
M. Löwe, R. Wilhelm: Risiken polizeilicher Datenverarbeitung, in: Schöne neue Computerwelt, Verlag für Studium und Ausbildung in der Elefanten Press, Berlin, 216–252 (1988).
P. Padawitz: Graph Grammars and Operational Semantics, in: Theoretical Computer Science 19, 37–58 (1982).
F. Parisi-Presicce: Modular System Design Applying Graph Grammars Techniques, in: ICALP'89, Springer, LNCS 372 (1989).
F. Parisi-Presicce, H. Ehrig, U. Montanari: Graph Rewriting with Unification and Composition, in: Graph Grammars and Their Application to Computer Science, Springer, LNCS 291 (1987).
J.C. Raoult: On Graph Rewriting, in: Theoretical Computer Science 32, 1–24 (1984).
G. Rozenberg: An Introduction to the NLC way of rewriting graphs, in: Graph Grammars and Their Application to Computer Science, Springer, LNCS 291, 55–66 (1987).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Löwe, M., Ehrig, H. (1991). Algebraic approach to graph transformation based on single pushout derivations. In: Möhring, R.H. (eds) Graph-Theoretic Concepts in Computer Science. WG 1990. Lecture Notes in Computer Science, vol 484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-53832-1_52
Download citation
DOI: https://doi.org/10.1007/3-540-53832-1_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53832-5
Online ISBN: 978-3-540-46310-8
eBook Packages: Springer Book Archive