一句话:为有限群定义三种Weisfeiler-Leman算法,刻画其表达能力与计数逻辑、双射石子博弈的关系。
有限群同构问题的组合方法相比代数方法发展不足。为研究有限群的描述复杂度和群同构问题,本文为群定义Weisfeiler-Leman算法,并给出三个版本。与图上三个类似版本容易一致不同,群上的情形更为复杂:作者证明这三个版本在表达能力上呈线性关系,并分别用计数逻辑和双射石子博弈刻画每个版本。该工作将图同构研究中的WL方法推广到群,为群同构问题的组合与逻辑复杂度分析提供了新工具。
In comparison to graphs, combinatorial methods for the isomorphism problem of finite groups are less developed than algebraic ones. To be able to investigate the descriptive complexity of finite groups and the group isomorphism problem, we define the Weisfeiler-Leman algorithm for groups. In fact we define three versions of the algorithm. In contrast to graphs, where the three analogous versions readily agree, for groups the situation is more intricate. For groups, we show that their expressive power is linearly related. We also give descriptions in terms of counting logics and bijective pebble games for each of the versions.