Fine hierarchies and Boolean terms

DOI10.2307/2275522MaRDI QIDQ4836056zbMATH OpenOpenAlexFDO

Authors Victor Selivanov

Publication date 31 October 1995

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275522

zbMATH Keywords

complexity theoryrecursion theorydescriptive set theoryBoolean termsfine hierarchies

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Descriptive set theory (03E15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Fine hierarchies and m-reducibilities in theoretical computer science
• The Boolean Hierarchy I: Structural Properties
• scientific article; zbMATH DE number 956483
• Fine hierarchy and definable index sets
• scientific article; zbMATH DE number 4045650

Cites work

• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Convex subsets of \(2^n\) and bounded truth-table reducibility
• Descriptive set theory

Cited in

(27)

• Boole vs Wadge: comparing two basic tools of descriptive set theory
• On the main scientific achievements of Victor Selivanov
• Logic vs topology on regular \(\omega \)-languages
• Fine hierarchies via Priestley duality
• The Shrinking Property for NP and coNP
• Fine hierarchy of regular \(\omega\)-languages
• A syntactic approach to Borel functions: some extensions of Louveau's theorem
• Turing degrees in refinements of the arithmetical hierarchy
• Fine hierarchies and m-reducibilities in theoretical computer science
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Fine hierarchy of regular \(\omega\)-languages
• Precomplete numberings
• scientific article; zbMATH DE number 7770056 (Why is no real title available?)
• The shrinking property for NP and coNP
• Normalized information distance and the oscillation hierarchy
• A Q-WADGE HIERARCHY IN QUASI-POLISH SPACES
• scientific article; zbMATH DE number 1534578 (Why is no real title available?)
• Facets of Synthesis: Revisiting Church’s Problem
• On the structure of the Wadge degrees of bqo-valued Borel functions
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• A reducibility for the dot-depth hierarchy
• Turing reducibility in the fine hierarchy
• Well-Quasi Orders and Hierarchy Theory
• Towards a descriptive set theory for domain-like structures
• 1999 European Summer Meeting of the Association for Symbolic Logic
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES

This page was built for publication: Fine hierarchies and Boolean terms

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