Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Effective Dimensions and Relative Frequencies

Edit abstract data

Author(s): Xiaoyang Gu and Jack H. Lutz
Slot: Wed, 16:30-16:50, Room 24 (col. 3)


Consider the problem of calculating the fractal dimension of a set X consisting of all infinite sequences S over a finite alphabet \Sigma that satisfy some given condition P on the asymptotic frequencies with which various symbols from \Sigma appear in S. Solutions to this problem are known in cases where (i) the fractal dimension is classical (Hausdorff or packing dimension), or (ii) the fractal dimension is effective (even finite-state) and the condition P completely specifies an empirical distribution \pi over \Sigma, i.e., a limiting frequency of occurrence for every symbol in \Sigma. In this paper we show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of such a set X when the condition P only imposes partial constraints on the limiting frequencies of symbols. Our results automatically extend to less restrictive effective fractal dimensions (e.g., polynomial-time, computable, and constructive dimensions), and they have the classical results (i) as immediate corollaries. Our methods are nevertheless elementary and, in most cases, simpler than those by which the classical results were obtained.

websites: Arnold Beckmann 2008-05-18 Valid HTML 4.01! Valid CSS!