Primitive recursive equivalence relations and their primitive recursive complexity

DOI10.3233/COM-210375MaRDI QIDQ5061388

Andrea Sorbi, Keng Meng Ng, Nikolay Bazhenov, Luca San Mauro

Publication date: 12 January 2023

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.04055

zbMATH Keywords

latticeprimitive recursive functionprimitive recursive equivalence relation

Mathematics Subject Classification ID

Computability and recursion theory (03Dxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Algebraic structures computable without delay
• Primitive recursive ordered fields and some applications
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Polynomial and abstract subrecursive classes
• Handbook of computability theory
• Eliminating unbounded search in computable algebra
• The theory of ceers computes true arithmetic
• Classifying equivalence relations in the Ershov hierarchy
• Online presentations of finitely generated structures
• On the degree structure of equivalence relations under computable reducibility
• On polynomial-time relation reducibility
• The metamathematics of algebraic systems. Collected papers: 1936-1967. Translated, edited, and provided with supplementary notes by Benjamin Franklin Wells III
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY
• A Survey on Universal Computably Enumerable Equivalence Relations
• Nondensity of Double Bubbles in the D.C.E. Degrees
• A Borel reductibility theory for classes of countable structures
• Borel Equivalence Relations
• Strong isomorphism reductions in complexity theory
• Classifying positive equivalence relations
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• On the Structure of Polynomial Time Reducibility
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• A structure of punctual dimension two
• Joins and meets in the structure of ceers
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• CONSTRUCTIVE ALGEBRAS I
• Isomorphism relations on computable structures
• Computably enumerable equivalence relations

This page was built for publication: Primitive recursive equivalence relations and their primitive recursive complexity