1 citations · 1 across the 3 of their papers we have counts for
Showing cs.LOShow all
2 papers · 1 filter
cs.LO2024
Finite Variable Counting Logics with Restricted Requantification
Simon Raßmann, Georg Schindling, Pascal Schweitzer
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula…
cs.LO2019
Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm
Moritz Lichter, Ilia Ponomarenko, Pascal Schweitzer
We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-…