Effective Hausdorff Dimension in General Metric Spaces

Mayordomo, E. (Universidad de Zaragoza)

Resumen: 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.

Idioma: Inglés

DOI: 10.1007/s00224-018-9848-3

Año: 2018

Publicado en: THEORY OF COMPUTING SYSTEMS 62, 7 (2018), 1620-1636
ISSN: 1432-4350

Factor impacto JCR: 0.603 (2018)

Categ. JCR: MATHEMATICS rank: 208 / 313 = 0.665 (2018) - Q3 - T3
Categ. JCR: COMPUTER SCIENCE, THEORY & METHODS rank: 94 / 104 = 0.904 (2018) - Q4 - T3

Factor impacto SCIMAGO: 0.475 - Theoretical Computer Science (Q2) - Computational Theory and Mathematics (Q2)

Financiación: info:eu-repo/grantAgreement/ES/MINECO/PSI2014-62092-EXP
Financiación: info:eu-repo/grantAgreement/ES/MINECO/TIN2016-80347-R

Tipo y forma: Artículo (PostPrint)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)