Rutger Campbell

Rutger Campbell, Noleen Köhler

Laminar set systems consist of non-crossing subsets of a universe with set inclusion essentially corresponding to the descendant relationship of a tree, the so-called laminar tree. Laminar set systems lie at the core of many graph decompositions such as modular decompositions, split decompositions, and bi-join decompositions. We show that from a laminar set system we can obtain the corresponding laminar tree by means of a monadic second order logic (MSO) transduction. This resolves an open question originally asked by Courcelle and is a satisfying resolution as MSO is the natural logic for set systems and is sufficient to define the property ``laminar''. Using results from Campbell et al. [STACS 2025], we can now obtain transductions for obtaining modular decompositions, co-trees, split decompositions and bi-join decompositions using MSO instead of CMSO. We further gain some insight into the expressive power of counting quantifiers and provide some results towards determining when counting quantifiers can be simulated in MSO in laminar set systems and when they cannot.

Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté et al.

We give $\operatorname{CMSO}$-transductions that, given a graph $G$, output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant $\operatorname{MSO}$, a strictly more expressive logic than $\operatorname{CMSO}$. Our methods more generally yield $\operatorname{C}_2 \operatorname{MSO}$-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.