Polylog-time reductions decrease dot-depth

DOI10.1007/978-3-540-31856-9_14MaRDI QIDQ5710672zbMATH OpenOpenAlexFDO

Authors Christian Glaßer

Publication date 2 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b106485

Mathematics Subject Classification ID

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

Recommendations

• A reducibility for the dot-depth hierarchy
• A reducibility for the dot-depth hierarchy
• Languages polylog-time reducible to dot-depth 1/2
• On adaptive DLOGTIME and POLYLOGTIME reductions
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 3999294
• Some results on the dot-depth hierarchy
• Reduction of OBDDs in linear time
• Computational depth and reducibility
• Computational depth and reducibility

Cited in

(5)

• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Hierarchies and reducibilities on regular languages related to modulo counting
• The dot-depth and the polynomial hierarchy correspond on the Delta levels
• Dot operators
• Languages polylog-time reducible to dot-depth 1/2

This page was built for publication: Polylog-time reductions decrease dot-depth

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