Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

DOI10.4230/LIPIcs.STACS.2012.66zbMath1245.68086OpenAlexW2170478756MaRDI QIDQ2904750

Michael Elberfeld, Till Tantau, Andreas Jakoby

Publication date: 23 August 2012

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2012/3405/pdf/21.pdf

zbMATH Keywords

monadic second-order logictree widthcircuit complexitytree depthalgorithmic meta theorem

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Parallel complexity for nilpotent groups, Balancing bounded treewidth circuits, Complexity of regular functions, Knapsack in graph groups, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, Practical algorithms for MSO model-checking on tree-decomposable graphs, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Closure properties of knapsack semilinear groups, Unnamed Item, TC^0 circuits for algorithmic problems in nilpotent groups, Knapsack in hyperbolic groups, Unnamed Item, Where First-Order and Monadic Second-Order Logic Coincide