Model checking on interpretations of classes of bounded local cliquewidth
From MaRDI portal
Publication:6649489
DOI10.1145/3531130.3533367MaRDI QIDQ6649489
Jakub Gajarský, Stephan Kreutzer, Szymon Toruńczyk, Jan Dreier, Pierre Simon, Unnamed Author, Édouard Bonnet
Publication date: 6 December 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Learnability and definability in trees and similar structures
- Second-order quantifiers and the complexity of theories
- Computing roots of graphs is hard
- Bounded VC-dimension implies a fractional Helly theorem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Approximating clique-width and branch-width
- Recognizability, hypergraph operations, and logical types
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Deciding first-order properties of locally tree-decomposable structures
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Stable graphs
- A New Perspective on FO Model Checking of Dense Graph Classes
- Deciding First-Order Properties of Nowhere Dense Graphs
- Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory
- Twin-width II: small classes
- Twin-width I: Tractable FO Model Checking
- First-Order Interpretations of Bounded Expansion Classes
- Linear rankwidth meets stability
- A Guide to NIP Theories
- Directed Nowhere Dense Classes of Graphs
This page was built for publication: Model checking on interpretations of classes of bounded local cliquewidth
