12 citations · 18 across the 7 of their papers we have counts for
8 papers · 1 filter
A General Notion of Useful Information
Philippe Moser
In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth noti…
Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
Elvira Mayordomo, Philippe Moser, Sylvain Perifel
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation, and in particular calls for a formulation of information-lossl…
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…
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…
Baire Categories on Small Complexity Classes and Meager-Comeager Laws
Philippe Moser
We introduce two resource-bounded Baire category notions on small complexity classes such as P, SUBEXP, and PSPACE and on probabilistic classes such as BPP, which differ on how the…
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…