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 hierarchypolynomial-time hierarchyleaf-languages

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 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
• STACS 2005
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• The dot-depth hierarchy of star-free languages is infinite
• The polynomial-time hierarchy

Cited in

(10)

• Hierarchies and reducibilities on regular languages related to modulo counting
• Mathematical Foundations of Computer Science 2004
• Dot operators
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• Languages polylog-time reducible to dot-depth 1/2
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• A reducibility for the dot-depth hierarchy
• 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 hierarchies

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