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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,865 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesLauri Hella, Leonid Libkin & Juha Nurmonen (1999). Notions of Locality and Their Logical Characterizations Over Finite Models. Journal of Symbolic Logic 64 (4):1751-1773.
Ursula Martin & Elizabeth Scott (1997). The Order Types of Termination Orderings on Monadic Terms, Strings and Monadic Terms, Strings and Multisets. Journal of Symbolic Logic 62 (2):624-635.
Kerkko Luosto (2000). Hierarchies of Monadic Generalized Quantifiers. Journal of Symbolic Logic 65 (3):1241-1263.
Shmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
Hans Läuchli & Christian Savioz (1987). Monadic Second Order Definable Relations on the Binary Tree. Journal of Symbolic Logic 52 (1):219-226.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Yuri Gurevich & Saharon Shelah (1983). Interpreting Second-Order Logic in the Monadic Theory of Order. Journal of Symbolic Logic 48 (3):816-828.
B. Courcelle (2012). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press.
Alan R. Woods (1997). Counting Finite Models. Journal of Symbolic Logic 62 (3):925-949.
Yuri Gurevich & Saharon Shelah (1983). Rabin's Uniformization Problem. Journal of Symbolic Logic 48 (4):1105-1119.
Analytics
Monthly downloads |
Added to index2009-02-05Total downloads14 ( #84,198 of 556,807 )Recent downloads (6 months)1 ( #64,847 of 556,807 )How can I increase my downloads? |
My notes
Discussion
