Constructive Dimension and Weak Truth-Table Degrees

DOI10.1007/978-3-540-73001-9_7MaRDI QIDQ5426866zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, David Doty, Frank Stephan

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_7

zbMATH Keywords

constructive dimensiondegreeextractorrandomnessweak truth-table

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Constructive dimension and Turing degrees
• Hausdorff-dimension and weak truth-table reducibility
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• The arithmetical complexity of dimension and randomness
• Computer Science Logic

Cited in

(12)

• Dimension extractors and optimal decompression
• Intervals and sublattices of the r.e. weak truth table degrees. II: Nonbounding
• Weak truth table degrees of structures
• Algorithmically Independent Sequences
• On a metric generalization of the \(tt\)-degrees and effective dimension theory
• Hausdorff-dimension and weak truth-table reducibility
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• Constructive dimension and Turing degrees
• Algorithmically independent sequences
• Turing degrees of reals of positive effective packing dimension

This page was built for publication: Constructive Dimension and Weak Truth-Table Degrees

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