Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T05:37:47.007Z Has data issue: false hasContentIssue false
  • English
  • Français

On outward and inward productions in the categorical graph-grammar approach and Δ-grammars

Published online by Cambridge University Press:  19 April 2018

Hans J. Schneider
Hans J. Schneider*
Affiliation:
Lehrstuhl für Programmiersprachen – Universität Erlangen-Nürnberg, Martensstraße 3 D-91058 Erlangen (Germany) Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the relationship between three ways of defining graph derivability. That the traditional double-pushout approach and Banach's inward version are equivalent in the case of injective left-hand sides is proved in a purely categorical setting. In the case of noninjective left-hand sides, equivalence can be shown in special categories if the right-hand side is injective. Both approaches have the same generative power in the category of graphs if the pushout connecting the outward production with the inward one is a pullback as well. Finally, it is shown that Banach's point of view establishes a close relationship between the categorical approach and Kaplan's Δ-grammars, allowing a slight generalization of Δ-grammars and making them an operational description of the categorical approach.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 6 , Issue 6 , December 1996 , pp. 527 - 543
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Banach, R. (1994) The contractum in algebraic graph rewriting. In: Preprints 5th Int. Workshop on Graph Grammars, Williamsburg, VA.Google Scholar
Banach, R. (1995) Locating the contractum in the double pushout approach. Theoretical Computer Science 152 305–320.Google Scholar
Ehrig, H. and Kreowski, H. J. (1976) Categorical approach to graphic systems and graph grammars. In: Sympos. Algebraic System Theory. Springer-Verlag Lecture Notes in Economics and Mathematical Systems 131 323–351.Google Scholar
Ehrig, H., Kreowski, H. J. and Taentzer, G. (1994) Canonical derivations for high-level replacement systems. In: Graph Transformations in Computer Science. Springer-Verlag Lecture Notes in Computer Science 776 153–169.CrossRefGoogle Scholar
Ehrig, H., Pfender, M. and Schneider, H. J. (1973) Graph grammars - An algebraic approach. In: Proc. 14.th Ann. Conf. Switching Automata Theory 167-180.Google Scholar
Herrlich, H. and Strecker, G. E. (1973) Category Theory - An Introduction, Allyn and Bacon.Google Scholar
Kaplan, S. M., Loyall, J. P. and Goering, S. K. (1991) Specifying concurrent languages and systems with Δ-grammars. In: Graph Grammars and Their Application to Computer Science. Springer-Verlag Lecture Notes in Computer Science 532 475–489.CrossRefGoogle Scholar
Parisi-Presicce, F., Ehrig, H. and Montanari, U. (1987) Graph rewriting with unification and composition. In: Graph-Grammars and Their Application to Computer Science. Springer-Verlag Lecture Notes in Computer Science 291 496–514.Google Scholar
Schneider, H. J. (1993) On categorical graph grammars integrating structural transformations and operations on labels. Theoretical Computer Science 109 257–274.CrossRefGoogle Scholar