On the expressive power of counting

DOI10.1016/0304-3975(95)00026-SzbMATH Open0874.68091MaRDI QIDQ672336FDOQ672336

Authors: Stéphane Grumbach, Christophe Tollu 

Publication date: 28 February 1997

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

Recommendations

• The expressive power of fixed-point logic with counting
• scientific article; zbMATH DE number 515737
• Logics with counting and local properties
• Lower bounds for invariant queries in logics with counting.
• scientific article; zbMATH DE number 1086488

zbMATH Keywords

LOGSPACE extensionPTIME extension

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

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

Cited In (18)

• Local properties of query languages
• Arithmetic, first-order logic, and counting quantifiers
• The logic of counting query answers
• Hanf normal form for first-order logic with unary counting quantifiers
• Verifiable properties of database transactions
• Title not available (Why is that?)
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• First-order definable counting-only queries
• The Power of Counting Logics on Restricted Classes of Finite Structures
• How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited
• Logics with counting and local properties
• Extensions of MSO and the monadic counting hierarchy
• Counting Proportions of Sets: Expressive Power with Almost Order
• On counting propositional logic and Wagner's hierarchy
• INTERLEAVING LOGIC AND COUNTING
• LATIN 2004: Theoretical Informatics
• On the power of enumerative counting
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672336)