Asymptotic probabilities of languages with generalized quantifiers

Guy Fayolle 1 Stéphane Grumbach 2 Christophe Tollu 3
1 MEVAL - Methods, algorithms and software in automatic control
Inria Paris-Rocquencourt
2 VERSO - Databases
Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8629
3 LIPN - Laboratoire d'Informatique de Paris-Nord
Abstract : We study the impact of adding certain families of generalized quantifiers to first-order logic (FO) on the asymptotic behavior of sentences. All our 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. Our first theorem (0/1 law for FO with any set of sm quantifiers) subsumes a previous criterion for proving that almost no graphs satisfy a given property. We also establish a 0/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). The proofs of these last two results combine standard combinatorial enumerations with more sophisticated techniques from complex analysis. We also prove that the 0/1 law fails for the extension of FO with Hartig quantifiers if the above syntactic restriction is relaxed. We therefore get the best upper bound for the existence of a 0/1 law for FO with Hartigg quantifiers.
Type de document :
Communication dans un congrès
Eighth Annual IEEE Symposium on Logic in Computer Science, Jun 1993, Montréal / Canada, IEEE Computer Society, pp.199-207, 1993, Logic in Computer Science, 1993. LICS '93., Proceedings of Eighth Annual IEEE Symposium on. 〈10.1109/LICS.1993.287587〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00077192
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 17:16:43
Dernière modification le : mardi 17 avril 2018 - 11:32:00
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:49:58

Fichiers

RR-1916.pdf

Identifiants

Collections

INRIA | INRIA-RRRT | LIPN | UNIV-PARIS13 | USPC

Citation

Guy Fayolle, Stéphane Grumbach, Christophe Tollu. Asymptotic probabilities of languages with generalized quantifiers. Eighth Annual IEEE Symposium on Logic in Computer Science, Jun 1993, Montréal / Canada, IEEE Computer Society, pp.199-207, 1993, Logic in Computer Science, 1993. LICS '93., Proceedings of Eighth Annual IEEE Symposium on. 〈10.1109/LICS.1993.287587〉. 〈inria-00077192〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

63

Contact


archive-ouverte@inria.fr