8 citations · 9 across the 2 of their papers we have counts for
3 papers · 1 filter
Simulating Logspace-Recursion with Logarithmic Quantifier Depth
Steffen van Bergerem, Martin Grohe, Sandra Kiefer +1
The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in the quest for a logic to capture all problems decidable in logarithmic space. It extends FO+C, first-order l…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Graphs Identified by Logics with Counting
Sandra Kiefer, Pascal Schweitzer, Erkal Selman
We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we…