On spectra of sentences of monadic second order logic with counting

Journal of Symbolic Logic 69 (3):617-640 (2004)
Abstract
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1096901758
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 25,651
Through your library
References found in this work BETA
Monadic Generalized Spectra.Ronald Fagin - 1975 - Mathematical Logic Quarterly 21 (1):89-96.
Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität.Günter Asser - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (4):252-263.
Arity and Alternation in Second-Order Logic.J. A. Makowsky & Y. B. Pnueli - 1996 - Annals of Pure and Applied Logic 78 (1-3):189-202.
Some Remarks on Generalized Spectra.L. Lovász & P. Gács - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (36):547-554.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Monthly downloads

Added to index

2009-02-05

Total downloads

35 ( #140,609 of 2,143,561 )

Recent downloads (6 months)

4 ( #185,644 of 2,143,561 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums