Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Eighth Annual IEEE Symposium on

Logic in Computer Science (LICS 1993)

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

Authors: Guy Fayolle Stéphane 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 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éphane Grumbach and Chritophe Tollu},
    title = 	 {Asymptotic probabilities of languages with generalized quantifiers },
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {199--207},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski