research
∙
04/25/2023
Simulating Logspace-Recursion with Logarithmic Quantifier Depth
The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in ...
share
research
∙
01/23/2023
Revisiting the growth of polyregular functions: output languages, weighted automata and unary inputs
Polyregular functions are the class of string-to-string functions defina...
research
∙
06/21/2022
A Study of Weisfeiler-Leman Colorings on Planar Graphs
The Weisfeiler-Leman (WL) algorithm is a combinatorial procedure that co...
research
∙
03/25/2022
SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks
While (message-passing) graph neural networks have clear limitations in ...
research
∙
01/26/2022
Treelike decompositions for transductions of sparse graphs
We give new decomposition theorems for classes of graphs that can be tra...
research
∙
06/30/2021
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial proced...
research
∙
05/20/2020
The Iteration Number of Colour Refinement
The Colour Refinement procedure and its generalisation to higher dimensi...
research
∙
08/14/2019
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
The Weisfeiler-Leman procedure is a widely-used approach for graph isomo...
research
∙
05/30/2019
String-to-String Interpretations with Polynomial-Size Output
String-to-string MSO interpretations are like Courcelle's MSO transducti...
research
∙
04/15/2019
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inhe...
research
∙
08/24/2017