Counting finite models
Journal of Symbolic Logic 62 (3):925-949 (1997)
| Abstract | Let φ be a monadic second order sentence about a finite structure from a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component K-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates | |||||||||
| 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,711 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesH. Andréka, I. Hodkinson & I. Németi (1999). Finite Algebras of Relations Are Representable on Finite Sets. Journal of Symbolic Logic 64 (1):243-267.
A. C. Walczak-Typke (2005). The First-Order Structure of Weakly Dedekind-Finite Sets. Journal of Symbolic Logic 70 (4):1161 - 1170.
David Fernández Duque (2011). On the Modal Definability of Simulability by Finite Transitive Models. Studia Logica 98 (3):347-373.
Ian Hodkinson & Martin Otto (2003). Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures. Bulletin of Symbolic Logic 9 (3):387-405.
M. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
Martin Otto (1996). The Expressive Power of Fixed-Point Logic with Counting. Journal of Symbolic Logic 61 (1):147-176.
Yuri Gurevich & Saharon Shelah (1996). On Finite Rigid Structures. Journal of Symbolic Logic 61 (2):549-562.
Eric Rosen (1997). Modal Logic Over Finite Structures. Journal of Logic, Language and Information 6 (4):427-439.
Robert Goldblatt (2001). Quasi-Modal Equivalence of Canonical Structures. Journal of Symbolic Logic 66 (2):497-508.
E. Fischer & J. A. Makowsky (2004). On Spectra of Sentences of Monadic Second Order Logic with Counting. Journal of Symbolic Logic 69 (3):617-640.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #275,109 of 551,054 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
