On the Expressive Power of Counting

Stéphane Grumbach 1 Christophe Tollu 2
1 VERSO - Databases
Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8629
Abstract : We investigate the expressive power of various extensions of first-order, inductive, and infinitary logic with counting quantifiers. We consider in particular a LOGSPACE extension of first-order logic, and a PTIME extension of fixpoint logic with counters. Counting is a fundamental tool of algorithms. It is essential in the case of unordered structures. Our aim is to understand the expressive power gained with a limited counting ability. We consider two problems: (i) unnested counters, and (ii) counters with no free variables. We prove a hierarchy result based on the arity of the counters under the first restriction. The proof is based on a game technique that is introduced in the paper. We also establish results on the asymptotic probabilities of sentences with counters under the second restriction. In particular, we show that first-order logic with equality of the cardinalities of relations has a 0/1 law.
Type de document :
[Research Report] RR-2330, INRIA. 1992, pp.38
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:06:19
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:08:38




Stéphane Grumbach, Christophe Tollu. On the Expressive Power of Counting. [Research Report] RR-2330, INRIA. 1992, pp.38. 〈inria-00074344〉



Consultations de la notice


Téléchargements de fichiers