Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

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.

Questions and Answers

You need to be logged in to be able to post here.