Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T22:34:04.089Z Has data issue: false hasContentIssue false

Counting finite models

Published online by Cambridge University Press:  12 March 2014

Alan R. Woods*
Affiliation:
Department of Mathematics, University of Western Australia, Nedlands W.A. 6907, Australia, E-mail: woods@maths.uwa.edu.au

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 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 -structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable