DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY

DOI10.1002/MALQ.19840303202MaRDI QIDQ3337459zbMATH OpenOpenAlexFDO

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)

• scientific article; zbMATH DE number 1138314 (Why is no real title available?)
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Complexity properties of recursively enumerable sets and \(bsQ\)-completeness
• scientific article; zbMATH DE number 4160710 (Why is no real title available?)
• Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
• Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Ordinal complexity of recursive definitions
• scientific article; zbMATH DE number 4130363 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 5295822 (Why is no real title available?)
• scientific article; zbMATH DE number 5000345 (Why is no real title available?)
• scientific article; zbMATH DE number 535104 (Why is no real title available?)

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)