Relational Growth Grammars

Relational growth grammars (RGG) are based on the concept of graph rewriting. Graphs themselves provide an expressive and versatile representation of data, graph rewriting is the equally expressive and versatile approach to the representation of dynamics. Relational growth grammars allow to benefit from these features when building complex models: In their concrete implementation XL, graphs, graph rewriting rules and graph queries are made available within a modelling language built on top of Java.

The history of relational growth grammars goes back to L-systems and their extensions, sensitive growth grammars. It turned out that the rule-based approach itself, which is the driving force behind L-systems and growth grammars, is well suited for the specification of models of various disciplines. However, when dealing with complex models exhibiting complex data and dynamics, L-system-based formalisms fall short of elegantly representing all aspects of the model. One reason is that one has to cut down a model until it fits into the plain string nature of L-systems. With this in mind, relational growth grammars were defined on top of graphs and their versatile relational structure.

Relational growth grammars exibit the following features (for more detailed information, have a look at the publications):

• The fundamental data structure is a graph, i.e., a set of nodes and edges connecting the nodes. The nodes are objects of the underlying programming language.
• Edges form a simple, static kind of relation. More complex relations may be defined, e.g., geometrical neighbourhood relations, topological relations.
• Common data structures can be represented using this relational view, among them strings, trees and multisets.
• The graph representation of data is completed by the corresponding representation of dynamics, graph rewriting. L-systems are included as a special case, but the power of graph rewriting by far exceeds that of string rewriting.
• To have a simple but powerful access to objects in the graph, relational growths grammars allow graph queries. With their help, it is easy to locate an object with a specific property in the graph, to formulate global interactions, or to calculate aggregate properties of a set of objects.
• Within relational growth grammars, "conventional" (imperative) code blocks of the underlying programming language are allowed. This addresses the requirements of real-world-programming, in which a pure rule-based programming is not in all situations feasible, and in which an easy linking with external libraries is desirable.