On the expressive power of counting

DOI10.1016/0304-3975(95)00026-SMaRDI QIDQ672336zbMATH OpenFDO

Authors Stéphane Grumbach, Christophe Tollu

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)00026-S

zbMATH Keywords

LOGSPACE extensionPTIME extension

Mathematics Subject Classification ID

Database theory (68P15)

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

Cites work

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

Cited in

(23)

• On the power of enumerative counting
• Verifiable properties of database transactions
• Counting quantifiers, successor relations, and logarithmic space
• Local properties of query languages
• Logical definability of counting functions
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited
• Counting Proportions of Sets: Expressive Power with Almost Order
• The Power of Counting Logics on Restricted Classes of Finite Structures
• scientific article; zbMATH DE number 4006240 (Why is no real title available?)
• scientific article; zbMATH DE number 515737 (Why is no real title available?)
• scientific article; zbMATH DE number 1086488 (Why is no real title available?)
• scientific article; zbMATH DE number 1136077 (Why is no real title available?)
• Hanf normal form for first-order logic with unary counting quantifiers
• The expressive power of fixed-point logic with counting
• The logic of counting query answers
• Arithmetic, first-order logic, and counting quantifiers
• Logics with counting and local properties
• LATIN 2004: Theoretical Informatics
• First-order definable counting-only queries
• On counting propositional logic and Wagner's hierarchy
• Extensions of MSO and the monadic counting hierarchy
• INTERLEAVING LOGIC AND COUNTING

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)