Paper: Asymptotic probabilities of languages with generalized quantifiers (at LICS 1993)
Authors: Guy Fayolle Stéphanie Grumbach Chritophe TolluAbstract
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 QK 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} }