Relational Kleene algebra with graph loop has a PSPACE-complete equational theory over relational models.
Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
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-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
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.
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 Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
Relational Kleene algebra with graph loop has a PSPACE-complete equational theory over relational models.
-
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
-
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.
-
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.