DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY

DOI10.1002/MALQ.19840303202zbMATH Open0546.03022OpenAlexW2070246900MaRDI QIDQ3337459FDOQ3337459

Authors: Robert Byerly 

Publication date: 1984

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

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

zbMATH Keywords

definability of recursively enumerable sets

Mathematics Subject Classification ID

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

Cited In (14)

• Title not available (Why is that?)
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Complexity properties of recursively enumerable sets and \(bsQ\)-completeness
• Title not available (Why is that?)
• Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
• Ordinal complexity of recursive definitions
• Title not available (Why is that?)
• A representation of recursively enumerable sets through Horn formulas in higher recursion theory
• On reduction of the decision problem of recursively enumerable sets to the separability problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY

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