Lower bounds for invariant queries in logics with counting.

DOI10.1016/S0304-3975(01)00152-9zbMath1058.03030DBLPjournals/tcs/LibkinW02OpenAlexW2063991224WikidataQ61910885 ScholiaQ61910885MaRDI QIDQ1853505

Limsoon Wong, Leonid O. Libkin

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00152-9

zbMATH Keywords

expressive powercomplexity classesdescriptive complexityfirst-order logic with countingcounting logics

Mathematics Subject Classification ID

Logic in computer science (03B70) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (1)

Game-based notions of locality over finite models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel computation with threshold functions
• Infinitary logics and 0-1 laws
• An optimal lower bound on the number of variables for graph identification
• Counting quantifiers, successor relations, and logarithmic space
• Query languages for bags and aggregate functions
• Local properties of query languages
• Logical hierarchies in PTIME
• Generalized quantifiers and pebble games on finite structures
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• On uniformity within \(NC^ 1\)
• Epsilon-logic is more expressive than first-order logic over finite structures
• On winning strategies with unary quantifiers
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Graph Connectivity, Monadic NP and built-in relations of moderate degree
• Notions of locality and their logical characterizations over finite models
• Logics with aggregate operators
• Natural proofs

This page was built for publication: Lower bounds for invariant queries in logics with counting.