Lower bounds for invariant queries in logics with counting.
type: Item
instance of: scholarly article
title: Lower bounds for invariant queries in logics with counting.
zbMATH Open document ID: 1058.03030
DOI: 10.1016/S0304-3975(01)00152-9
author: Limsoon Wong
author: Leonid Libkin
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 1857044
zbMATH Keywords: complexity classes
zbMATH Keywords: descriptive complexity
zbMATH Keywords: expressive power
zbMATH Keywords: counting logics
zbMATH Keywords: first-order logic with counting
Wikidata QID: Q61910885
MaRDI profile type: Publication
cites work: On uniformity within \(NC^ 1\)
cites work: Q4362726
cites work: An optimal lower bound on the number of variables for graph identification
cites work: Local properties of query languages
cites work: Q4850061
cites work: Counting quantifiers, successor relations, and logarithmic space
cites work: On monadic NP vs monadic co-NP
cites work: Q3666827
cites work: Q4218118
cites work: Logical hierarchies in PTIME
cites work: Notions of locality and their logical characterizations over finite models
cites work: Logics with aggregate operators
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Generalized quantifiers and pebble games on finite structures
cites work: Infinitary logics and 0-1 laws
cites work: Query languages for bags and aggregate functions
cites work: Q4381388
cites work: On winning strategies with unary quantifiers
cites work: Q4332930
cites work: Epsilon-logic is more expressive than first-order logic over finite structures
cites work: Parallel computation with threshold functions
cites work: Natural proofs
cites work: Graph Connectivity, Monadic NP and built-in relations of moderate degree
cites work: On winning Ehrenfeucht games and monadic NP
full work available at URL: s0304-3975(01)00152-9
OpenAlex ID: W2063991224
DBLP publication ID: journals/tcs/LibkinW02
Recommended article: Infinitary queries and their asymptotic probabilities. II. Properties definable in least fixed point logic
Recommended article: The Power of Counting Logics on Restricted Classes of Finite Structures
Recommended article: Q4332930
Recommended article: Q4202960
Recommended article: Two-variable first order logic with counting quantifiers: complexity results
Recommended article: A lower bound for intuitionistic logic
Recommended article: Q4893144
Recommended article: Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
Recommended article: On the Expressive Power of Logics with Invariant Uses of Arithmetic Predicates
description: scientific article; zbMATH DE number 1857044