Lindenmayer systems
Lindenmayer systems[1] are formal languages favored by botanists for describing the outward forms of plants and other living organisms as well as modelling the stages of their growth and development. Of course they apply to other structures as well, since the basic concept is to implant growth centers within otherwise static objects and watch the subsequent interplay between patterns already formed and the new growth patterns which they implicitly contain. For example, Bamboo could be said to grow at the joints of vertical stalks, but the root could also send out horizontal runners sprouting stalks at intervals.
A Lindenmayer system, highly abstracted from actual plants, contains the following ingredients:
- an alphabet (with words), consisting of letters, symbols, or icons, some of which are
- constants, which never change, and othere are
- variables, which stand in for other quantities, which are assigned from time to time,
- transformation rules according to which words are repeatedly changed, and finally, an
- initiator which starts the process.
If successive transformations reach a point where no variables remain, the process stops, but growth results when the replacement word contains either itself or other variables; it could go on forever, creating ever more complex structures. Lindenmayer systems are only one of an assortment of transformation schemes, which include regular expressions and Markov algorithms; however they are somewhat more adapted to geometric visualization.
Hat wick
 Hat |
 1½ Hats |
 two Hats |
As an example showing how they may be used to organize large classes of Life patterns, consider the sequence running through Hat, Sesquihat and Twin hats, which could easily run on, including more and more half-hats. Moreover, as the hats proliferate, the assemblage comes to resemble more and more a bordered Zebra stripes agar.
Lindenmayer hat productions
| production | commentary | icon |
|---|---|---|
| initiator | Starting from Hat, no further attention needs to be given to the left vertical bar. However, were a longer bar to be an initiator, it would require induction coils on the left to stabilize it. |  |
| equal | If two successive bars rise to the same height, as in the simple Hat string, the wick may be turned around with a beehive-like connection. |  |
| overshoot | A following bar may rise two cells higher because its predecessor acts like an induction coil. It could possibly rise higher, but arranging the rise would be outside this particular Lindenmayer system. |  |
| undershoot | Similarly the successor of a high bar could lie two cells lower |  |
| up and down | Within the body of the Zebra stripe agar, cells are just strung out parallel to the neighboring stripe accordint to whether the new stripe is rising or falling. |  |
| terminator | When the stripe is so short that it cannot be bridged into a new stripe, it is closed with a hook. |  |
Hat footnotes
- Not all productions have been shown since each production has a mirror image by reflection in a horizontal axis. Furthermore, the table could be rotated, applying to horizontal stripes, and reflected vertically to construct the wick in the other direction.
- The variables in the productions are the red dots in the icon to the left; the relevant replacement is shown to the right. Consequently, these productions are context sensitive meaning that the surroundings of the dot determine whether the replacement is possible.
- The choices available while applying the production are
- raise, introducing a longer zebra stripe,
- stand, as in the hat sequence, which could lead to rectangular bordering of a whole zebra agar, or
- lower, which requires lookahead, and could lead to termination.
- As a preparatory phase, another Lindenmayer system could be invoked to induct an initiator, likewise a terminator, forsaking hats completely while going into the wild with zebras.
Circle of Fire
 A possible two-dimensional recursion |
 A large circle of fire |
 Ring of fire |
The pattern Ring of fire is somewhat similar to the Hat wick, in that it is mainly composed of a series of Zebra stripes, although of rather short length. However, instead of closing successive pairs of stripes to make a sort of elongated beehive or chickenwire, they are left hanging. To keep them from either shrinking and disappearing, or leaving ragged ends with a messy evolution, it was found that a staggered configuration with a slight overhang shadowing slightly shorter stripes produced an oscillator of period 2. Terminating the pattern was not so easy until Dean Hickerson discovered the Ring of fire, which solves the problem by turning a corner and after four quadrants closing into a ring.
Once the principle has been understood, rings of any circumference and various fillings can be constructed. The process lends itself to description as a Lindenmayer system operating in two dimensions to produce an agar which is not just a convoluted wick, since growth takes place at multiple buds rather than a single tip.
Lindenmayer circle productions
| production | commentary | icon |
|---|---|---|
| initiator | A quadrant is begun by a glider, which has the smallest arms possible for turning a corner, although held back by the first root bud. |  |
| root growth | The root grows toward the southwest, leaving buds for horizontal and vertical stalks behind yet reproducing itself. |  |
| vertical | A vertical stalk rises until it matches its righthand neighbor, at which point it leaves a little leaf shadowing it. |  |
| horizontal | Similarly a horizontal stalk reaches out until it just barely overshoots its neighbor. |  |
| root terminator | Unless stopped, the root would keep on growing forever. |  |
Circle footnotes
- Note that all growth sites must be serviced at each Lindenmayer step, although lists of alternatives could be provided. Growth stops when no active sites are left. For the shoots, when the branch matches the length of its neighbor; for the root, when a new bud is not provided.
- The productions shown only generate one quadrant of the circle. Once the quadrant has been generated, four copies have to be welded into a stable circle. The stage at which the root stops growing determines the radius of the circle, thereby defining the family.
- Like Rings of fire, Circles of fire are oscillators of period 2; in this case adjacent 45 degree sectors are swapped, so both phases are implicit in the same construction.
- Note that the Lindenmayer system only generates patterns through a series of steps, but does not execute any Game of Life evolution. Indeed, the quadrant which this system generates requires bordering for stability. The use of mirror images as induction coils or for welding is often effective.
References
- Prusinkiewicz, Przemyslaw; Lindenmayer, Aristid; et. al. (1996), The Algorithmic Beauty of Plants, Springer Verlag