Abstract
We show that the classical Hausdorff and constructive dimensions of any union of Π 01 -definable sets of binary sequences are equal. If the union is effective, that is, the set of sequences is Σ 02 -definable, then the computable dimension also equals the Hausdorff dimension. This second result is implicit in the work of Staiger (1998).
Staiger also proved related results using entropy rates of decidable languages. We show that Staiger’s computable entropy rate provides an equivalent definition of computable dimension. We also prove that a constructive version of Staiger’s entropy rate coincides with constructive dimension.
This research was supported in part by National Science Foundation Grant 9988483.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. H. Lutz. Dimension in complexity classes. In Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity, pages 158–169. IEEE Computer Society Press, 2000.
J. H. Lutz. Information and computation seminar. Iowa State University, 2000. Unpublished lectures.
J. H. Lutz. The dimensions of individual strings and sequences. Technical Report cs.CC/0203016, ACM Computing Research Repository, 2002.
C. A. Rogers. Hausdorff Measures. Cambridge University Press, 1998. Originally published in 1970.
L. Staiger. Kolmogorov complexity and Hausdorff dimension. Information and Control, 103:159–94, 1993.
L. Staiger. A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems, 31:215–29, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hitchcock, J.M. (2002). Correspondence Principles for Effective Dimensions. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds) Automata, Languages and Programming. ICALP 2002. Lecture Notes in Computer Science, vol 2380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45465-9_48
Download citation
DOI: https://doi.org/10.1007/3-540-45465-9_48
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43864-9
Online ISBN: 978-3-540-45465-6
eBook Packages: Springer Book Archive