11: Grammar-Based Models and Fractals



MCED Chapter 11

Title

Grammar-Based Models and Fractals

Authors

Winfried Kurth and Dirk Lanwert

Abstract (from the book)

In ecological interactions the three-dimensional structure of organisms can play an important role. We will present an approach for modelling and simulation of the development of geometrical structures in space, which is particularly suitable for representing branching systems as they occur in plants. The related notions of self-similarity and fractality will be briefly discussed. The crucial idea for modelling is to describe the development of a modular structure by rules controlling the replacement of substructures by other substructures. Such replacement systems are also called “grammars”. When the structures are encoded as strings, we speak of L-systems. A more general case are graph grammars, where the transformed structures are networks consisting of nodes and arcs. Loosely following Kurth (2007), we will first show example grammars written down in the programming language XL, which simulate the branching structures of simple plants. The final example, also implemented in XL, is about competition and resulting spatial interaction between plants. All code examples can be tested with the free software GroIMP (“Growth-grammar related Interactive Modelling Platform”).

Additional material

Further Reading

  • Abelson H, diSessa A A (1982) Turtle Geometry. MIT Press, Cambridge
  • Andrieu B (guest ed.) (1999) Architectural modelling of plants. Special issue of: Agronomie 19 (3-4):161-328
  • Barnsley M F (1988) Fractals Everywhere. Associated Press, Boston
  • Bouchon J, de Reffye Ph, Barthélémy D (eds.) (1997) Modélisation et simulation de l’architecture des végétaux. Science Update, INRA, Paris (435 pp.)
  • Buck-Sorlin G, Kniemeyer O, Kurth W (2007) A grammar-based model of barley including virtual breeding, genetic control and a hormonal metabolic network. In: Vos et al. (2007), 243-252.
  • Cournède P-H (2009) Système dynamique de croissance des plantes. HDR thesis, Université Montpellier II
  • Edgar G A (1990) Measure, Topology, and Fractal Geometry. Springer, New York
  • Fourcaud Th, Zhang X, Stokes A, Lambers H, Körner Ch. (guest eds.) (2008) Plant growth modelling. Special issue of: Annals of Botany 101 (8):1053-1293
  • Frijters D, Lindenmayer A (1974) A model for the growth and flowering of Aster novae-angliae on the basis of table <1,0> L-systems. In: Rozenberg G, Salomaa A (eds) L-systems. Springer, Berlin, 24-52
  • Godin Ch, Sinoquet H (guest eds.) (2005) Functional-structural plant modelling. Featured in: New Phytologist 166 (3):705-708 and 771-894
  • Goel NS, Rozehnal I (1991) Some non-biological applications of L-systems. International Journal of General Systems 18 (4):321-405+color plates
  • Guo Y, Ma Y, Zhan Z, Li B, Dingkuhn M, Luquet D, de Reffye P (2006) Para­meter optimization and field validation of the functional-structural model GreenLab for maize. Ann. Bot. 97:217-230
  • Hanan J, Prusinkiewicz P (guest eds.) (2008) Functional-structural plant modelling. Special issue of: Funct. Plant Biol. 35 (9/10):i-iii and 739-1090
  • Harvey B (1997) Computer Science Logo Style, 2nd edn. 3 volumes. MIT Press, Cambridge, MA. Also available under http://www.cs.berkeley.edu/~bh/ (accessed Feb. 14, 2011)
  • Hemmerling R, Smoleňová K, Kurth W (2010) A programming language tailored to the specification and solution of differential equations describing pro­cesses on networks. In: Dediu AH, Fernau H, Martín-Vide C (eds.): Language and Automata Theory and Appli­cations. Proceedings of LATA 2010, Trier, Germany, May 24-28, 2010. Lecture Notes in Computer Science 6031, Springer, Berlin etc., pp. 297-308
  • Herman GT, Schiff GL (1975) Simulation of multi-gradient models of organisms in the context of L-systems. J. Theor. Biol. 54:35-46
  • Hogeweg P, Hesper B (1974) A model study on biomorphological description. Pattern Recognition 6:165-179
  • Hu B-G, Jaeger M (eds.) (2003) Plant growth modeling and applications. Proceedings – PMA03. Tsinghua University Press, Beijing / Springer, Berlin (435 pp.)
  • Karwowski R, Prusinkiewicz P (2003) Design and implementation of the L+C modeling language. Electronic Notes in Theoretical Computer Science 86 (2) 19 pp. http://algorithmicbotany.org/papers/l+c.tcs2003.pdf (accessed Feb. 14, 2011)
  • Kastner-Maresch A, Kurth W, Sonntag M, Breckling B. (eds.) (1998) Individual-based structural and functional models in ecology. Bayreuther Forum Ökologie 52 (243 pp.)
  • Kniemeyer O, Buck-Sorlin G, Kurth W. (2004) A graph-grammar approach to Artificial Life. Artificial Life 10 (4):413-431
  • Kniemeyer O (2008) Design and implementation of a graph-grammar based language for functional-structural plant modelling. Doctoral dissertation, BTU Cottbus, 432 pp. http://nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de: kobv:co1-opus-5937
  • Kurth W (2007) Specification of morphological models with L-systems and relational growth grammars. Image – Journal of Interdisciplinary Image Science 5 / Themenheft. http://www.uni-forst.gwdg.de/~wkurth/cb/html/ima_lsy.pdf (accessed Feb. 14, 2011)
  • Kurth W, Sloboda B (2001) Sensitive growth grammars specifying models of forest structure, competition and plant-herbivore interaction. Proc. IUFRO 4.11 Congress, Greenwich, UK, June 25-29, 2001. http://www.uni-forst.gwdg.de/~wkurth/cb/html/gree_tx.pdf (accessed Feb. 14, 2011)

  • Lanwert D (2007) Funktions- / Strukturorientierte Pflanzenmodellierung in E-Learning-Szenarien. Doctoral dissertation, Universität Göttingen, 209 pp. http://webdoc.sub.gwdg.de/diss/2008/lanwert/ (accessed Feb. 14, 2011)

  • LeRoux X, Sinoquet H (guest eds.) (2000) 2nd international workshop on functional-structural tree models. Special issue of: Annals of Forest Science 57 (5/6):393-621

  • Li B, Jaeger M, Guo Y (eds.) (2010) Plant Growth Modeling, Simulation, Visualization and Applications. Proceedings – PMA09, Beijing (China) 9-13 Nov. 2009. IEEE, Los Alamitos (454 pp.)

  • Lindenmayer A (1968) Mathematical models for cellular interactions in development. J. Theor. Biol. 18:280-315

  • Mandelbrot B (1977) The Fractal Geometry of Nature. W. H. Freeman, N.Y.

  • Monsi M, Saeki T (1953) Über den Lichtfaktor in den Pflanzengesellschaften und seine Bedeutung für die Stoffproduktion. Japanese Journal of Botany 14: 205-234

  • NVIDIA Corp. (2006) DirectX 10: The next-generation graphics API. Technical brief. http://forum.greycomputer.de/download/handbuecher/nvidia/nvidia_ microsoft_directx-10_technical_brief.pdf (accessed Feb. 6, 2010)

  • Peitgen H-O, Richter PH (1986) The Beauty of Fractals. Springer, Berlin

  • Pfreundt J (1988) Modellierung der räumlichen Verteilung von Strahlung, Photo­synthesekapazität und Pro­duk­tion in einem Fichtenbestand und ihre Beziehung zur Bestandesstruktur. Doctoral dissertation, Uni­ver­sität Göttingen

  • Pfreundt J, Sloboda B (1996) The relation of local stand structure to photosynthetic capacity in a spruce stand: a model calculation. Lesnictví / Forestry 42:149-160

  • Prusinkiewicz P (1987) Applications of L-systems to computer imagery. Lecture Notes in Computer Science 291:534-548

  • Prusinkiewicz P, Lindenmayer A (1990) The algorithmic beauty of plants. Sprin­ger, New York. http://algorithmicbotany.org/papers/abop/abop.pdf (accessed Feb. 14, 2011)
  • Room PM, Hanan JS (1995) Virtual cotton: A new tool for research, management and training. In: Constable GA, Forrester NW (eds) Challenging the Future. CSRIO Australia, 40-44
  • Rozenberg G (1973) T0L systems and languages. Information and Control 23:357-381
  • Rozenberg G (1997) Handbook of Graph Grammars and Computing by Graph Transformations. Vol. 1: Foundations. World Scientific, Singapore
  • Sievänen R, Mäkelä A, Nikinmaa E (guest eds.) (1997) Functional-structural tree models. Special issue of: Silva Fennica 31 (3):237-380

  • Sloboda B, Pfreundt J (1989) Baum- und Bestandeswachstumsprozess. Ein system­analytischer Ansatz mit Versuchsplanungskonsequenzen für die Durchforstung und Einzelbaumentwicklung. Bericht der Jahres­tagung der Sektion Ertragskunde im Deutschen Verband Forstlicher Forschungsanstalten, Attendorn 1989, pp. 17/1-17/25

  • Smith AR (1984) Plants, fractals, and formal languages. Computer Graphics (ACM/SIGGRAPH) 18 (3):1-10

  • Tunbridge A, Jones H (1995) An L-systems approach to the modelling of fungal growth. The Journal of Visualization and Computer Animation 6 (2):91-107

  • Vos J, Marcelis LFM, de Visser PHB, Struik PC, Evers JB (eds.) (2007) Functional-structural plant modelling in crop production. Springer, Dordrecht (269 pp.)

Links

Several software systems exist which can be used to explore the possibilities of fractals and L-systems and to create virtual plants. One of the oldest tools is

It does not only include a simple L-system interpreter, but also other algorithms for generating fractal structures.

developed by Christoph Streit, was one of the first tools specializing on L-systems and was later used in an agronomical application. A more advanced tool,

was developed by Laurens Lapré.

from P. Prusinkiewicz’s team is one of the most widely used L-system software tools, with numerous applications in functional-structural plant modelling.

contains not only an L-system interpreter, but also several tools for analysing branching systems of trees. Meanwhile, most of its functions are also available in the open-source system

developed by Ole Kniemeyer et al. (2004), which offers an advanced, interactive graphics display and an XL compiler.

by Christophe Pradal, is an open-source system designed to compose submodels and tools from different sources in order to create complex models of plants and ecosystems.

General Webpages on L-systems, fractals and functional-structural plant models
L-systems

Fractals

Functional-structural plant models

Project web pages linked to functional-structural plant modelling