On the expressive power of counting

DOI10.1016/0304-3975(95)00026-SzbMath0874.68091MaRDI QIDQ672336

Christophe Tollu, Stéphane Grumbach

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

LOGSPACE extensionPTIME extension

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (3)

INTERLEAVING LOGIC AND COUNTING ⋮ Verifiable properties of database transactions ⋮ Local properties of query languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-model theory -- A personal perspective
• 0-1 laws and decision problems for fragments of second-order logic
• Fixed-point extensions of first-order logic
• Infinitary logics and 0-1 laws
• Logical hierarchies in PTIME
• Generalized quantifiers and pebble games on finite structures
• On a generalization of quantifiers
• An application of games to the completeness problem for formalized theories
• Complexity of the first-order theory of almost all finite structures
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• Almost sure theories
• Zero-one law for an extension of first-order predicate language
• Probabilities on finite models
• On Moschovakis closure ordinals

This page was built for publication: On the expressive power of counting