paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the Weisfeiler-Leman Dimension of Finite Groups

论有限群的Weisfeiler-Leman维数
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文研究有限群上的Weisfeiler-Leman算法、描述复杂性与群同构问题,属于组合群论与逻辑领域,与用户关注的程序静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向几乎没有交集。引用 0 inbox
Jendrik Brachter, Pascal Schweitzer
crossref: 2026-09-12

AI 速览

一句话:为有限群定义三种Weisfeiler-Leman算法,刻画其表达能力与计数逻辑、双射石子博弈的关系。

有限群同构问题的组合方法相比代数方法发展不足。为研究有限群的描述复杂度和群同构问题,本文为群定义Weisfeiler-Leman算法,并给出三个版本。与图上三个类似版本容易一致不同,群上的情形更为复杂:作者证明这三个版本在表达能力上呈线性关系,并分别用计数逻辑和双射石子博弈刻画每个版本。该工作将图同构研究中的WL方法推广到群,为群同构问题的组合与逻辑复杂度分析提供了新工具。

问题
有限群同构问题的组合方法不如代数方法成熟,需要新的组合工具来研究有限群的描述复杂度和群同构问题。
方法
为有限群定义三种Weisfeiler-Leman算法,并用计数逻辑和双射石子博弈分别刻画它们的表达能力。
评估
通过理论证明比较三个版本的表达能力,建立其线性关系,并给出相应的逻辑与博弈刻画。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5525,
  title = {On the Weisfeiler-Leman Dimension of Finite Groups},
  author = {Jendrik Brachter and Pascal Schweitzer},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394786}
}