Preprint series: 98-30, Reports on Computer Science

The paper is published: Bull. EATCS 66 (1998), pp. 178 - 182.

MSC:

68Q68 Automata theory, general, See also {03D05}

28A80 Fractals, See also {58Fxx}

Abstract: We show that there is an algorithm which computes Hausdorff
dimension and Hausdorff measure of arbitrary regular
\omega-languages. Our algorithm is a generalization of the one
given in a previous paper which was designed to compute Hausdorff dimension
and Hausdorff measure of regular \omega-languages closed in the
Cantor topology.

Our new algorithm is based on a decomposition lemma for regular
\omega-languages and a relationship between the Hausdorff measure
of regular \omega-languages of a special shape and their closures.

Keywords: Hausdorff dimension, finite automata, \omega-languages

Upload: 1998-10-19

Update: 2002 -09 -23