Shape grammar
Shape grammars in computation are a specific class of production systems that generate geometric shapes. Typically, shapes are 2- or 3-dimensional, thus shape grammars are a way to study 2- and 3-dimensional languages. Shape grammars were first introduced in a seminal article by George Stiny and James Gips in 1971. The mathematical and algorithmic foundations of shape grammars (in particular, for linear elements in two-dimensions) were developed in "Pictorial and Formal Aspects of Shapes and Shape Grammars" (Birkhäuser Basel, 1975) by George Stiny. Applications of shape grammars were first considered in "Shape Grammars and their Uses" (Birkhäuser Basel, 1975) by James Gips. These publications also contain two independent, though equivalent, constructions showing that shape grammars can simulate Turing machines. Definition A shape grammar consists of shape rules and a generation engine that selects and processes rules. A shape rule defines how an existing (part of a) shape can be transformed. A shape rule consists of two parts separated by an arrow pointing from left to right. The part left of the arrow is termed the Left-Hand Side (LHS). It depicts a condition in terms of a shape and a marker. The part right of the arrow is termed the Right-Hand