# Courcelle's theorem for bounded clique-width graphs

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.

• 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. Commented May 6, 2015 at 20:38
• 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. Commented May 7, 2015 at 7:18