Counting finite models
Alan R. Woods · Journal of Symbolic Logic · 1997
Abstract Letφbe a monadic second order sentence about a finite structure from a class which is closed under disjoint unions and has components. Compton has conjectured that if the number ofnelement 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 -structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.