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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
H. 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.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #291,386 of 722,826 )
Recent downloads (6 months)0
How can I increase my downloads?