scientific article; zbMATH DE number 1303200
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35) Theory of numerations, effectively presented structures (03D45)
A survey (including some new results) of the occurrences and uses of \(\Pi^0_1\) classes in areas such as logic, nonmonotonic logic, algebra, analysis, and combinatorics. More specifically, a typical result here represents \(\Pi^0_1\) classes by solutions to problems in one of these areas of application. E.g., given a recursive graph, its set of \(k\)-colorings forms a recursively bounded \(\Pi^0_1\) class. The representation result, loosely stated, is that every recursively bounded \(\Pi^0_1\) class arises in this manner. Such a representation then allows the general machinery of \(\Pi^0_1\) classes to be brought to bear on, in this case, recursive graph theory. Polynomial-time versions of these ideas are also treated. For the entire collection see [Zbl 0905.03002].
- scientific article; zbMATH DE number 1531920
- Π10 classes with complex elements
- Small \(\Pi^{0}_{1}\) classes
- \(\Pi_1^0\) classes and minimal degrees
- choice classes
- scientific article; zbMATH DE number 1390012
- scientific article; zbMATH DE number 3891998
- Functions of class \(\Pi\)
- Almost complemented \(\Pi^{0}_{1}\) classes
- Π01-classes and Rado's selection principle
- Members of countable \(\Pi ^ 0_ 1\) classes
- Index sets in computable analysis
- Feasible graphs with standard universe
- A blend of methods of recursion theory and topology.
- Effectively closed sets and graphs of computable real functions.
- \(\Pi_{1}^{0}\) classes and orderable groups
- A blend of methods of recursion theory and topology: a _1⁰ tree of shadow points
- Sequent calculi for skeptical reasoning in predicate default logic and other nonmonotonic logics
- The random members of a \({\Pi }_{1}^{0}\) class
- A connection between the Cantor-Bendixson derivative and the well-founded semantics of finite logic programs
- The members of thin and minimal \(\Pi_1^0\) classes, their ranks and Turing degrees
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Small \(\Pi^{0}_{1}\) classes
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
- Automorphisms of the lattice of _1⁰ classes; perfect thin classes and anc degrees
- choice classes
- \it \Pi^0_1 Sets and Tilings
- Computability in Symbolic Dynamics
- Invariance in ℰ* and ℰ_{Π}
- Computable symbolic dynamics
- On Turing degrees of points in computable topology
- Singular coverings and non‐uniform notions of closed set computability
- Immunity for closed sets
- Turing degrees of multidimensional SFTs
- Π01-classes and Rado's selection principle
- Coding true arithmetic in the Medvedev degrees of ^0_1 classes
- scientific article; zbMATH DE number 1531920 (Why is no real title available?)
- Recursive Quantum Functions, Avoidable Points, & Shadow Points in Recursive Analysis
- Singular coverings and non-uniform notions of closed set computability
- Effective symbolic dynamics
- Random Continuous Functions
- Computability of Subsets of Metric Spaces
- Subshifts with sparse traces
- Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
- COMPUTABLY COMPACT METRIC SPACES
- The complexity of recursive constraint satisfaction problems
- On degree-preserving homeomorphisms between trees in computable topology
- Effectively closed sets and enumerations
- The upward closure of a perfect thin class
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249723)
