Lower bounds for invariant queries in logics with counting. (Q1853505): Difference between revisions

@@ Property / author @@
-Leonid O. Libkin
@@ Property / author: Leonid O. Libkin / rank @@
-Normal rank
@@ Property / author @@
+Leonid O. Libkin
@@ Property / author: Leonid O. Libkin / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q61910885
@@ Property / Wikidata QID: Q61910885 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+Q4362726
@@ Property / cites work: Q4362726 / rank @@
+Normal rank
@@ Property / cites work @@
+An optimal lower bound on the number of variables for graph identification
+Normal rank
@@ Property / cites work @@
+Local properties of query languages
@@ Property / cites work: Local properties of query languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q4850061
@@ Property / cites work: Q4850061 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting quantifiers, successor relations, and logarithmic space
+Normal rank
@@ Property / cites work @@
+On monadic NP vs monadic co-NP
@@ Property / cites work: On monadic NP vs monadic co-NP / rank @@
+Normal rank
@@ Property / cites work @@
+Q3666827
@@ Property / cites work: Q3666827 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4218118
@@ Property / cites work: Q4218118 / rank @@
+Normal rank
@@ Property / cites work @@
+Logical hierarchies in PTIME
@@ Property / cites work: Logical hierarchies in PTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Notions of locality and their logical characterizations over finite models
+Normal rank
@@ Property / cites work @@
+Logics with aggregate operators
@@ Property / cites work: Logics with aggregate operators / rank @@
+Normal rank
@@ Property / cites work @@
+Relational queries computable in polynomial time
@@ Property / cites work: Relational queries computable in polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Languages that Capture Complexity Classes
@@ Property / cites work: Languages that Capture Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized quantifiers and pebble games on finite structures
+Normal rank
@@ Property / cites work @@
+Infinitary logics and 0-1 laws
@@ Property / cites work: Infinitary logics and 0-1 laws / rank @@
+Normal rank
@@ Property / cites work @@
+Query languages for bags and aggregate functions
@@ Property / cites work: Query languages for bags and aggregate functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4381388
@@ Property / cites work: Q4381388 / rank @@
+Normal rank
@@ Property / cites work @@
+On winning strategies with unary quantifiers
@@ Property / cites work: On winning strategies with unary quantifiers / rank @@
+Normal rank
@@ Property / cites work @@
+Q4332930
@@ Property / cites work: Q4332930 / rank @@
+Normal rank
@@ Property / cites work @@
+Epsilon-logic is more expressive than first-order logic over finite structures
+Normal rank
@@ Property / cites work @@
+Parallel computation with threshold functions
@@ Property / cites work: Parallel computation with threshold functions / rank @@
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Connectivity, Monadic NP and built-in relations of moderate degree
+Normal rank
@@ Property / cites work @@
+On winning Ehrenfeucht games and monadic NP
@@ Property / cites work: On winning Ehrenfeucht games and monadic NP / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0304-3975(01)00152-9
+Normal rank
@@ Property / OpenAlex ID @@
+W2063991224
@@ Property / OpenAlex ID: W2063991224 / rank @@
+Normal rank
@@ Property / DBLP publication ID @@
+journals/tcs/LibkinW02
@@ Property / DBLP publication ID: journals/tcs/LibkinW02 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1853505