Perfect correspondences between dot-depth and polynomial-time hierarchies

DOI10.1016/j.jcss.2014.03.006zbMath1410.68136OpenAlexW2036337451MaRDI QIDQ2453555

Christian Glaßer, Stephen Travers, Klaus 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 complexitypolynomial-time hierarchydot-depth hierarchyleaf-languages

Mathematics Subject Classification ID

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

Cites Work

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