Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy

DOI10.1007/11779148_37MaRDI QIDQ3617079zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)