<p>Courcelle's theorem states that  "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded clique-width graphs <a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf" rel="nofollow">[CMR99]</a>.</p>

<p>The theorem also holds with linear time replaced by logarithmic space <a href="http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Sommerakademie2010/talks/tantau_paper.pdf" rel="nofollow">[EJT10]</a> for bounded tree-width graphs.
My question is: Does this theorem still hold for bounded clique-width graphs if we replace linear time with logarithmic space? Let me know of the recent progress in this direction.</p>

CC BY-SA 3.0
2015-05-06T20:38:32.677Z
You should be careful with what you mean by "monadic second order logic". MSO${}_1$ (vertex set) properties can be extended to bounded clique-width, but MSO${}_2$ (edge set) properties only work with bounded treewidth.
David Eppstein
CC BY-SA 3.0
2015-05-07T07:18:49.770Z
I will assume that you are talking about $MSO_1$. I am not aware of any work, however as far as I know about the proof in Tantau et al.'s paper Section 4 can be probably translated to any graph grammar based on disjoint union, fusion and quantifier-free operations (which will include clique-width). Now, the problem will be how to construct a rank-decomposition (or clique-width expression) in logspace.
M. kanté
<cc.complexity-theory><lo.logic><cliquewidth>
Courcelle's theorem for bounded clique-width graphs
Kumar
# Courcelle's theorem for bounded clique-width graphs

(Asked by: username_0 on 2015-05-06)

Courcelle's theorem states that "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded clique-width graphs [[CMR99]](http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf).

The theorem also holds with linear time replaced by logarithmic space [[EJT10]](http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Sommerakademie2010/talks/tantau_paper.pdf) for bounded tree-width graphs.
My question is: Does this theorem still hold for bounded clique-width graphs if we replace linear time with logarithmic space? Let me know of the recent progress in this direction.

**Tags:** cc.complexity-theory, lo.logic, cliquewidth

> **Comments:**
> **username_1**: You should be careful with what you mean by "monadic second order logic". MSO${}_1$ (vertex set) properties can be extended to bounded clique-width, but MSO${}_2$ (edge set) properties only work with bounded treewidth.  
> **username_2**: I will assume that you are talking about $MSO_1$. I am not aware of any work, however as far as I know about the proof in Tantau et al.'s paper Section 4 can be probably translated to any graph grammar based on disjoint union, fusion and quantifier-free operations (which will include clique-width). Now, the problem will be how to construct a rank-decomposition (or clique-width expression) in logspace.  

---

## 0 answers

