Binary subtrees with few labeled paths

DOI10.1007/S00493-011-2634-3MaRDI QIDQ654001zbMATH OpenOpenAlexFDO

Authors Noam Greenberg, Carl G. jun. Jockusch, Kevin G. Milans, Rodney G. Downey

Publication date 20 December 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-011-2634-3

zbMATH Keywords

Cantor spaceBaire spacecomputability theoryrandomnessbinary subtreeKurtz random setMedvedev degreestrong reducibilityternary edge-labeled tree

Mathematics Subject Classification ID

Extremal combinatorics (05D99) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On growing random binary trees
• On the probability of occurence of labelled subtrees of a randomly labelled tree
• Sub-trees of a random tree
• Reverse mathematics, computability, and partitions of trees
• On the richness of the collection of subtrees in random binary search trees

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Algorithmic randomness and complexity.
• An Effective Version of Dilworth's Theorem
• Calibrating Randomness
• Diagonally non-recursive functions and effective Hausdorff dimension
• Difference sets and inverting the difference operator
• Functional iteration and the Josephus problem
• Mass Problems and Randomness
• On the Equimorphism Types of Linear Orderings
• The McKinsey axiom is not canonical
• The Medvedev lattice of computably closed sets
• The canonical Ramsey theorem and computability theory

Cited in

(8)

• The coding power of a product of partitions
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Growth and irreducibility in path-incompressible trees
• scientific article; zbMATH DE number 5016713 (Why is no real title available?)
• Diagonally non-computable functions and bi-immunity
• On the uniform computational content of computability theory
• Forcing with bushy trees
• Weihrauch Complexity in Computable Analysis

This page was built for publication: Binary subtrees with few labeled paths

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