scientific article; zbMATH DE number 535104

MaRDI QIDQ4285797zbMATH OpenFDO

Authors André Nies

Publication date 21 March 1994

zbMATH Keywords

definabilitylattices of sets under inclusion and degree orderingsreducibilitiesundecidabilityupper semilattices of r.e. degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Undecidability of Brouwerian semilattices
• Some undecidability results for lattices in recursion theory
• Recursion theory in a lower semilattice
• Undecidability of free pseudo-complemented semilattices
• scientific article; zbMATH DE number 1984520
• scientific article; zbMATH DE number 5000345
• The semilattice of computable families of recursively enumerable sets
• DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY
• The undecidability of the semi-unification problem

Cited in

(20)

• Semilattices of disjunctive and linear degrees
• Undecidability results for low complexity time classes
• Elementary theories and hereditary undecidability for semilattices of numberings
• Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• Undecidable fragments of elementary theories
• On the structural properties of the set of fixpoints for nondeterministic recursive definitions
• Undecidability of elementary theories of Rogers semilattices of analytical hierarchies
• scientific article; zbMATH DE number 3880676 (Why is no real title available?)
• scientific article; zbMATH DE number 5000345 (Why is no real title available?)
• Degrees of presentability of structures. I
• scientific article; zbMATH DE number 3896923 (Why is no real title available?)
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• Recursively Enumerable Equivalence Relations Modulo Finite Differences
• scientific article; zbMATH DE number 1048044 (Why is no real title available?)
• Definability with a predicate for a semi-linear set
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• Undecidability and initial segments of the (r.e.) tt-degrees
• A Useful Undecidable Theory
• Undecidability and 1-types in the recursively enumerable degrees

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 Q4285797)