Graphs and Graph Transformations (GraTra)
Internally funded project
Acronym: GraTra
Start date : 01.10.2004
End date : 31.12.2014
Project details
Scientific Abstract
Graphs are often used as an intuitive
aid for the clarification of complex matters. Examples of outside
computer science include, e.g., chemistry where molecules are modeled in
a graphical way. In computer science, data or control flow charts are
often used as well as entity relationship charts or Petri-nets to
visualize software or hardware architectures. Graph grammars and graph
transformations combine ideas from the fields of graph theory, algebra,
logic, and category theory, to formally describe changes in graphs.
Category
theory is an attractive tool for the description of different
structures in a uniform way, e.g., the different models for asynchronous
processes: Petri-Nets are based on standard labeled graphs, state
charts use hierarchical graphs, parallel logic programming can be
interpreted in a graph-theoretical way using so-called jungles, and the
actor systems can be visualized as graphs, whose labeling alphabet is a
set of term graphs.
Lately, we have concentrated our attention on a theoretical aspect.
Our
work on graph transformation is based on notions borrowed from category
theory. The so-called double-pushout approach represents a production
by two morphisms starting at a common interface graph. One pushout glues
the left-hand side of the production into the context, the other does
with the right-hand side. Effectively constructing a derivation step,
however, requires finding a pushout complement on the left-hand side.
Some people consider this disadvantageous. In 1984, Raoult has proposed
to model graph rewriting by a single pushout; Loewe has extensively
studied this approach, but the discussion was mainly restricted to
injective morphisms. Under this assumption, the approaches are
equivalent. Some relevant applications such as term graph rewriting,
however, lead to non-injective morphisms. We have examined these cases
in detail, and we could show that the equivalence also holds for
non-injective cases as long as the handle satisfies some reasonable
conditions.