412 citations · 423 across the 12 of their papers we have counts for
6 papers · 1 filter
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
Jan Dreier, Daniel Mock, Peter Rossmanith
It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth- minors have constant density.…
Pseudorandom Finite Models
Jan Dreier, Jamie Tucker-Foltz
We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we sh…
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly general…
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz +1
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attent…
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…
Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. They showed that there is an efficient mo…