Perfect correspondences between dot-depth and polynomial-time hierarchies

DOI10.1016/J.JCSS.2014.03.006zbMATH Open1410.68136OpenAlexW2036337451MaRDI QIDQ2453555FDOQ2453555

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

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

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)

Cites Work

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

Cited In (10)

• Mathematical Foundations of Computer Science 2004
• Hierarchies and reducibilities on regular languages related to modulo counting
• 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)