Fractals, dimension, and formal languages

W. Merzenich; L. Staiger

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)

  • Volume: 28, Issue: 3-4, page 361-386
  • ISSN: 0988-3754

How to cite


Merzenich, W., and Staiger, L.. "Fractals, dimension, and formal languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.3-4 (1994): 361-386. <>.

author = {Merzenich, W., Staiger, L.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {formal languages; automata theory},
language = {eng},
number = {3-4},
pages = {361-386},
publisher = {EDP-Sciences},
title = {Fractals, dimension, and formal languages},
url = {},
volume = {28},
year = {1994},

AU - Merzenich, W.
AU - Staiger, L.
TI - Fractals, dimension, and formal languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 3-4
SP - 361
EP - 386
LA - eng
KW - formal languages; automata theory
UR -
ER -


  1. [Ba88] C. BANDT, Self-similar sets 4: Topology and measure, in Proc. Conf. Topology and Measure V, Wiss. Beitr. Ernst-Mortiz-Arndt-Univ., Greifswald, 1988, pp. 8-16. Zbl0779.54022MR1029552
  2. [Ba89] C. BANDT, Self-similar sets 3: Constructions with sofic Systems, Mh. Math., 1989, 108, pp. 89-102. Zbl0712.58039MR1026611
  3. [By88] M. R. BARNSLEY, Fractals Everywhere, Academic Press, Orlando, 1988. Zbl0691.58001MR977274
  4. [BM89] J. BERSTEL and M. MORCRETTE, Compact representations of patterns by finite automata, in Proc. Pixim'89, Hermes, Paris, 1989, pp. 387-402. 
  5. [BN80] L. BOASSON and M. NIVAT, Adherences of languages, J. Comput. System Sci., 1980, 20, 3, pp. 285-309. Zbl0471.68052MR584863
  6. [BN89] J. BERSTEL and A. NAIT-ABDALLAH, Tétrarbres engendrés par des automates finis, in Journées AFCET-GROPLAN, no. 61-62, Bigre + Globule, 1989, pp. 167-175. 
  7. [CD90/93] K. CULIK II and S. DUBE, Rational and affine expressions for image description, Discrete Appl. Math., 1993, 41, pp. 85-120. Zbl0784.68058MR1198549
  8. Preliminary version: Affine automata and related techniques for generation of complex images, in: Mathematical Foundations of Computer Science, 1990, Proc. Intern. Conf., Lect Notes Comput. Sci., No. 452, Springer-Verlag, Berlin, 1990, pp. 224-231. Zbl0729.68083
  9. [CD90] K. CULIK II and S. DUBE, Automata-theoretic techniques for image generation and compression, in Proc. of FST-TCS 1990, Lect. Notes Comput. Sci., No.472, Springer-Verlag, Berlin, 1990, pp. 76-90. Zbl0733.68098MR1085038
  10. [CD93] K. CULIK II and S. DUBE, Encoding images as words and languages, Intern. J. Algebra and Computation, 1993, 3, 2, pp. 211-236. Zbl0777.68056MR1233222
  11. [Da64] M. DAVIS, Infinitary games of perfect information, in Advances in Game Theory, Princeton Univ. Press, Princeton N. J., 1964, pp. 89-101. Zbl0133.13104MR170727
  12. [Fa85] K. J. FALCONER, The Geometry of Fractal Sets, Cambridge University Press, Cambridge, 1985. Zbl0587.28004MR867284
  13. [Fe93] H. FERNAU, Variaten iterierter Funktionensysterne und Methoden der Formalen Sprachen, Diss., Univ. Karlsruhe, 1993. 
  14. [Ga58] F. R. GANTMACHER, Matrizenrechnung II, Deutscher Verlag der Wissenschaften, Berlin, 1958. MR97415
  15. [HKT93] A. HABEL, H.-J. KREOWSKI and S. TAUBENBERGER, Collages and patterns generated by hyperedge replacement, Languages of Design, 1993, 1, 2, pp. 125-145. 
  16. [HPS92] F. von HAESELER, H.-O. PEITGEN and G. SKORDEV, On the fractal structure of rescaled evolution sets of cellular automata and attractors of dynamical systems, Report Nr. 278, Inst. dynam. Systeme, Univ. Bremen, 1992. 
  17. [Ku70] W. KUICH, On the entropy of context-free languages, Inform. Control., 1970, 16, 2, pp. 173-200. Zbl0193.32603MR269447
  18. [La69] P. LANKASTER, Theory of Matrices, Academic Press, New York, 1969. Zbl0186.05301MR245579
  19. [LS77] R. LINDNER and L. STAIGER, Algebraische Codierungstheorie - Theorie der sequentiellen Codierungen, Akademie-Verlag, Berlin, 1977. Zbl0363.94016MR469495
  20. [Ma77] B. B. MANDELBROT, Fractals, Form, Chance, and Dimension, Freeman, San Francisco, 1977. Zbl0376.28020MR471493
  21. [MW88] R. D. MAULDIN and S. C. WILLIAMS, Hausdorff dimension in graph directed constructions, Trans. Amer. Math. Soc., 1988, 309, 2, pp. 811-829. Zbl0706.28007MR961615
  22. [PS88] H.-O. PEUGEN and D. SAUPE, The Science of Fractal Images, Springer-Verlag, New York, 1988. MR952853
  23. [PLH88] P. PRUSINKIEWICZ, A. LINDENMAYER and J. HANAN, Developmental models for herbaceous plants for computer imagery purposes, Computer Graphics, 1988, 22, 4, pp. 141-150. 
  24. [Sm84] A. R. SMITH III, Plants, fractals, and formal languages, Computer Graphics, 1984, 18, 3, pp. 1-10. 
  25. [St83] L. STAIGER, Finite-state ω-languages, J. Comput System Sci., 1983, 27, 3, pp. 434-448. Zbl0541.68052MR727390
  26. [St85] L. STAIGER, The entropy of finite-state ω-languages, Problems Control Inform. Theory, 1985, 14, 5, pp. 383-392. Zbl0582.94012MR820702
  27. [St87] L. STAIGER, Research in the Theory of ω-languages, J. Inf. Process. Cybern. EIK, 1987, 23, pp. 415-439. Zbl0637.68095MR923334
  28. [St85/89] L. STAIGER, Combinatorial properties of the Hausdorff dimension, J. Statist. Plann. Inference, 1989, 23, pp. 95-100. Preliminary version in "GEOBILD'85" Proc. of the 2nd Workshop on Geometrical Problems of Image Processing, Wissenschaftliche Beiträge, Friedrich-Schiller-Univ., Jena, 1985, pp. 43-48. Zbl0709.11041MR1029243
  29. [St89] L. STAIGER, Quadtrees and the Hausdorff dimension of pictures, in: "GEOBILD'89" Proc. of the 4th Workshop on Geometrical Problems of Image Processing, Mathematical Research, No. 51,Akademie-Verlag, Berlin, 1989, pp. 173-178. Zbl0679.68169MR1003331
  30. [St89/93] L. STAIGER, Kolmogorov complexity and Hausdorff dimension, Inform. and Comput., 1993, 103, 2, pp. 159-194. Preliminary version in: "Fundamentals of Computation Theory" Proc. Intern. Conf., Lecture Notes in Comput. Sci., No. 380, Springer-Verlag, Berlin, 1989, pp. 334-343. Zbl0789.68076MR1216454
  31. [SW74] L. STAIGER and K. WAGNER, Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen, Elektron. Informationsverarb. Kybernet EIK, 1974, 10, pp. 379-392. Zbl0301.94069MR472265

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.