Generic density and small span theorem

DOI10.1016/J.IC.2007.10.001MaRDI QIDQ2475804zbMATH OpenOpenAlexFDO

Authors Philippe Moser

Publication date 11 March 2008

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://eprints.maynoothuniversity.ie/8243/1/PM-Generic-2008.pdf

zbMATH Keywords

genericityresource-bounded dimensionsmall span theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Fundamentals of Computation Theory
• A density version of the Halpern-Läuchli theorem
• A density statement generalizing Schur's theorem
• Density versions of two generalizations of Schur's theorem
• A density version of the Carlson-Simpson theorem
• On general densities and intersectivity
• The density theorem and Hausdorff inequality for packing measure in general metric spaces
• scientific article; zbMATH DE number 3852016
• Density-1-bounding and quasiminimality in the generic degrees
• scientific article; zbMATH DE number 4148256

Cites work

• Almost everywhere high nonuniform complexity
• Baire categories on small complexity classes and meager-comeager laws
• Category and Measure in Complexity Classes
• Effective fractal dimensions
• Finite-state dimension
• Fundamentals of Computation Theory
• Genericity and measure for exponential time
• Genericity and randomness over feasible probability measures
• Hard sets are hard to find
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• Prediction and dimension
• Small Spans in Scaled Dimension
• STACS 2004
• The dimensions of individual strings and sequences

Cited in

(1)

• Fundamentals of Computation Theory

This page was built for publication: Generic density and small span theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2475804)