The role of counting quantifiers in laminar set systems
Rutger Campbell, Noleen Köhler · 2025
Read The role of counting quantifiers in laminar set systems by Rutger Campbell, Noleen Köhler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02617.txt.
Introduction
Rutger Campbell and Noleen Köhler study laminar set systems, families of sets that never partly overlap. In such a family, any two sets are either separate or one contains the other, like a tree of folders. These systems sit at the core of modular, split, and bi-join decompositions of graphs.
The pair examines what counting quantifiers, logic tools that count how many elements fit a rule, can express about laminar systems. The results clarify which properties of these tidy structures logic can capture. That helps both logicians and algorithm designers who lean on such decompositions. Tree like sets are rare in raw data, so tools that spot them earn their keep in code bases.
Catalog record
| CREATOR | Rutger Campbell, Noleen Köhler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-02617
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The role of counting quantifiers in laminar set systems Rutger Campbell, Noleen Köhler Abstract 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 \operatorname{MSO} ) transduction. This resolves an open question originally asked by Courcelle and is a satisfying resolution as MSO \operatorname{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 \operatorname{MSO} instead of CMSO \operatorname{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 \operatorname{MSO} in laminar set systems and when they cannot. School of Computing, KAIST, Daejeon, South [email protected] School of Computer Science, University of Leeds, Leeds, [email protected]://orcid.org/0000-0002-1023-6530 Campbell was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Science and ICT (No. RS-2025-00563533). We thank the Institute for Basic Science (IBS-R029-C1) for funding and hosting the research visit where this work was conducted. ccs Theory of computation Finite Model Theory keywords \operatorname{MSO} -transductions, simulating counting quantifiers, laminar set systems, graph decompositions † † runningauthor: R. Campbell and N. Köhler † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction A transduction transforms relational structures over an input vocabulary \Sigma_{1} into relation structures over an output vocabulary \Sigma_{2} in such a way that each \Sigma_{2} -definable property can be “translated” back to a \Sigma_{1} -definable preimage. Theorem 1 (Backwards Translation Theorem [ 7 , Theorem 1.40] ) . Let \tau be a \operatorname{MSO} -transduction with input vocabulary \Sigma_{1} and output vocabulary \Sigma_{2} . If \phi_{2} is an \operatorname{MSO} -sentence over \Sigma_{2} , then there is a \operatorname{MSO} -sentence \phi_{1} over \Sigma_{1} so that, the sentence \phi_{1} holds for precisely the structures \mathbb{A} over \Sigma_{1} for which \tau(\mathbb{A}) contains a structure satisfying \phi_{2} . This is incredibly useful as it means derived structure can be used to define properties. Of particular significance is derived tree-structure, due to connections to tree-automata. Thatcher and Wright showed that a property of labelled rooted trees of bounded degree is \operatorname{MSO} -definable if and only if it is recognizable by a tree-automaton. So if we have a class of objects from which we can transduce a bounded tree description, from whence we can, in turn, transduce the original object, then \operatorname{MSO} -definability of the original object corresponds to recognizability with a tree-automaton. There are also generalizations of the Theorem of Thatcher and Wright which rely on the same principles of obtaining a tree-structured decomposition and then using backwards translation to simulate a run of the tree-automaton on the decomposition. Most prominently, for graphs of bounded treewidth, \operatorname{MSO} -definability is equivalent to tree-automaton recognizability, where the forwards implication is Courcelle’s Theorem [ 9 ] and the backward direction was finally shown by Bojańczyk and Pilipczuk in 2016 [ 2 ] . Using the powerful method of Simon’s factorization [ 19 ] , results of Bojańczyk et al. [ 1 ] show that definability equal recognizability in graphs of bounded linear clique-width. This was recently generalized to show definability equal recognizability in classes of represented matroids [ 3 ] and more generally representable matroids [ 5 ] over finite fields of bounded linear branch-width. In pursuit of understanding when definability equals recognizability, Courcelle studied how to transduce tree-structured decompositions such as modular decompositions and split decompositions [ 10 , 11 , 12 , 14 ] . In this series of work, Courcelle uses order invariant \operatorname{MSO} , which allows the use of a global linear order of the vertices of the graph. This logic is strictly more expressive than \operatorname{MSO} with counting quantifiers, denoted \operatorname{CMSO} , which in turn is more expressive than \operatorname{MSO} [ 16 ] . These transductions were recently improved to avoid the use of linear order, but still relied on counting quantifiers for the key step [ 4 ] . This key step involves transducing a tree from a collection of sets and was independently described by Bojańczyk [ 3 ] , also using counting quantifiers. It was asked as an open question in [ 3 , 4 , 13 ] whether this transduction can be obtained using just \operatorname{MSO} . We focus on transducing a tree from the setting of set systems as it provides a general form of structure itself, to which many other settings have a transduction to. A set system is a pair (U,\mathcal{F}) consisting of a set U and a family \mathcal{F} of subsets of U . We model this over the vocabulary \{\mathsf{SET}\} , consisting of the unary set-predicate \mathsf{SET} , by taking \{\mathsf{SET}\} -structure \mathbb{F} with universe U_{\mathbb{F}} and taking \mathsf{SET}_{\mathbb{F}}(X) to be true precisely when X\in\mathcal{F} . We say a set system is laminar when: U\in\mathcal{F} , for each u\in U the singleton \{u\}\in\mathcal{F} , and for any F_{1},F_{2}\in\mathcal{F} the intersection F_{1}\cap F_{2} is one of \emptyset,F_{1},F_{2} . For the last condition, we say that F_{1} and F_{2} do not cross. Any laminar set system (U,\mathcal{F}) naturally corresponds to a tree T , called the laminar tree of (U,\mathcal{F}) , in which each node of T corresponds to a set in \mathcal{F} and the descendant relation coincides with the subset relation. In particular, U\in\mathcal{F} corresponds to the root of T while the leaves of T correspond to the singletons \{u\}\in\mathcal{F} . For ease of notation, we identify u\in U with the leaf that corresponds to the singleton \{u\} . Doing this, a set F\in\mathcal{F} corresponds to the node v_{F} of T where the leaves that are descendants of v_{F} are precisely the elements of F . For an example of a laminar set system and its laminar tree see \cref fig:laminarTree. In this paper, we introduce a new technique for choosing a representative leaf for every node of a tree in such a way that each leaf is used only a bounded number of times, we give an \operatorname{MSO} -transduction that, given any laminar set system (U,\mathcal{F}) , outputs its laminar tree. We believe that our new technique is of independent interest to the community and has other applications. Formally, our main theorem is the following: Theorem 2 . There is an \operatorname{MSO} -transduction \tau from structures over the vocabulary \{\mathsf{SET}\} of set systems, to structures over the vocabulary \{\mathsf{desc}\} of rooted trees, such that if (U,\mathcal{F}) is a laminar set system, then its image is the