The category of typed graph grammars and its adjunctions with categories of derivations. (English) Zbl 1412.68099
Cuny, J. (ed.) et al., Graph grammars and their application to computer science. 5th international workshop, Williamsburg, VA, USA, November 13–18, 1994. Selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 1073, 56-74 (1996).
Summary: Motivated by the work which has been done for Petri-nets, the paper presents a categorical approach to graph grammars “in the large”. In the large means, that we define categories of graph grammars, graph transition systems, and graph derivation systems which embody the notion “grammar”, “direct derivation”, and “derivation”, respectively, as they are defined in the classical algebraic theory. For this purpose we introduce a suitable notion of graph grammar morphism on “typed graph grammars” in analogy to Petri-nets. A typed graph grammar is a grammar for typed graphs which is a slight generalization of the standard case. The main result shows that the three categories are related by left-adjoint functors. We discuss the relationship of our results to similar results obtained in the Petri-net field, and applications to entity/relationship models.
For the entire collection see [Zbl 0847.00026].
For the entire collection see [Zbl 0847.00026].
MSC:
| 68Q42 | Grammars and rewriting systems |
| 18A40 | Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) |
Keywords:
transition system; direct derivation; graph transformation; graph grammar; injective morphismReferences:
| [1] | M. A. Bednarcsyk: \(Categories of asynchronous systems\), Ph.D. Thesis, University of Sussex, Report no. 1/88, 1988. |
| [2] | A. Corradini, H. Ehrig, M. Löwe, U. Montanari and F. Rossi: \(Abstract Graph Derivations in the Double-Pushout Approach\), LNCS 776, Springer-Verlag, 1994, 86-103. · Zbl 1494.68104 |
| [3] | A. Corradini, H. Ehrig, M. Löwe, U. Montanari and F. Rossi: \(An Event Structure Semantics for Safe Graph Grammars\), in Proc. IFIP Conf. PROCOMET’94 (Conference Edition), San Miniato, Italy, 1994. |
| [4] | P.P. Chen: \(The Entity-Relationship Model: Toward a Unified View of Data\), ACM Transactions on Database Systems, 1(1):9-36, 1976. |
| [5] | I. Claßen, M. Löwe: \(Scheme Evolution in Object-Oriented Models: A Graph Transformation Approach\), to appear Proc. Workshop on Formal Methods at the ICSE’95, Seattle (U.S.A.), 1995. |
| [6] | I. Claßen, M. Löwe, S. Wasserroth, J. Wortmann: \(Static and Dynamic Semantics of EIR Models Based on Algebraic Methods\), Integration von semiformalen und formalen Methoden für die Spezifikation von Software-Systemen (B. Wolfinger, ed.), Springer-Verlag, Informatik aktuell, 1994, 2-9. |
| [7] | A. Corradini, U. Montanari and F. Rossi: \(Graph Processes\), accepted for publication in Fundamenta Informaticae. |
| [8] | P. Degano, J. Meseguer, U. Montanari: \(Axiomatizing Net Computations and Processes\), in Proc. 4th Annual Symp. on Logic in Comp. Sci., Asilomar, CA, USA, 1989, 175-185. · Zbl 0722.68085 |
| [9] | H. Ehrig: \(Tutorial Introduction to the Algebraic Approach of Graph-Grammars\), LNCS 291, Springer-Verlag, 1987, 3-14. · Zbl 0643.68102 |
| [10] | H. Ehrig, B.K. Rosen: \(Parallelism and Concurrency of Graph Manipulation\), TCS 11(1980), 247-275. · Zbl 0449.68036 |
| [11] | M. Löwe: \(Von Graphgrammatiken zu Petri-Netzen und zurück\), Tagungsband Alternative Konzepte für Sprachen und Rechner 1994 (F. Simon, eds.), Univ. Kiel, FB Informatik, Nr. 9412, 79-82. |
| [12] | J. Meseguer, and U. Montanari: \(Petri-Nets are Monoids\), in Info. and Co., 88(1990) 105-155. · Zbl 0711.68077 |
| [13] | M. Nielsen, G. Plotkin and G. Winskel: \(Petri-Nets, Event Structures and Domains\), Part 1, in Theoret. Comp. Sci. 13 (1981), 85-108. · Zbl 0452.68067 |
| [14] | W. Reisig: \(Petri Nets: An Introduction\), EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985. · Zbl 0555.68033 |
| [15] | V. Sassone, M. Nielsen and G. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
