Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes

DOI10.46298/lmcs-19(2:14)2023arXiv2104.10446MaRDI QIDQ6135763

Jan Dreier

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.10446

zbMATH Keywords

first-order logicinterpretationsbounded expansiontransductions

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items

Bounding generalized coloring numbers of planar graphs using coin models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Algorithmic uses of the Feferman-Vaught theorem
• Strong computational lower bounds via parameterized complexity
• On low tree-depth decompositions
• Colouring graphs with bounded generalized colouring number
• Orderings on graphs and game coloring number
• Uniform orderings for generalized coloring numbers
• 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
• Coloring and Covering Nowhere Dense Graphs
• A New Perspective on FO Model Checking of Dense Graph Classes
• Deciding First-Order Properties of Nowhere Dense Graphs
• Twin-width I: Tractable FO Model Checking
• First-Order Interpretations of Bounded Expansion Classes
• On the number of types in sparse graphs
• Testing first-order properties for subclasses of sparse graphs
• First-Order Model-Checking in Random Graphs and Complex Networks