Computably enumerable equivalence relations via primitive recursive reductions

DOI10.1093/LOGCOM/EXAD082MaRDI QIDQ6915763zbMATH OpenFDO

Authors B. S. Kalmurzayev, Nikolay Bazhenov, Alibek M. Iskakov

Publication date 15 October 2025

Published in Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/LOGCOM/EXAD082

zbMATH Keywords

computable reducibilitycomputably enumerable equivalence relationcomputably enumerable preorderprimitive recursive functionprimitive recursive reducibility

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Cites work

• A Note on Positive Equivalence Relations
• A survey on universal computably enumerable equivalence relations
• Algebraic structures computable without delay
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Borel equivalence relations
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Classifying equivalence relations in the Ershov hierarchy
• Classifying positive equivalence relations
• Computably enumerable equivalence relations
• CONSTRUCTIVE ALGEBRAS I
• EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Foundations of online structure theory. II: The operator approach
• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• scientific article; zbMATH DE number 1390028 (Why is no real title available?)
• Joins and meets in the structure of ceers
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• On isomorphism classes of computably enumerable equivalence relations
• On polynomial-time relation reducibility
• On the degree structure of equivalence relations under computable reducibility
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Positive equivalences
• Primitive recursive equivalence relations and their primitive recursive complexity
• Rogers semilattices of punctual numberings
• The back-and-forth method and computability without delay
• The first-order theory of the computably enumerable equivalence relations in the uncountable setting
• The structure of computably enumerable preorder relations
• The theory of ceers computes true arithmetic
• Universal computably enumerable equivalence relations

Cited in

(1)

• Undecidability of the degree structure of primitive recursive m-reducibility

This page was built for publication: Computably enumerable equivalence relations via primitive recursive reductions

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