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

Boolean termscomplexity theorydescriptive set theoryfine hierarchiesrecursion theory

Mathematics Subject Classification ID

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

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

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

Cited in

(28)

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

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)