[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink] [PUBLink])

This section provides a more or less informal introduction in algebraic graph grammars (see [PUBLink] [PUBLink] [PUBLink] for a detailed overview).

Algebraic graph grammars are a generalization of Chomsky grammars. A graph signature GSig consists of the sorts of vertices V, edges E, and a label alphabet L. The operations of GSig provide source and target vertices for every edge, s, t : E V, and associate a label to every vertex and edge, l_v : V L and l_e : E L. The figure below shows an example graph.

A match m of graph g₁ to graph g₂ is a total graph morphism that maps the vertices and edges of g₁ to g₂ such that the graphical structure and the labels are preserved. We use injective matches only.

A production P is a partial morphism between a left-hand side P_l and a right-hand side P_r, which provides information about which elements are preserved, deleted and created in the case of an application of the production. The identity of objects is marked by appended identifiers like :1 (see figure below). A production is applicable to a graph g, if there is a match of P_l to g. The figure below shows an example of a production. A general vertex that can match any vertex is graphically depicted by a flat ellipse with a dotted outline. A general edge that can match any edge is graphically depicted by a dotted line.

A derivation g₂ of g₁ is the so-called push-out graph of an application of an applicable production P. The new graph g₂ is similar to g₁, but the elements of P_r that are not in P_l are added, and elements of P_l that are not in P_r are deleted. We formulate a general requirement for the deletion of vertices as it would be unclear how to proceed with dangling edges:

The application of a production may also require application conditions. A negative application condition (NAC) is a total morphism C: P_l n that is satisfied for a match L: P_l g such that there is no morphism G: n g such that G · C = L. An NAC is represented by a convex dark area (e.g., in the production of the figure above). A positive application condition (PAC) is a total morphism C: P_l p that is satisfied for a match L: P_l g if there is a morphism G: p g such that G · C = L. A PAC is represented by a convex light area (e.g., in left-hand side of the figure of Section [Avoiding Redundancy]). For multiple application conditions, such as in production P_Machinee of the figure of Section [Productions for Constraint Extensions], the conjunction of the conditions must hold.

Graph grammars can be used as a mechanism for describing potential neighbor states in the search space. This neighborhood is composed of all possible direct derivations of the current graph. The whole search space, such as the Cartesian product of all variables' domains in conventional CSPs, can be described by the corresponding graph language, with the empty graph as start graph.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek