Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-062 | 7th April 2010 14:01

Logspace Versions of the Theorems of Bodlaender and Courcelle

RSS-Feed




TR10-062
Authors: Michael Elberfeld, Andreas Jakoby, Till Tantau
Publication: 11th April 2010 00:23
Downloads: 5639
Keywords: 


Abstract:

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for
every $k$ there is a linear-time algorithm that decides whether a given logical structure $\mathcal A$ of tree width at most $k$ satisfies $\phi$. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.



ISSN 1433-8092 | Imprint