Brief announcement: Distributed model checking on graphs of bounded treedepth

DOI10.1145/3662158.3662793MaRDI QIDQ6971955zbMATH OpenFDO

Authors Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Publication date 13 June 2025

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

zbMATH Keywords

CONGESTmodel checkingmonadic second-order logictreedepth

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites work

• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• A meta-theorem for distributed certification
• Approximate proof-labeling schemes
• Compact distributed certification of planar graphs
• Kernelizing MSO properties of trees of fixed height, and some consequences
• Local Certification of Graph Decompositions and Applications to Minor-Free Classes
• Local certification of graphs on surfaces
• Local certification of graphs with bounded genus
• Locally checkable proofs in distributed computing
• Methods for algorithmic meta theorems
• On the power of the congested clique model
• Proof labeling schemes
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
• Where first-order and monadic second-order logic coincide

This page was built for publication: Brief announcement: Distributed model checking on graphs of bounded treedepth

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