EXCALIBURAdaptive Constraint-Based Agents in Artificial Environments

 [SCSP] [Grammars]   [Elements]   [Structural Constraints]   [SCSPs]   [Generation]   [Redundancy]   [Combination]   [Conclusion]

 [ 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. ]

Algebraic Graph Grammars

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, lv : V L and le : E L. The figure below shows an example graph.

A match m of graph g1 to graph g2 is a total graph morphism that maps the vertices and edges of g1 to g2 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 Pl and a right-hand side Pr, 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 Pl 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 g2 of g1 is the so-called push-out graph of an application of an applicable production P. The new graph g2 is similar to g1, but the elements of Pr that are not in Pl are added, and elements of Pl that are not in Pr are deleted. We formulate a general requirement for the deletion of vertices as it would be unclear how to proceed with dangling edges:

Requirement reqd: A production can specify the deletion of a vertex only if the vertex has no edge to another vertex.

The figure below shows how the graph of the first figure above can be transformed using the production of the second figure.

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.

 [SCSP] [Grammars]   [Elements]   [Structural Constraints]   [SCSPs]   [Generation]   [Redundancy]   [Combination]   [Conclusion]