Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Graph Operations and Free Graph Algebras
verfasst von : Uwe Wolter, Zinovy Diskin, Harald König
Erschienen in: Graph Transformation, Specifications, and Nets
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We introduce a concept of graph algebra that generalizes the traditional concept of algebra in the sense that (1) we use graphs rather than sets as carriers, and (2) we generalize algebraic operations to diagrammatic operations over graphs, which we call graph operations.
Our main objective is to extend the construction of term algebras, i.e., free algebras, for the new setting. The key mechanism for the construction of free graph algebras are pushout-based graph transformations for non-deleting injective rules. The application of rules, however, has to be controlled in such a way that “no confusion” arises. For this, we introduce graph terms and present a concrete construction of free graph algebras as graph term algebras.
As the main result of the paper, we obtain for any graph signature \(\varGamma \) an adjunction between the category \(\mathsf {Graph}\) of graphs and the category \(\mathsf {GAlg}{(\varGamma )}\) of graph \(\varGamma \)-algebras. In such a way, we establish an “integrating link” between the two areas Hartmut Ehrig contributed most: algebraic specifications with initial/free semantics and pushout-based graph transformations.