COUNTING FINITE-MODELS

Let phi be a monadic second order sentence about a finite structure fr om a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of it element structures h as appropriate asymptotics, then unlabelled (labelled) asymptotic prob abilities v(phi) (mu(phi) respectively) for phi always exist. By apply ing generating series methods to count finite models, and a tailor mad e Tauberian lemma, this conjecture is proved under a mild additional c ondition on the asymptotics of the number of single component K-struct ures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of una ry predicates.