I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching in the bracketed string representation of edge-labeled rooted trees called axial trees.

The predecessor of a 2-L system is defined by the text as follows:

A predecessor of a context-sensitive production $p$ consists of three components: a path $l$ forming the left context, an edge $S$ called the strict predecessor, and an axial tree $r$ constituting the right context.

Such a predecessor is written in the form $l < S > r$. A predecessor is said to match a given occurrence of the edge $S$ in an axial tree $T$ if:

$l$ is a path in $T$ terminating at the starting node of $S$, and $r$ is a subtree of $T$ originating at the ending node of $S$.

This definition is followed by an example wherein the predecessor $BC < S > G[H]M$ is matched in the tree

$$ T_0 = ABC[DE][SG[HI[JK]L]MNO] $$

By this example, we can see that the axial tree given as a right context can be smaller than the subtree it matches in a tree, because the $[H]$ portion of the right context matches the subtree $[HI[JK]L]$ in $T_0$.

The definition of $r$ as a subtree of $T$ rooted at the ending node of $S$ led me to believe that the predecessor $A < B > C$ would match in the tree:

$$ T_1 = AB[C]D $$

However, the text continues to give examples of 2-L systems from Hogeweg and Hesper's A Model Study On Biomorphological Description, which gives a different definition of the right context. In their paper, when matching a symbol representing the strict predecessor $S$, the following is used to match the right context:

When the right-sided symbol is an opening bracket, the rightsided context is defined by the first alphabetic symbol towards the right, which is separated from the symbol by an equal number of opening and closing brackets( including the neighboring open bracket).

This means that the predecessor $A < B > C$ does not match in $T_1$, whereas the context $A < B > D$ does.

As far as I can tell, the definition given by Hogeweg and Hesper is the one used in rendering these examples in ABOP, as well as in pfg, the Plant and Fractal Generator program for legacy Macs referenced in the back-matter of the book.

How do I reconcile these two definitions?

In particular, what should happen if I try matching the predecessor $A < B > [C]$ against the tree $T_1$? What about the tree $AB[X][C]D$?

Unfortunately, ABOP only gives the one example above involving brackets in the right context, and pfg does not support brackets in contexts at all.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.