## Paper: Asymptotic probabilities of languages with generalized quantifiers (at LICS 1993)

Authors:**Guy Fayolle Stéphanie Grumbach Chritophe Tollu**

### Abstract

The impact of adding certain families of generalized quantifiers to first-order logic (FO) on the asymptotic behavior of sentences
is studied. All the results are stated and proved for languages disallowing free variables in the scope of generalized quantifiers.
For a class K of finite structures closed under isomorphism, the quantifier Q_{K} is said to be strongly monotonic, sm, if membership in the class is preserved under a loose form of extensions. The first
theorem (O/1 law for FO with any set of sm quantifiers) subsumes a previous criterion for proving that almost no graphs satisfy
a given property. A O/1 law for FO with Hartig quantifiers (equicardinality quantifiers) and a limit law for a fragment of
FO with Rescher quantifiers (expressing inequalities of cardinalities) are also established. It is also proved that the O/1
law fails for the extension of FO with Hartig quantifiers if the above syntactic restriction is relaxed, giving the best upper
bound for the existence of a O/1 law for FO with Hartig quantifiers

### BibTeX

@InProceedings{FayolleGrumbachToll-Asymptoticprobabili, author = {Guy Fayolle and Stéphanie Grumbach and Chritophe Tollu}, title = {Asymptotic probabilities of languages with generalized quantifiers }, booktitle = {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993}, year = 1993, editor = {Moshe Vardi}, month = {June}, pages = {199--207}, location = {Montreal, Canada}, publisher = {IEEE Computer Society Press} }