Document

**Published in:** LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces ℝⁿ. These are classical questions, meaning that their statements do not involve computation or related aspects of logic.
In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two fractal dimensions - computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim(x) and Dim(x) to individual points x ∈ X - to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families.
We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E₀, E₁, E₂, … used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ¹₁, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Extending the Reach of the Point-To-Set Principle. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.STACS.2022.48, author = {Lutz, Jack H. and Lutz, Neil and Mayordomo, Elvira}, title = {{Extending the Reach of the Point-To-Set Principle}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.48}, URN = {urn:nbn:de:0030-drops-158585}, doi = {10.4230/LIPIcs.STACS.2022.48}, annote = {Keywords: algorithmic dimensions, geometric measure theory, hyperspace, point-to-set principle} }

Document

**Published in:** LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true.
(1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S.
(2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S.
In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S.
Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S.
(1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}.
(2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}.
We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull. Asymptotic Divergences and Strong Dichotomy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2020.51, author = {Huang, Xiang and Lutz, Jack H. and Mayordomo, Elvira and Stull, Donald M.}, title = {{Asymptotic Divergences and Strong Dichotomy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51}, URN = {urn:nbn:de:0030-drops-119125}, doi = {10.4230/LIPIcs.STACS.2020.51}, annote = {Keywords: finite-state dimension, finite-state gambler, Kullback-Leibler divergence, normal sequences} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 1 (2012)

Research on the notions of information and randomness has drawn on methods and ideas from computability theory and cumputational complexity, as well as core mathematical subjects like measure theory and information theory. The Dagstuhl seminar 12021 ``Computability, Complexity and Randomness'' was aimed to meet people and ideas in these areas to share new results and discuss open problems.
This report collects the material presented during the course of the seminar.

Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo. Computability, Complexity and Randomness (Dagstuhl Seminar 12021). In Dagstuhl Reports, Volume 2, Issue 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{becher_et_al:DagRep.2.1.19, author = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, title = {{Computability, Complexity and Randomness (Dagstuhl Seminar 12021)}}, pages = {19--38}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {1}, editor = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.1.19}, URN = {urn:nbn:de:0030-drops-34555}, doi = {10.4230/DagRep.2.1.19}, annote = {Keywords: algorithmic randomness, computability theory, computationl complexity, Kolmogorov complexity, algorithmic information theory} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 395-404, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fortnow_et_al:LIPIcs.STACS.2010.2471, author = {Fortnow, Lance and Lutz, Jack H. and Mayordomo, Elvira}, title = {{Inseparability and Strong Hypotheses for Disjoint NP Pairs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {395--404}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2471}, URN = {urn:nbn:de:0030-drops-24711}, doi = {10.4230/LIPIcs.STACS.2010.2471}, annote = {Keywords: Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure, Genericity} }

Document

**Published in:** OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

We exhibit a polynomial time computable plane curve ${\bf \Gamma}$ that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization $f$ of ${\bf\Gamma}$ and every positive integer $m$, there is some positive-length subcurve of ${\bf\Gamma}$ that $f$ retraces at least $m$ times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Curves That Must Be Retraced. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 149-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:OASIcs.CCA.2009.2267, author = {Gu, Xiaoyang and Lutz, Jack H. and Mayordomo, Elvira}, title = {{Curves That Must Be Retraced}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {149--160}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2267}, URN = {urn:nbn:de:0030-drops-22674}, doi = {10.4230/OASIcs.CCA.2009.2267}, annote = {Keywords: Computable analysis, computable curve, computational complexity, Hausdorff measure, rectifiable curve} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

The pressing need for efficient compression schemes for XML
documents has recently been focused on stack computation (Hariharan
and Shankar 2006, League and Eng 2007), and in particular calls for
a formulation of information-lossless stack or pushdown compressors
that allows a formal analysis of their performance and a more
ambitious use of the stack in XML compression, where so far it is
mainly connected to parsing mechanisms. In this paper we introduce
the model of pushdown compressor, based on pushdown transducers
that compute a single injective function while keeping the widest
generality regarding stack computation.
The celebrated Lempel-Ziv algorithm LZ78 was introduced as a general
purpose compression algorithm that outperforms finite-state
compressors on all sequences. We compare the performance of the
Lempel-Ziv algorithm with that of the pushdown compressors, or
compression algorithms that can be implemented with a pushdown
transducer. This comparison is made without any a priori assumption
on the data's source and considering the asymptotic compression
ratio for infinite sequences. We prove that Lempel-Ziv is
incomparable with pushdown compressors.

Pilar Albert, Elvira Mayordomo, Philip Moser, and Sylvain Perifel. Pushdown Compression. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 39-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.STACS.2008.1332, author = {Albert, Pilar and Mayordomo, Elvira and Moser, Philip and Perifel, Sylvain}, title = {{Pushdown Compression}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {39--48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1332}, URN = {urn:nbn:de:0030-drops-13327}, doi = {10.4230/LIPIcs.STACS.2008.1332}, annote = {Keywords: Finite-state compression, Lempel-Ziv algorithm, pumping-lemma, pushdown compression, XML document} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail