MSO transduction recovers the laminar tree from a laminar set system, resolving Courcelle's question and enabling MSO constructions for modular, split, and bi-join decompositions.
Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press
7 Pith papers cite this work, alongside 289 external citations. Polarity classification is still indexing.
7
Pith papers citing it
289
external citations · OpenAlex
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
Tree-to-tree Hennie machines compute functions with linear size-to-height increase that lie between LSHI macro tree transducers and MSO set interpretations, are closed under specific compositions, contain the strict linear-height MTT composition hierarchy, and are equivalently characterized by a lin
The equational theory of relational Kleene algebra with graph loop is PSPACE-complete, and this PSPACE bound extends to top, tests, converse, and nominals, resolving the complexity of relational KAT with domain.
Fair MSO1 problems are W[1]-hard parameterized by cluster vertex deletion in general, but admit FPT algorithms under a sufficient condition that includes fair feedback vertex set, vertex cover, dominating set, and odd cycle transversal.
CMSO-transductions are given for the modular, split and bi-join decompositions of graphs, plus a generalization to weakly-partitive set systems.
The paper defines FO Cost-Value Decision for token-sliding discovery and proves FPT and W[1]-hardness results for Partial Vertex Cover Discovery across various graph classes.
Generalizes graph coverings and unfoldings to weighted versions, proves analogous theorems to Leighton-Norris, and obtains a canonical factorization of universal coverings plus a weighted version of characteristic polynomial factorization.
citing papers explorer
-
The role of counting quantifiers in laminar set systems
MSO transduction recovers the laminar tree from a laminar set system, resolving Courcelle's question and enabling MSO constructions for modular, split, and bi-join decompositions.
-
Tree transducers of linear size-to-height increase (and the additive conjunction of linear logic)
Tree-to-tree Hennie machines compute functions with linear size-to-height increase that lie between LSHI macro tree transducers and MSO set interpretations, are closed under specific compositions, contain the strict linear-height MTT composition hierarchy, and are equivalently characterized by a lin
-
The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
The equational theory of relational Kleene algebra with graph loop is PSPACE-complete, and this PSPACE bound extends to top, tests, converse, and nominals, resolving the complexity of relational KAT with domain.
-
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
Fair MSO1 problems are W[1]-hard parameterized by cluster vertex deletion in general, but admit FPT algorithms under a sufficient condition that includes fair feedback vertex set, vertex cover, dominating set, and odd cycle transversal.
-
CMSO-transducing tree-like graph decompositions
CMSO-transductions are given for the modular, split and bi-join decompositions of graphs, plus a generalization to weakly-partitive set systems.
-
FO Value Discovery and Partial Vertex Cover Discovery
The paper defines FO Cost-Value Decision for token-sliding discovery and proves FPT and W[1]-hardness results for Partial Vertex Cover Discovery across various graph classes.
-
Unfoldings and coverings of weighted graphs
Generalizes graph coverings and unfoldings to weighted versions, proves analogous theorems to Leighton-Norris, and obtains a canonical factorization of universal coverings plus a weighted version of characteristic polynomial factorization.