Fine hierarchies and m-reducibilities in theoretical computer science

DOI10.1016/j.tcs.2008.06.031zbMath1165.03023OpenAlexW2052976441MaRDI QIDQ949621

Victor L. Selivanov

Publication date: 21 October 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.031

zbMATH Keywords

surveyBaire spacealternating treecomputabilitycomplexity theoryautomatondifference hierarchyordinals\(\omega \)-languageBaire domainBoolean termfine hierarchylogical hierarchyrecursive reducibilityset-theoretic hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items

The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Non-collapse of the effective Wadge hierarchy ⋮ A Q-WADGE HIERARCHY IN QUASI-POLISH SPACES ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Turing reducibility in the fine hierarchy ⋮ Towards a descriptive theory of cb₀-spaces ⋮ Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces ⋮ On the main scientific achievements of Victor Selivanov ⋮ Logic vs topology on regular \(\omega \)-languages ⋮ Two Effective Properties of ω-Rational Functions ⋮ Fine hierarchies via Priestley duality ⋮ Unnamed Item ⋮ On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ On the separation question for tree languages ⋮ Precomplete numberings ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Non-collapse of the effective wadge hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural complexity of ω-automata
• On Existentially First-Order Definable Languages and Their Relation to NP
• Continuous Lattices and Domains
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Fine hierarchies and Boolean terms
• On balanced versus unbalanced computation trees
• Fine hierarchy of regular ω-languages
• Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• A Useful Undecidable Theory
• Fine Hierarchy of Regular Aperiodic ω-Languages
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• On the Topological Complexity of Weakly Recognizable Tree Languages
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS
• Separation principles in the hierarchy theory of pure first-order logic
• Solving Sequential Conditions by Finite-State Strategies
• Trial and error predicates and the solution to a problem of Mostowski
• A discrete chain of degrees of index sets
• Machines, Computations, and Universality
• Logical Approaches to Computational Barriers
• The Wadge Hierarchy of Deterministic Tree Languages
• The Wadge Hierarchy of Deterministic Tree Languages
• Wadge hierarchy of omega context-free languages
• On the acceptance power of regular languages
• Finite-automaton aperiodicity is PSPACE-complete
• The Hausdorff-Ershov hierarchy in Euclidean spaces
• Towards a descriptive set theory for domain-like structures
• Languages polylog-time reducible to dot-depth 1/2
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• Structure of degrees of generalized index sets
• Ershov hierarchy
• Hierarchy of limiting computations
• Characterizations of some classes of regular events
• First-order logic and star-free sets
• Fine hierarchy of regular \(\omega\)-languages
• Descriptive set theory
• Structures of the degrees of unsolvability of index sets
• Chain properties in Pomega
• Structure of the m-degrees of the index sets of families of partial recursive functions
• Classifying regular events in symbolic logic
• Index sets of classes of hyper-hypersimple sets
• A uniform approach to define complexity classes
• \(X\)-automata on \(\omega\)-words
• The monadic second order theory of all countable ordinals
• The polynomial-time hierarchy
• Classical recursion theory. Vol. II
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Borel hierarchy and omega context free languages.
• Topology and ambiguity in \(\omega\)-context free languages
• Refined hierarchy of formulas
• Topological complexity with continuous operations
• Fine hierarchy and definable index sets
• Labeled posets are universal
• Boolean algebras, Tarski invariants, and index sets
• The theory of well-quasi-ordering: a frequently discovered concept
• A reducibility for the dot-depth hierarchy
• A note on parallel queries and the symmetric-difference hierarchy.
• Hierarchies in?-spaces and applications
• Characterizations of the class Δ^ta₂ over Euclidean spaces
• Separation principles in the hierarchies of classical and effective descriptive set theory
• Weak Second‐Order Arithmetic and Finite Automata
• Kleene index sets and functional m-degrees
• Borel ranks and Wadge degrees of context free $\omega$-languages
• The Shrinking Property for NP and coNP
• Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
• Hierarchies of function classes defined by the first-value operator
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
• The quotient algebra of labeled forests modulo h-equivalence
• Hierarchies and reducibilities on regular languages related to modulo counting
• Visibly pushdown languages
• The complexity of agreement
• Logical Refinements of Church’s Problem
• Undecidability in Some Structures Related to Computation Theory
• The difference and truth-table hierarchies for NP
• Hyperarithmetical Index Sets in Recursion Theory
• Les propriétés de réduction et de norme pour les classes de Boréliens
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• On ω-regular sets
• Countable structures, Ehrenfeucht strategies, and Wadge reductions
• Theorie der Numerierungen I
• Invariant sets in topology and logic
• Star-free regular sets of ω-sequences
• Π₁¹ Borel sets
• A Downward Collapse within the Polynomial Hierarchy
• Query Order
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Chains and Superchains for ω-Rational Sets, Automata and Semigroups
• Wadge Degrees ofω-Languages of Deterministic Turing Machines

This page was built for publication: Fine hierarchies and m-reducibilities in theoretical computer science