20 citations · 132 across the 38 of their papers we have counts for
Showing 2005Show all
3 papers · 1 filter
cs.IT2005
Every Sequence is Decompressible from a Random One
David Doty
Kucera and Gacs independently showed that every infinite sequence is Turing reducible to a Martin-Lof random sequence. This result is extended by showing that every infinite sequen…
cs.IT2005
Pushdown dimension
David Doty, Jared Nichols
This paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. Pushdown dimension is trivially bounded above by finite-state dimens…
cs.CC2005
Zeta-Dimension
David Doty, Xiaoyang Gu, Jack H. Lutz +2
The zeta-dimension of a set A of positive integers is the infimum s such that the sum of the reciprocals of the s-th powers of the elements of A is finite. Zeta-dimension serves as…