\(L\)-systems and mutually recursive function systems. (English) Zbl 0790.68056

Culik, Karel II; Dube, Simant

Acta Inf. 30, No. 3, 279-302 (1993).

The authors investigate the relationships between two different approaches to generate fractal images – \(L\)-systems and Mutually Recursive Function Systems (MRFS). Two different ways in which \(L\)- systems have been used to generate images are considered. The first is the well-known turtle geometry method, and the other is the vector interpretation method as used by Dedekind. It is shown that a uniformly growing D0L-systems can be simulated by an MRFS, and any D0L-system can be simulated by an MRFS with a control set produced by an iterative GSM.

Reviewer: K.Culik II (Columbia/SC)

MSC:

68Q45	Formal languages and automata
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

fractals; image generation; mutually recursive function systems; fractal images; \(L\)-systems; D0L-system

References:

[1]	Barnsley, M.F.: Fractals everywhere. New York: Academic Press 1988 · Zbl 0691.58001
[2]	Barnsley, M.F., Jacquin, A., Reuter, L., Sloan, A.D.: Harnessing chaos for image synthesis. Computer Graphics, SIGGRAPH 1988 Conference Proceedings
[3]	Barnsley, M.F., Elton, J.H., Hardin, D.P.: Recurrent iterated function systems. Construct. Approx.5, 3-31 (1989) · Zbl 0659.60045
[4]	Barnsley, M.F., Devaney, R.L., Mandelbrot, B.B., Peitgen, H-O., De Saupe, Voss, R.F.: Science of fractal images. Berlin Heidelberg New York: Springer 1988 · Zbl 0683.58003
[5]	Culik K. II, Dube, S.: Affine automata and related techniques for generation of complex images, Theor. Comput. Sci. Preliminary version in Proceedings of MFCS’1990 (Lect. Notes Comput. Sci., vol. 452, pp. 224-231) Berlin Heidelberg New York: Springer 1990 · Zbl 0779.68062
[6]	Culik, K. II, Dube, S.: Rational and affine expressions for image Discrete Appl. Math. (to appear). Preliminary version: Automata-Theoretic Techniques for Image Generation and Compression, Proceedings of FST-TCS’1990 (Lect. Notes Comput. Sci., vol. 472, pp. 76-90). Berlin Heidelberg New York: Springer 1990 · Zbl 0733.68098
[7]	Culik, K. II, Dube, S.: Balancing order and chaos in image generation. Comput. and Graphics (to appear) Preliminary version in Proceedings of ICALP’91 (Lect. Notes Comput. Sci., vol. 510, pp. 600-614) Berlin Heidelberg New York: Springer 1991 · Zbl 0769.68120
[8]	Dekking, F.M.: Recurrent sets. Adv. Math.44, 78-104 (1982) · Zbl 0495.51017
[9]	Dekking, F.M.: Recurrent sets: A fractal formalism. Report 82-32, Delft University of Technology, 1982 · Zbl 0495.51017
[10]	Frijters, D., Lindenmayer, A.: A model for the growth and flowering ofAster novae-angliae on the basis of table (1, 0) L-systems. In: Rozenberg, G., Salomaa, A. (eds.) L-Systems. (Lect. Notes Comput. Sci., vol. 15, pp. 24-52) Berlin Heidelberg New York: Springer 1974 · Zbl 0293.92007
[11]	Giessmann, E.G.: Generation of fractal curves by generalizations of Lindemayer’s L-systems. Proceedings of FRACTAL’90, Plymouth State College, New Hampshire 1990
[12]	Hogeweg, P., Hesper, B.: A model study on biomorphological description. Pattern Recogn.6, 165-179 (1974)
[13]	Lindenmayer, A.: Mathematical models for cellular interaction in development, Parts I & II. J. Theor. Biol.18, 280-315 (1968)
[14]	Mandelbrot, B.: The fractal geometry of nature. San Francisco: W.H. Freeman 1982 · Zbl 0504.28001
[15]	Prusinkiewicz, P.: Applications of L-systems to computer imagery. In: Ehrig, H., Nagl, M., Rosenfeld, A., Rozenberg, G. (eds.) Graph grammars and their application to computer science. (Lect. Notes Comput. Sci., vol. 291, pp. 534-548) Berlin Heidelberg New York: Springer 1987
[16]	Prusinkiewicz, P.: Graphical applications of L-systems. Proceedings of graphics interface’86-Vision Interface’86, pp. 247-253 (1986)
[17]	Prusinkiewicz, P., Lindenmayer, A.: The algorithmic beauty of plants. Berlin Heidelberg New York: Springer 1990 · Zbl 0850.92038
[18]	Shallit, J., Stolfi, J.: Two methods for generating fractals. Comput. and Graphics13, 185-191 (1989)
[19]	Smith, A.R.: Plants, fractals, and formal languages. Computer Graphics18, 1-10 (1984)
[20]	Szilard, A.L., Quinton, R.E.: An interpretation for D0L systems by computer graphics. Sci. Terrapin4, 8-13 (1979)