Valuations and Unambiguity of Languages, with Applications to Fractal
Geometry

H. Fernau, L. Staiger

	   Valuations - morphisms from the monoid of words to real
	   numbers - are a simple generalization of Bernoulli morphisms
	   (distributions, measures). 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
	   contextfree grammars, or for defining outer measures on the
	   space of infinite 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
	   contextfree grammars. Furthermore, we generalize the classical
	   notion of the entropy of a formal language.

	   This paper is an enhanced version of the one presented at
	   ICALP'94 (LNCS 820, Springer-Verlag, Berlin 1994, pp. 11 - 22).