THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
From MaRDI portal
Publication:5462667
DOI10.1142/S0129054105003200zbMath1161.68512MaRDI QIDQ5462667
Pascal Tesson, Denis Thérien, Klaus-Joern Lange, Frank Stephan, Bernd Borchert
Publication date: 3 August 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Related Items (3)
Lamplighter groups and automata ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Machines that can output empty words
Cites Work
- Unnamed Item
- A characterization of the leaf language classes
- Locally trivial categories and unambiguous concatenation
- A uniform approach to define complexity classes
- Sur le produit de concatenation non ambigu
- Polynomial closure and unambiguous product
- Regular languages defined by generalized first-order formulas with a bounded number of bound variables
- Randomness is Hard
- Relativized polynomial hierarchies extending two levels
- Bounded Query Classes
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Existentially First-Order Definable Languages and Their Relation to NP
- LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
This page was built for publication: THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
