Effective Hausdorff Dimension in General Metric Spaces
Tóm tắt
We introduce the concept of effective dimension for a wide class of metric spaces whose metric is not necessarily based on a measure. Effective dimension was defined by Lutz (Inf. Comput., 187(1), 49–79, 2003) for Cantor space and has also been extended to Euclidean space. Lutz effectivization uses gambling, in particular the concept of gale and supergale, our extension of Hausdorff dimension to other metric spaces is also based on a supergale characterization of dimension, which in practice avoids an extra quantifier present in the classical definition of dimension that is based on Hausdorff measure and therefore allows effectivization for small time-bounds. We present here the concept of constructive dimension and its characterization in terms of Kolmogorov complexity, for which we extend the concept of Kolmogorov complexity to any metric space defining the Kolmogorov complexity of a point at a certain precision. Further research directions are indicated.
Tài liệu tham khảo
citation_journal_title=J. Comput. Syst. Sci.; citation_title=On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line; citation_author=J Cai, J Hartmanis; citation_volume=49; citation_publication_date=1994; citation_pages=605-619; citation_doi=10.1016/S0022-0000(05)80073-X; citation_id=CR1
citation_journal_title=Theor. Comput. Sci.; citation_title=Finite-state dimension; citation_author=JJ Dai, JI Lathrop, JH Lutz, E Mayordomo; citation_volume=310; citation_publication_date=2004; citation_pages=1-33; citation_doi=10.1016/S0304-3975(03)00244-5; citation_id=CR2
citation_title=Algorithmic Randomness and Complexity; citation_publication_date=2010; citation_id=CR3; citation_author=RG Downey; citation_author=DR Hirschfeldt; citation_publisher=Springer
citation_title=Fractal Geometry: Mathematical Foundations and Applications; citation_publication_date=2003; citation_id=CR4; citation_author=K Falconer; citation_publisher=Wiley
citation_journal_title=Theor. Comput. Sci.; citation_title=Uniform test of algorithmic randomness over a general space; citation_author=P Gács; citation_volume=341; citation_publication_date=2005; citation_pages=91-137; citation_doi=10.1016/j.tcs.2005.03.054; citation_id=CR5
citation_journal_title=Math. Ann.; citation_title=Dimension und äußeres Maß; citation_author=F Hausdorff; citation_volume=79; citation_publication_date=1919; citation_pages=157-179; citation_doi=10.1007/BF01457179; citation_id=CR6
citation_journal_title=SIGACT News Complexity Theory Column; citation_title=The fractal geometry of complexity classes; citation_author=JM Hitchcock, JH Lutz, E Mayordomo; citation_volume=36; citation_publication_date=2005; citation_pages=24-38; citation_id=CR7
citation_journal_title=Inf. Process. Lett.; citation_title=Base invariance of feasible dimension; citation_author=JM Hitchcock, E Mayordomo; citation_volume=113; citation_publication_date=2013; citation_pages=546-551; citation_doi=10.1016/j.ipl.2013.04.004; citation_id=CR8
citation_journal_title=Inf. Comput.; citation_title=Computability of probability measures and martin-löf randomness over metric spaces; citation_author=M Hoyrup, C Rojas; citation_volume=207; citation_publication_date=2009; citation_pages=830-847; citation_doi=10.1016/j.ic.2008.12.009; citation_id=CR9
citation_journal_title=SIAM J. Comput.; citation_title=Dimension in complexity classes; citation_author=JH Lutz; citation_volume=32; citation_issue=5; citation_publication_date=2003; citation_pages=1236-1259; citation_doi=10.1137/S0097539701417723; citation_id=CR10
citation_journal_title=Inf. Comput.; citation_title=The dimensions of individual strings and sequences; citation_author=JH Lutz; citation_volume=187; citation_issue=1; citation_publication_date=2003; citation_pages=49-79; citation_doi=10.1016/S0890-5401(03)00187-1; citation_id=CR11
Lutz, J.H., Lutz, N.: Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Transactions on Computation Theory. To appear
citation_journal_title=SIAM J. Comput.; citation_title=Dimensions of points in self-similar fractals; citation_author=JH Lutz, E Mayordomo; citation_volume=38; citation_publication_date=2008; citation_pages=1080-1112; citation_doi=10.1137/070684689; citation_id=CR13
Mayordomo, E.: Effective Fractal Dimension in Algorithmic Information Theory. In: New Computational Paradigms: Changing Conceptions of What is Computable, pp 259–285. Springer (2008)
citation_journal_title=Bull. London Math. Soc.; citation_title=Diagonally non-recursive functions and effective Hausdorff dimension; citation_author=J Miller, N Greenberg; citation_volume=43; citation_publication_date=2011; citation_pages=636-654; citation_doi=10.1112/blms/bdr003; citation_id=CR15
citation_journal_title=Math. Log. Q.; citation_title=Algorithmic randomness over general spaces; citation_author=K Miyabe; citation_volume=60; citation_publication_date=2014; citation_pages=184-204; citation_doi=10.1002/malq.201200051; citation_id=CR16
Reimann, J.: Computability and Fractal Dimension. Phd thesis University of Heidelberg (2004)
citation_journal_title=Soviets Math. Doklady; citation_title=Coding of combinatorial sources and Hausdorff dimension; citation_author=YB Ryabko; citation_volume=30; citation_publication_date=1984; citation_pages=219-222; citation_id=CR18
citation_journal_title=Probl. Inf. Transm.; citation_title=Noiseless coding of combinatorial sources; citation_author=YB Ryabko; citation_volume=22; citation_publication_date=1986; citation_pages=170-179; citation_id=CR19
citation_journal_title=Theory Comput. Syst.; citation_title=Symbolic dynamics: entropy = dimension = complexity; citation_author=SG Simpson; citation_volume=56; citation_publication_date=2015; citation_pages=527-543; citation_doi=10.1007/s00224-014-9546-8; citation_id=CR20
citation_journal_title=Inf. Comput.; citation_title=Kolmogorov complexity and Hausdorff dimension; citation_author=L Staiger; citation_volume=103; citation_publication_date=1993; citation_pages=159-94; citation_doi=10.1006/inco.1993.1017; citation_id=CR21
citation_journal_title=Theory Comput. Syst.; citation_title=A tight upper bound on Kolmogorov complexity and uniformly optimal prediction; citation_author=L Staiger; citation_volume=31; citation_publication_date=1998; citation_pages=215-29; citation_doi=10.1007/s002240000086; citation_id=CR22
citation_title=Computable Analysis. An Introduction; citation_publication_date=2000; citation_id=CR23; citation_author=K Weihrauch; citation_publisher=Springer