Elberfeld, Michael ;
Jakoby, Andreas ;
Tantau, Till
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
Abstract
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 secondorder (MSO) definable
problems are lineartime solvable on graphs of bounded tree width. We
contribute new algorithmic meta theorems, which state that
MSOdefinable problems are (a) solvable by uniform constantdepth
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 logarithmicdepth 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 TC0completeness 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 width3 tree decompositions of trees
in TC0, which encapsulates most of the technical difficulties
surrounding earlier results connecting tree automata and NC1.
BibTeX  Entry
@InProceedings{elberfeld_et_al:LIPIcs:2012:3405,
author = {Michael Elberfeld and Andreas Jakoby and Till Tantau},
title = {{Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {6677},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3405},
URN = {urn:nbn:de:0030drops34059},
doi = {10.4230/LIPIcs.STACS.2012.66},
annote = {Keywords: algorithmic meta theorem, monadic secondorder logic, circuit complexity, tree width, tree depth}
}
2012
Keywords: 

algorithmic meta theorem, monadic secondorder logic, circuit complexity, tree width, tree depth 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 