A reducibility for the dot-depth hierarchy

DOI10.1016/j.tcs.2005.07.020zbMath1079.03028OpenAlexW2033286469MaRDI QIDQ2575760

Klaus W. Wagner, Victor L. Selivanov

Publication date: 6 December 2005

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

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

zbMATH Keywords

ReducibilityComplete setsLeaf languagesDot-depth hierarchyDegree structure

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items

Languages polylog-time reducible to dot-depth 1/2 ⋮ On the main scientific achievements of Victor Selivanov ⋮ Fine hierarchies via Priestley duality ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Fine hierarchies and m-reducibilities in theoretical computer science

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
• Classifying regular events in symbolic logic
• A uniform approach to define complexity classes
• The dot-depth hierarchy of star-free languages is infinite
• Polynomial closure and unambiguous product
• The chain method to separate counting classes
• Logspace and logtime leaf languages
• Dot-depth of star-free events
• A note on parallel queries and the symmetric-difference hierarchy.
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• On Existentially First-Order Definable Languages and Their Relation to NP
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Fine hierarchies and Boolean terms
• On balanced versus unbalanced computation trees
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• Mathematical Foundations of Computer Science 2004