Recursively Enumerable Equivalence Relations Modulo Finite Differences

DOI10.1002/MALQ.19940400407MaRDI QIDQ4315325zbMATH OpenOpenAlexFDO

Authors André Nies

Publication date 8 December 1994

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19940400407

zbMATH Keywords

\(m\)-reducibilityrecursion-theoretic semilatticerecursively enumerable equivalence relationstrue first-order arithmetic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Reducibilities among equivalence relations induced by recursively enumerable structures
• On Some Properties of Recursively Enumerable Equivalence Relations
• \(\Sigma^ n_ 0\)-equivalence relations
• scientific article; zbMATH DE number 535104
• On the degree structure of equivalence relations under computable reducibility

Cited in

(7)

• Elementary theories and hereditary undecidability for semilattices of numberings
• The theory of ceers computes true arithmetic
• Unification modulo lists with reverse relation with certain word equations
• Congruence relations on lattices of recursively enumerable sets
• On Some Properties of Recursively Enumerable Equivalence Relations
• Complete, Recursively Enumerable Relations in Arithmetic
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures

This page was built for publication: Recursively Enumerable Equivalence Relations Modulo Finite Differences

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