Learn Generative Grammars

This section discusses the theory behind GraphSynth. For help in actually using GraphSynth, please refer to the help section.

Graph grammars can be devised to capture the complexities or heuristics of a particular design problem. These rules contain a left hand side of application conditions, L, and a right hand side of resulting graph transformations, R. In general, L and R share some common elements; nodes and arcs which provide the context for a rule application. This intersection of L and R is referred to as K and it is crucial to indicate the overlap in the representation of grammar rules. K is the context or common graph. It includes the elements that "pass through" through the rule and play a particularly important role in connected nodes and arcs in graph grammars. 

There is a distinct three step process in how generative grammar rules function: recognize, choose, and apply (as illustrated in the figure). While others researchers have indicated this process, an automated design system would benefit from systematically executing these three steps. At any stage in the creation of a system, we would like to know all possible changes that can be made. All possible rules should be checked with the graph to determine whether their application conditions allow the rule to be applied. Some rules may not be applicable; some may; and others may be applicable at more than one location in the graph. The details of a generic recognition process for generative systems are described later. From this recognition process, a list of choices is concatenated. The decision now rests on a designer or some computational agent to choose the best rule and location from the list of choices. Finally, the rule is applied after the choice is made. This application of a rule may introduce new nodes and arcs to the graph, remove nodes and arcs, or simply change qualities within existing nodes and arcs. A discussion of rule application specific to generative systems is shown below.