Annual Reports

Graph Transformation Systems 2002-2012

Graphs are often used as an intuitive aid for the clarification of complex matters. Outside the field of computer science, this is for example true in lingiustics, biology, or chemistry, where the structure of sentences or molecules are modeled in a graphical way. In computer science, data or control flow charts are often used as well as entity relationship diagrams 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. A graph grammar is used to define a set of syntactically correct diagrams, i.e., the diagrams built according to the specific rules of an application area. Graph transformations allow dynamically changing such representations, and therefore, they can describe the development of structures.

The underlying theory is an attractive tool for the description of extremely 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.

2002

In 2002, we have continued the investigation of how to describe different approaches to asynchronous processes in a uniform way. 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. Resuming the lectures on graph transformation systems, we have formulated some theorems, e.g., the generation of all possible traces of a program, or the question of whether steps can be exchanged, as general as possible, such that they can be applied to all the different models.

The lecture on functional programming motivated us to reconsider the implementations of the categorical constructions that has been written in Miranda and Java some years ago, and re-implement them in Haskell.

2003

Preparing the textbook on the categorical approach to graph transformation systems, we concentrated on unifying the effective construction of derivations steps; especially, we have investigated the case of ambiguous pushout complements. In this context, we have found that the definitions previously given by Rosen and Parisi-Presicce are special cases of a general construction: You know all possiblke solutions if you can construct the pushout complement that, in some sense, is minimal.

2004

In the double-pushout approach, the left-hand side of the productions usually is assumed to be injective, since the noninjective case leads to ambiguous derivations. Changing labels by a graph derivation can be treated using a structured alphabet. In this case, however, ambiguity is added even in the case of injective graph productions. Most authors solve the problem by restricting the categorical treatment to the underlying graphs, whereas changing the labels is treated separately. In 2004, we could characterize all the solutions categorically. For this we used a result published by Kreowski and Ehrig in 1976. Our result covers some important applications, e.g., Petri Nets, term graphs, and data bases.

With graph transformations not only general graphs can be generated and analyzed, also string-based languages can be handled. A typical example is the context-sensitive language a^n b^n c^n. It can be modelled with the help of context-free hyperedge replacement grammars. To parse such languages, we developed a parser similar to the Earley-Parser. Compared to the original Earley-parser the concept of inactive elements has been extended. An element does not only turn inactive when it has found all its components, it can become inactive in between to allow the parsing process to continue. A new variant of the predictor ensures that inactive edges will be turned active again if necessary.

2005

In the double-pushout approach, the left-hand side of the productions usually is assumed to be injective, since the noninjective case leads to ambiguous derivations. Using a structured alphabet, i.e., productions that may change labels, however, ambiguity is added even in the case of injective graph productions. A well-known solution to this problem is to restrict the categorical treatment to the underlying graphs, whereas the labels on the derived graph are defined by other means. Contrary to this approach, we could characterize all the solutions categorically. For this we used a result published by Kreowski and Ehrig in 1976. Our result covers some important applications, e.g., Petri Nets, term graphs, and data bases. This result has been published in the "Ehrig Festschrift":
http://www2.informatik.uni-erlangen.de/Personen/schneide/hebook.pdf

If two or more productions are applicable to a given graph, the result may depend on the order of application, or the second production is no longer applicable after the first has been applied. Most authors discuss the criterion to check the independence under the strong assumption that both sides of the productions are injective, although the original proof did allow noninjective right-hand sides. As some authors explicitly mention, the category of structurally labeled graphs does not satisfy the independence criterion. We could prove that a modest restriction to the structure of the alphabet is sufficient to guarantee the validitiy of the independence theorem with respect to some important applications, namely term graphs and data base applications.

With graph transformations not only general graphs can be generated and analyzed, also string-based languages can be handled. A typical example is the context-sensitive language a^n b^n c^n. It can be modelled with the help of context-free hyperedge replacement grammars. To parse these languages, we developed a parser similar to the Earley-Parser. Compared to the original Earley-parser the concept of inactive elements is extended. An element does not only turn inactive when it has found all its components, it can become inactive in between to allow the parsing process to continue. A new variant of the predictor ensures that inactive edges will be turned active again if necessary.

2006

If two or more productions are applicable to a given graph, the result may depend on the order of application, or the second production is no longer applicable after the first has been applied. Most authors discuss the criterion to check the independence under the strong assumption that both sides of the productions are injective, although the original proof did allow noninjective right-hand sides. As some authors explicitly mention, the category of structurally labeled graphs does not satisfy the independence criterion. We could prove that a modest restriction to the structure of the alphabet is sufficient to guarantee the validitiy of the independence theorem with respect to some important applications, namely term graphs and data base applications. The results appear in Bulletin of the European Association for Theoretical Computer Science (Febr. 2007):
http://www2.informatik.uni-erlangen.de/Personen/schneide/parindep.pdf

The categorical approach to graph transformations is highly generic: All the proofs and constructions are vaild for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages like Java and Haskell. Java uses classes of objects, but does not really support multiple inheritance, since default methods are not allowed in interfaces. On the other hand, Haskell supports multiple inheritance, but considers classes of types. From our pilot implementations, interesting questions arise concerning the different meaning of genericity.

With graph transformations not only general graphs can be generated and analyzed, also string-based languages can be handled. Especially, context-free hyperedge replacement grammars can handle languages that are not contextfree in Chomsky's theory. This approach can be successfully applied to the problems of discontinuous constituents and free word order in natural languages. E.g., declarative sentences in English have a fixed word order (subject, verb, objects, prepositional phrases), whereas in Hungarian the use of word endings ensures that sentences can be understood despite the completely free word order. We have developed a notation for hypergraph productions that allows the user to restrict the order of nodes and that can be analyzed by HyperEarley, a parser for string generating hypergraph grammars. The results are published in the Proceedings of the Third International Conference on Graph Transformations (Natal, Brazil, Sept. 2006):
http://www2.informatik.uni-erlangen.de/Forschung/Publikationen/download/riedl.pdf

2007

The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages like Java and Haskell. Java uses classes of objects, but does not really support multiple inheritance, since default methods are not allowed in interfaces. On the other hand, Haskell supports multiple inheritance, but considers classes of types. From our pilot implementations, interesting questions arise concerning the different meaning of genericity. The Haskell version is now available:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-a.pdf

2008

A data base transaction is described by a sequence of atomic transformations, but from outside, it should be considered an indivisible step. From the graph transformation point of view, the question is: If we have a derivation sequence, can we construct a production simulating the effect of the whole derivation sequence by one derivation step? The problem has been already studied in our seminal paper (1973), but at that time, we assumed all the morphisms to be injective graph morphisms. In 1976, H. Ehrig and H.-J. Kreowski extended the solution to labeled graphs, and in 1977, H. Ehrig admitted noninjective embeddings, but his solution is based on set-theoretic arguments and doesnot use the categorical constructions. In 2006, H. Ehrig et al. have presented a purely categorical treatment, but this presentation considers only the special case of adhesive categories and is also restricted to monomorphisms. Now, we could show that these restrictions are too strong. Our solution is purely categorical, too, but does not impose any restrictions to the morphisms. Furthermore, we need only that the category under consideration has pushouts and pullbacks, i.e., we can apply the result to any category of interest, e.g., to the category of structurally labeled graphs that is not adhesive. The proof can be found in the draft of our textbook:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter5.pdf

The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages like Java or Haskell. Java uses classes of objects, but does not really support multiple inheritance, since method definitions are not allowed in interfaces. Therefore, we need factory classes to implement generic categorical constructions, and we have to import them into each implemented category. On the other hand, Haskell supports multiple inheritance, but considers classes of types and requires concrete types to be explicitly made instances of all the classes they belong to. From our pilot implementations, interesting questions arise concerning the differences in implementing genericity. The Haskell version is already available:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-a.pdf
A summary of the Java version will be available in the near future. The main parts, however, can be found in the material accompanying the lecture on graph transformations systems:
http://www2.informatik.uni-erlangen.de/Lehre/WS200809/GraTra/index.xml

2009

In the last years, we have generalized the concept of independent derivation steps in such a way that it can be applied to any category of interest, especially to the category of structurally labeled graphs. We have now completed the discussion of transforming derivation sequences by considering parallel productions, i.e., productions that combine the effects of two or more productions in one step. It is easy to define a parallel production as the coproduct of several productions, but in the case of graphs, this leads to derivation steps with non-injective handles. Contrary to some other known approaches, our discussion is not restricted to injective handles, and the construction is sufficient. On the basis of parallel derivation steps, one can also define canonical derivations. In the theory of Chomsky-languages, this definition takes advantage of the left-to-right order of the symbols, which is not available in the case of graphs. In 1976, Kreowski has proposed an alternative: Independent derivation steps are made parallel and the components are shifted to the first possible position. A canonical derivation is one that does no longer allow any shift. Kreowski's definition can be immediately applied to our general setting that is not restricted to graphs. The details can be found in the draft of our textbook: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter5.pdf

The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages such as Java or Haskell. Java uses classes of objects, but does not really support multiple inheritance. In our first version, we define interfaces Cat, CatWithColimits, etc. which must be implemented by classes such as CatFinSet, CatFinGraph, etc. The basic colimits (coproduct, coequalizer, initial object) are introduced as abstract classes the details of which must be implemented by the special categories. Since these colimits allow to construct all other colimits, it would be a straightforward solution to provide CatWithColimits with a method constructing pushouts, but CatWithColimits is an interface. Therefore, we introduce a class PushoutCreator describing this categorical construction independent of a special category. Each category with colimits must import this factory class. A summary of this implementation is available: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-b.pdf

2010

In 2010, we have again concentrated our attention on theoretical concepts as well as on an implementation aspect:

The focus of our research on graph transformation is the so-called double-pushout approach in which a production is given by two morphisms starting at a common interface graph. The ongoing work on the planned textbook has lead to analyze some alternatives and to study the relationships between them and the double-pushout approach. We have first considered hyperedge replacement and inward productions. Hyperedge replacement is well-suited to formally describe computations as well as graphical representations. In the literature, it is usually not treated in the context of the double-pushout approach since the mainstream of DPO research excludes noninjective mappings. Our previous results have avoided this restriction and, therefore, hyperedge replacement also fits well into the double-pushout approach. As a side effect, we find a class of contextfree graph grammars that includes some languages that are not contextfree when treated as string grammars. The second point is based on a proposal by Banach. He has reversed the directions of the morphisms in the production such that they go inwards and embed the left-hand side and the right-hand side into a larger context. This approach allows establishing some interesting relations to operational (non-categorical) approaches as well as to the adhesive-grammar approach. The details will be soon included into the draft of our textbook: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter6.pdf

The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages such as Java or Haskell. In 2008, we have implemented this approach in the functional language Haskell taking advantage of polymorphism. Java uses classes of objects, but does not really support multiple inheritance. In our 2009 version, we have defined interfaces Cat, CatWithColimits, etc. which must be implemented by classes such as CatFinSet, CatFinGraph. This solution, however, does not allow us to provide CatWithColimits with a method constructing pushouts. Therefore, we defined a separate factory class PushoutCreator describing this categorical construction independent of a special category, but it must be imported by the classes implementing special categories. Now, we have implemented an alternative based on generic Java data types. The trick is to define an abstract class CocoCat of cocomplete categories and to provide this class with the canonical constructions of colimits, e.g., pushouts, making them available in the concrete subclasses. The necessity to decorate all the classes and all the methods with the generic parameters is the main disadvantage of this solution. A summary of this implementation is published in Engels et al. (Eds.): Graph Transformation and Model-Driven Engineering (Lect. Notes Comp. Sc. vol. 5765, 2010), pp. 33-58.

2011

In 2011, we have concentrated our attention on a theoretical aspect, whereas research on implementation aspects came off a loser.

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. Using concepts of category theory, we can derive a lot of properties without referring to special types of graphs and/or labeling mechanisms. The first chapters of the planned textbook present a large variety of graphs and different labeling mechanisms and in each case, we had to prove that the properties we need are satisfied. In the last chapter, we resume Schied's work on applying comma categories to the double-pushout approach. Thus, it is sufficient to prove interesting properties only for some basic categories, since we can lift them to some other category by defining it as a comma-category of two appropriate functors. New results include (1) categories the morphisms of which are allowed to substitute labels in a well-defined way (structurally labeled graphs), and (2) the proof that the so-called PIT-property is lifted to the comma category if the first functor is cocontinuous. (Categories satisfying the PIT-property allow a simple criterion to decide on whether derivation steps are interchangeable.)

The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties on top of these are then defined automatically. Since modern programming languages support generic concepts, it is a promising idea to implement the categorical approach to graph transformation in languages such as Java or Haskell. In the last years, we have implemented three versions. The Haskell version takes advantage of polymorphism. Java, however, does not allow multiple inheritance. The first Java version uses factory classes to implement the categorical constructions such as the pushout. The second is based on generic data types. The next step will be a comparison of these versions elaborating their advantages and disadvantages.

2012

In 2012, 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; this approach has been extensively studied by Loewe, 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 noninjective morphisms. We have examined these cases in detail, and we could show that the equivalence also holds for noninjective cases as long as the handle satisfies some reasonable conditions.

watermark seal