HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074344
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:06:19 PM
Last modification on : Friday, February 4, 2022 - 3:08:02 AM
Long-term archiving on: : Monday, April 5, 2010 - 12:08:38 AM

Identifiers

Citation

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

Share

Metrics

Record views

188

Files downloads

130