10.4230/LIPICS.STACS.2012.66
Elberfeld, Michael
Michael
Elberfeld
Jakoby, Andreas
Andreas
Jakoby
Tantau, Till
Till
Tantau
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2012
Article
algorithmic meta theorem
monadic second-order logic
circuit complexity
tree width
tree depth
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
2012
2012-02-24
2012-02-24
2012-02-24
en
urn:nbn:de:0030-drops-34059
10.4230/LIPIcs.STACS.2012
978-3-939897-35-4
1868-8969
10.4230/LIPIcs.STACS.2012
LIPIcs, Volume 14, STACS 2012
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
2013
14
8
66
77
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2012
14
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
600785 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
An algorithmic meta theorem for a logic and a class C of structures
states that all problems expressible in this logic can be solved
efficiently for inputs from $C$. The prime example is Courcelle's
Theorem, which states that monadic second-order (MSO) definable
problems are linear-time solvable on graphs of bounded tree width. We
contribute new algorithmic meta theorems, which state that
MSO-definable problems are (a) solvable by uniform constant-depth
circuit families (AC0 for decision problems and TC0 for counting
problems) when restricted to input structures of bounded tree depth
and (b) solvable by uniform logarithmic-depth circuit families (NC1
for decision problems and #NC1 for counting problems) when a tree
decomposition of bounded width in term representation is part of the
input. Applications of our theorems include a TC0-completeness proof
for the unary version of integer linear programming with a fixed
number of equations and extensions of a recent result that counting
the number of accepting paths of a visible pushdown automaton lies in
#NC1. Our main technical contributions are a new tree automata model
for unordered, unranked, labeled trees; a method for representing the
tree automata's computations algebraically using convolution circuits;
and a lemma on computing balanced width-3 tree decompositions of trees
in TC0, which encapsulates most of the technical difficulties
surrounding earlier results connecting tree automata and NC1.
LIPIcs, Vol. 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 66-77