12 citations · 18 across the 7 of their papers we have counts for
Showing 2007 · cs.CCShow all
2 papers · 2 filters
cs.CC2007★ 2 cited
Bounded Pushdown dimension vs Lempel Ziv information density
Pilar Albert, Elvira Mayordomo, Philippe Moser
In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a…
cs.CC2007
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…