Elementary first-order model checking for sparse graphs

DOI10.1145/3661814.3662094MaRDI QIDQ6970241zbMATH OpenFDO

Authors Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis, Szymon Toruńczyk

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662094

zbMATH Keywords

sparsitybounded expansiontransductionsfirst-order model checkingelementary model-checking

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• A new perspective on FO model checking of dense graph classes
• A partial k-arboretum of graphs with bounded treewidth
• Deciding first-order properties of nowhere dense graphs
• Differential games, locality, and model checking for FO logic of graphs
• First order logic on Pathwidth revisited again
• First-Order Model Checking on Structurally Sparse Graph Classes
• First-order interpretations of bounded expansion classes
• First-order queries on classes of structures with bounded expansion
• Fixed-parameter tractability, definability, and model-checking
• Flip-width: cops and robber on dense graphs
• Grad and classes with bounded expansion. I: Decompositions
• Kernelizing MSO properties of trees of fixed height, and some consequences
• Linear rankwidth meets stability
• Methods for algorithmic meta theorems
• Model Theory Makes Formulas Large
• Model checking on interpretations of classes of bounded local cliquewidth
• Searching and pebbling
• Sparsity. Graphs, structures, and algorithms
• Stable graphs of bounded twin-width
• Structure and complexity of relational queries
• Testing first-order properties for subclasses of sparse graphs
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-width IV: ordered graphs and matrices
• Twin-width. I: Tractable FO model checking

Cited in

(1)

• On classes of bounded tree rank, their interpretations, and efficient sparsification

This page was built for publication: Elementary first-order model checking for sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970241)