1 citations · 3 across the 8 of their papers we have counts for
Showing cs.LOShow all
3 papers · 1 filter
cs.LO2026
A Rank-Preserving Locality Theorem
Jan Dreier, Szymon Toruńczyk
We prove a rank-preserving locality theorem for a syntactic variant of first-order logic, in the spirit of Gaifman's locality theorem and the rank-preserving locality theorem of Gr…
cs.LO2026★ 1 cited
Efficient reversal of transductions of sparse graph classes
Jan Dreier, Jakub Gajarský, Michał Pilipczuk
(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, we propose an efficient algorithmic method to…
cs.LO2023
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…