12 citations · 21 across the 6 of their papers we have counts for
5 papers · 1 filter
Limitations of Self-Assembly at Temperature One (extended abstract)
David Doty, Matthew J. Patitz, Scott M. Summers
We prove that if a subset X of the integer Cartesian plane weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition k…
Feasible Depth
David Doty, Philippe Moser
This paper introduces two complexity-theoretic formulations of Bennett's logical depth: finite-state depth and polynomial-time depth. It is shown that for both formulations, trivia…
Finite-State Dimension and Lossy Decompressors
David Doty, Philippe Moser
This paper examines information-theoretic questions regarding the difficulty of compressing data versus the difficulty of decompressing data and the role that information loss play…
Dimension Extractors and Optimal Decompression
David Doty
A *dimension extractor* is an algorithm designed to increase the effective dimension -- i.e., the amount of computational randomness -- of an infinite binary sequence, in order to…
Finite-State Dimension and Real Arithmetic
David Doty, Jack H. Lutz, Satyadev Nandakumar
We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+al…