Showing 2022 · cs.LOShow all
3 papers · 2 filters
cs.LO2022
Twin-width and types
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski +1
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local…
cs.LO2022
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…
cs.LO2022
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…