Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy

DOI10.1007/11779148_37zbMATH Open1227.68028OpenAlexW1544313815MaRDI QIDQ3617079FDOQ3617079

Authors: Christian Glaßer, Stephen Travers, K. W. Wagner 

Publication date: 26 March 2009

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11779148_37

Recommendations

• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Mathematical Foundations of Computer Science 2004
• A reducibility for the dot-depth hierarchy
• Proper hierarchies in polylogarithmic time and absence of complete problems
• Some results on the dot-depth hierarchy
• Relating polynomial time to constant depth
• scientific article; zbMATH DE number 8788
• Some logical characterizations of the dot-depth hierarchy and applications
• The polynomial and linear time hierarchies in V⁰
• Relativized Polynomial Time Hierarchies Having Exactly K Levels

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (10)

• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Mathematical Foundations of Computer Science 2004
• Dot operators
• Languages polylog-time reducible to dot-depth 1/2
• New Computational Paradigms
• A reducibility for the dot-depth hierarchy
• STACS 2005
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Proper hierarchies in polylogarithmic time and absence of complete problems
• Developments in Language Theory

This page was built for publication: Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy

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