Subapical bracketed L-systems

Przemyslaw Prusinkiewicz¹ and Lila Kari²

¹Department of Computer Science
University of Calgary
Calgary, Alberta, Canada T2N 1N4
e-mail: pwp@cpsc.ucalgary.ca

²Department of Mathematics
University of Western Ontario
London, Ontario, Canada N6A 5B7
e-mail: lkari@julian.uwo.ca

Abstract

This paper characterizes the development of modular branching structures that satisfy three assumptions: (a) subapical branching, meaning that new branches can be created only near the apices of the existing branches, (b) finite number of module types and states, and (c) absence of interactions between coexisting components of the growing structure. These assumptions are captured in the notion of subapical bracketed deterministic L-systems without interactions (sBDOL-systems). We present the biological rationale for sBDOL-systems and prove that it is decidable whether a given BDOL-system is subapical or not. In addition, using the assumption that modules, once created, continue to exist, we show that (propagating) sBDOL-systems are too weak to generate acrotonic and mesotonic branching structures, which are often observed in nature. Their development must therefore be controlled by more involved mechanisms, overriding at least one of the assumptions (a-c) above.

Reference

Przemyslaw Prusinkiewicz and Lila Kari. Subapical bracketed L-systems. In J. Cuny, H. Ehrig, G. Engles, and G. Rozenberg, editors, Grammars and their Application to Computer Science, volume 1073 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1996, pp. 550-564.

Download Postscript (101.8Kb compressed, 350.0Kb uncompressed)
or PDF (~121 kB)
Back to Publications