Primitive recursive equivalence relations and their primitive recursive complexity
From MaRDI portal
Publication:5061388
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
03Dxx: Computability and recursion theory
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