Valuations and unambiguity of languages, with applications to fractal geometry. (English) Zbl 1418.68117

Fernau, Henning; Staiger, Ludwig

Abiteboul, Serge (ed.) et al., Automata, languages and programming. 21st international colloquium, ICALP ’94, Jerusalem, Israel, July 11–14, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 820, 11-22 (1994).

Summary: Valuations – morphisms from \((\Sigma^\ast, \cdot, \lambda)\) to \(((0, \infty), \cdot, 1)\) – are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [S. Eilenberg, Automata, languages, and machines. Vol. A. New York, NY, London: Academic Press (1974; Zbl 0317.94045); G. Hansel and D. Perrin, Math. Syst. Theory 16, 133–157 (1983; Zbl 0519.94012); F. Blanchard and G. Hansel, Lect. Notes Comput. Sci. 192, 138–146 (1985; Zbl 0571.68059); J. Berstel and D. Perrin, Theory of codes. Orlando, FL etc.: Academic Press (1985; Zbl 0587.68066); J. Berstel and C. Reutenauer, Rational series and their languages. Berlin etc.: Springer-Verlag (1988; Zbl 0668.68005); G. Hansel and D. Perrin, Theor. Comput. Sci. 65, No. 2, 171–188 (1989; Zbl 0669.60005)]. This paper shows that valuations are not only useful within the theory of codes, but also when dealing with ambiguity, especially in regular expressions and context-free grammars, or for defining outer measures on the space of \(\omega\)-words which are of some importance for the theory of fractals. These connections yield new formulae to determine the Hausdorff dimension of fractal sets (especially in Euclidean spaces) defined via regular expressions and context-free grammars.
For the entire collection see [Zbl 0844.00024].

MSC:

68Q45	Formal languages and automata
28A80	Fractals
68Q70	Algebraic theory of languages and automata

Keywords:

formal language; Hausdorff dimension; regular expression; formal power series; fractal geometry

Citations:

Zbl 0317.94045; Zbl 0519.94012; Zbl 0571.68059; Zbl 0587.68066; Zbl 0668.68005; Zbl 0669.60005

References:

[1]	L. M. Andersson. Recursive Construction of Fractals. PhD thesis, Helsinki: Suomalainen Tiedeakatemia, Aug. 1992. Annales Academiae Scientiarum Fennicae Series A, I. Mathematica, Dissertationes, 86. · Zbl 0753.28005
[2]	M. F. Barnsley. Fractals Everywhere, Boston: Academic Press, 1988. · Zbl 0691.58001
[3]	M. F. Barnsley, J. H. Elton, and D. P. Hardin. Recurrent iterated function systems. Constructive Approximation, 5:3-31, 1989. · Zbl 0659.60045
[4]	J. Berstel and D. Perrin. Theory of Codes. Pure and Applied Mathematics. Orlando: Academic Press, 1985. · Zbl 0587.68066
[5]	J. Berstel and C. Reutenauer. Rational Series and Their Languages, volume 12 of EATCS Monographs on Theoretical Computer Science. Berlin: Springer, 1988. · Zbl 0668.68005
[6]	F. Blanchard and G. Hansel. Languages and subshifts. In M. Nivat and D. Perrin, editors, Automata on infinite words, volume 192 of LNCS, pages 138-146. Berlin: Springer, May 1984. · Zbl 0571.68059
[7]	A. Brüggemann-Klein. Regular expressions into finite automata. In LATIN’92, volume 483 of LNCS, pages 87-98, 1992.
[8]	K. Čulik, II and S. Dube. Methods for generating deterministic fractals and image processing. In LNCS: 464; IMYCS, pages 2-28. Springer, 1990. · Zbl 0735.68093
[9]	F. M. Dekking. Recurrent sets: A fractal formalism. Technical Report 82-32, Technische Hogeschool, Delft (NL), 1982.
[10]	S. Dube. Undecidable problems in fractal geometry. Manuscript, May 1993. · Zbl 0816.58024
[11]	G. A. Edgar. Measure, Topology, and Fractal Geometry. Undergraduate Texts in Mathematics. New York: Springer, 1990.
[12]	S. Eilenberg. Automata, Languages, and Machines, Volume A. Pure and Applied Mathematics. New York: Academic Press, 1974. · Zbl 0317.94045
[13]	K. J. Falconer. Fractal Geometry. Chichester: John Wiley & Sons, 1990. · Zbl 0689.28003
[14]	H. Fernau. MRFS-Fraktale aus dem Blickwinkel der regulären ω-Sprachen. In W. Thomas, editor, 2. Theorietag ‘Automaten und Formale Sprachen’, volume 9220 of Technische Berichte, pages 46-50. Universität Kiel, 1992.
[15]	H. Fernau. IIFS and codes (extended version). Technical Report 23/93, Universität Karlsruhe, Fakultät für Informatik, 1993.
[16]	H. Fernau. Infinite iterated function systems. Accepted for publication in Mathematische Nachrichten, 1994.
[17]	H. Fernau. Valuations of languages, with applications to fractal geometry. Accepted for publication in TCS, 1994.
[18]	H. Fernau. Valuations, regular expressions, and fractal geometry. Submitted for publication, Dec. 1993. · Zbl 0851.68064
[19]	H. Fernau. Varianten Iterierter Funktionensysteme und Methoden der Formalen Sprachen. PhD thesis, Universität Karlsruhe (TH) (Germany), 1993.
[20]	G. Hansel and D. Perrin. Codes and Bernoulli partitions. Mathematical Systems Theory, 16:133-157, 1983. · Zbl 0519.94012
[21]	G. Hansel and D. Perrin. Rational probability measures. Theoretical Computer Science, 65:171-188, 1989. · Zbl 0669.60005
[22]	J. Hutchinson. Fractals and self-similarity. Indiana University Mathematics Journal, 30:713-747, 1981. · Zbl 0598.28011
[23]	W. Kuich and A. Salomaa. Semirings, Automata, Languages, volume 5 of EATCS Monographs on Theoretical Computer Science. Berlin: Springer, 1986. · Zbl 0582.68002
[24]	B. Mandelbrot. The Fractal Geometry of Nature. New York: Freeman, 1977.
[25]	R. D. Mauldin and S. C. Williams. Hausdorff dimension in graph directed constructions. Transactions of the American Mathematical Society, 309(2):811-829, Oct. 1988. · Zbl 0706.28007
[26]	M. Nolle. Comparison of different methods for generating fractals. To appear in the Proceedings of the IMYCS’92, 1992.
[27]	H.-O. Peitgen, H. Jürgens, and D. Saupe. Fractals for the Classroom. Part One. Introduction to Fractals and Chaos. New York: Springer, 1992. · Zbl 0746.58005
[28]	C. A. Rogers. Hausdorff Measures. Cambridge at the University Press, 1970. · Zbl 0204.37601
[29]	A. K. Salomaa and M. Soittola. Automata-Theoretic Aspects of Formal Power Series. New York: Springer, 1978. · Zbl 0377.68039
[30]	L. Staiger. On infinitary finite length codes. RAIRO Informatique théorique et Applications/Theoretical Informatics and Applications, 20(4):483-494, 1986. · Zbl 0628.68056
[31]	L. Staiger. Quadtrees and the Hausdorff dimension of pictures. In A. Hübler et al., editors, Geobild’89, volume 51 of Mathematical Research, pages 173-178, Georgenthal, 1989. · Zbl 0679.68169
[32]	L. Staiger. Kolmogorov complexity and Hausdorff dimension. Information and Computation (formerly Information and Control), 103:159-194, 1993. · Zbl 0789.68076
[33]	K. Wicks. Fractals and Hyperspaces, volume 1492 of LNM. Berlin: Springer-Verlag, 1991.