Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MONADIC SECOND-ORDER LOGIC:
Reports tagged with monadic second-order logic:
TR10-062 | 7th April 2010
Michael Elberfeld, Andreas Jakoby, Till Tantau

#### Logspace Versions of the Theorems of Bodlaender and Courcelle

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 ... more >>>

TR11-128 | 21st September 2011
Michael Elberfeld, Andreas Jakoby, Till Tantau

#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

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 ... more >>>

ISSN 1433-8092 | Imprint