Bounded-depth circuits

DOI10.1145/1060590.1060629MaRDI QIDQ3581426zbMATH OpenOpenAlexFDO

Authors Michal Koucký, Pavel Pudlák, Denis Thérien

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060629

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited in

(5)

• A circuit complexity approach to transductions
• The complexity of intersecting finite automata having few final states
• Circuit complexity of regular languages
• The regular languages of first-order logic with one alternation
• Dynamic membership for regular tree languages

This page was built for publication: Bounded-depth circuits

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