19
$\begingroup$

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

The theorem also holds with linear time replaced by logarithmic space [EJT10] 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.

Improve this question
$\endgroup$
2
  • 9
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented May 6, 2015 at 20:38
  • 8
    $\begingroup$ 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. $\endgroup$
    – M. kanté
    Commented May 7, 2015 at 7:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.