Author name cluster

Donald M. Stull

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

MFCS Conference 2019 Conference Paper

Semicomputable Points in Euclidean Spaces

Mathieu Hoyrup
Donald M. Stull

We introduce the notion of a semicomputable point in R^n, defined as a point having left-c. e. projections. We study the range of such a point, which is the set of directions on which its projections are left-c. e. , and is a convex cone. We provide a thorough study of these notions, proving along the way new results on the computability of convex sets. We prove realization results, by identifying computability properties of convex cones that make them ranges of semicomputable points. We give two applications of the theory. The first one provides a better understanding of the Solovay derivatives. The second one is the investigation of left-c. e. quadratic polynomials. We show that this is, in fact, a particular case of the general theory of semicomputable points.

Details

MFCS Conference 2018 Conference Paper

Projection Theorems Using Effective Dimension

Neil Lutz
Donald M. Stull

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which shows that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.

Details

MFCS Conference 2018 Conference Paper

Results on the Dimension Spectra of Planar Lines

Donald M. Stull

In this paper we investigate the (effective) dimension spectra of lines in the Euclidean plane. The dimension spectrum of a line L_{a, b}, sp(L), with slope a and intercept b is the set of all effective dimensions of the points (x, ax + b) on L. It has been recently shown that, for every a and b with effective dimension less than 1, the dimension spectrum of L_{a, b} contains an interval. Our first main theorem shows that this holds for every line. Moreover, when the effective dimension of a and b is at least 1, sp(L) contains a unit interval. Our second main theorem gives lower bounds on the dimension spectra of lines. In particular, we show that for every alpha in [0, 1], with the exception of a set of Hausdorff dimension at most alpha, the effective dimension of (x, ax + b) is at least alpha + dim(a, b)/2. As a consequence of this theorem, using a recent characterization of Hausdorff dimension using effective dimension, we give a new proof of a result by Molter and Rela on the Hausdorff dimension of Furstenberg sets.

Details

MFCS Conference 2016 Conference Paper

Polynomial Space Randomness in Analysis

Xiang Huang 0001
Donald M. Stull

We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.

Details