Logic in Computer Science (LICS 1993)

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}
  }