We show that the spectrum of a sentence φ in Counting Monadic
Second Order Logic (CMSOL) using one binary relation symbol and
finitely many unary relation symbols, is ultimately periodic, provided
all the models of φ are of clique width at most k, for some
fixed k. We prove a similar statement for arbitrary finite
relational vocabularies τ and a variant of clique width for
τ-structures. This includes the cases where the models of φ
are of tree width at most k. For the case of bounded tree-width,
the ultimate periodicity is even proved for Guarded Second Order Logic
GSOL. We also generalize this result to many-sorted spectra, which
can be viewed as an analogue of Parikh’s Theorem on context-free
languages, and its analogues for context-free graph grammars due to
Habel and Courcelle.
Our work was inspired by Gurevich and Shelah (2003), who showed
ultimate periodicity of the spectrum for sentences of Monadic Second
Order Logic where only finitely many unary predicates and one unary
function are allowed. This restriction implies that the models are all
of tree width at most 2, and hence it follows from our result.