On the expressive power of counting
type: Item
instance of: scholarly article
title: On the expressive power of counting
zbMATH Open document ID: 0874.68091
DOI: 10.1016/0304-3975(95)00026-S
author: Stéphane Grumbach
author: Christophe Tollu
published in: Theoretical Computer Science
publication date: 1997-02-28T00:00:00Z
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 984933
zbMATH Keywords: LOGSPACE extension
zbMATH Keywords: PTIME extension
MaRDI profile type: Publication
cites work: On Moschovakis closure ordinals
cites work: Q3714043
cites work: A zero-one law for logic with a fixed-point operator
cites work: An application of games to the completeness problem for formalized theories
cites work: Probabilities on finite models
cites work: Finite-model theory -- A personal perspective
cites work: Q3666827
cites work: Q4283240
cites work: Complexity of the first-order theory of almost all finite structures
cites work: Fixed-point extensions of first-order logic
cites work: Q5533179
cites work: Logical hierarchies in PTIME
cites work: Relational queries computable in polynomial time
cites work: Zero-one law for an extension of first-order predicate language
cites work: 0-1 laws and decision problems for fragments of second-order logic
cites work: Infinitary logics and 0-1 laws
cites work: Generalized quantifiers and pebble games on finite structures
cites work: Q3113046
cites work: Almost sure theories
cites work: On a generalization of quantifiers
description: scientific article; zbMATH DE number 984933