Perfect correspondences between dot-depth and polynomial-time hierarchies

DOI10.1016/J.JCSS.2014.03.006MaRDI QIDQ2453555zbMATH OpenOpenAlexFDO

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

Publication date 10 June 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2014.03.006

zbMATH Keywords

computational complexitydot-depth hierarchyleaf-languagespolynomial-time hierarchy

Mathematics Subject Classification ID

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

Recommendations

• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• STACS 2005
• Languages polylog-time reducible to dot-depth 1/2
• Developments in Language Theory
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS

Cites work

• A uniform approach to define complexity classes
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Complete sets and the polynomial-time hierarchy
• Dot-depth of star-free events
• First-order logic and star-free sets
• Fundamentals of Computation Theory
• Lindström quantifiers and leaf language definability
• On Existentially First-Order Definable Languages and Their Relation to NP
• On the acceptance power of regular languages
• Polynomial closure and unambiguous product
• Polynomial operations and hierarchies of concatenation
• Programs over semigroups of dot-depth one
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• STACS 2005
• The dot-depth hierarchy of star-free languages is infinite
• The polynomial-time hierarchy

Cited in

(10)

• Proper hierarchies in polylogarithmic time and absence of complete problems
• A reducibility for the dot-depth hierarchy
• Hierarchies and reducibilities on regular languages related to modulo counting
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Mathematical Foundations of Computer Science 2004
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Developments in Language Theory
• Dot operators
• Languages polylog-time reducible to dot-depth 1/2

This page was built for publication: Perfect correspondences between dot-depth and polynomial-time hierarchies

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