scientific article; zbMATH DE number 761756

MaRDI QIDQ4835660zbMATH OpenFDO

Authors Bernd Borchert

Publication date 8 June 1995

zbMATH Keywords

closure propertiescomplexity classescomplexity theorylanguage classespredicate classesprincipal idealpromise classesreducibilityregular language

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the acceptance power of regular languages
• Publication:4941920
• Promise problems complete for complexity classes
• scientific article; zbMATH DE number 874695
• scientific article; zbMATH DE number 2040898

Cited in

(9)

• Unambiguous computations and locally definable acceptance types
• Succinct representation, leaf languages, and projection reductions
• Optimal proof systems imply complete sets for promise classes
• A characterization of the leaf language classes
• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• Exact Pairs for Abstract Bounded Reducibilities
• scientific article; zbMATH DE number 1418356 (Why is no real title available?)
• Succinct circuit representations and leaf language classes are basically the same concept
• On the acceptance power of regular languages

This page was built for publication:

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