Counting Finite Models
Woods, Alan R.
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 925-949 / Harvested from Project Euclid
Let $\varphi$ be a monadic second order sentence about a finite structure from a class $\mathscr{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 $\nu(\varphi) (\mu(\varphi)$ respectively) for $\varphi$ 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 $\mathscr{K}$-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.
Publié le : 1997-09-14
Classification: 
@article{1183745305,
     author = {Woods, Alan R.},
     title = {Counting Finite Models},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 925-949},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745305}
}
Woods, Alan R. Counting Finite Models. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  925-949. http://gdmltest.u-ga.fr/item/1183745305/