Metraipolis › archive › dc_35e14870cc67
Subgroup Accessibility in Group Order Logic — arXiv:2609.00499
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.00499
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T07:07:01.141Z
- SHA-256 of the archived text
8f90e90d219ddcf7241ced72f9ad93cb2ab23d2345cbfb651575de84eef6ea5c- Stable URL of this page
https://metraipolis.com/documento/dc_35e14870cc67
How to cite
Subgroup Accessibility in Group Order Logic — arXiv:2609.00499 — arXiv (en), https://arxiv.org/abs/2609.00499 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_35e14870cc67 (Metraipolis archive dc_35e14870cc67, sha256 8f90e90d219ddcf7241ced72f9ad93cb2ab23d2345cbfb651575de84eef6ea5c)
BibTeX
@misc{dc35e14870cc67,
title = {Subgroup Accessibility in Group Order Logic — arXiv:2609.00499},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.00499},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_35e14870cc67; sha256 8f90e90d219ddcf7241ced72f9ad93cb2ab23d2345cbfb651575de84eef6ea5c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.00499. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs--a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours--despite being unable to canonise such graphs. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in math.LO). Categorie arXiv: Logic in Computer Science (cs.LO) ; Computational Complexity (cs.CC); Logic (math.LO). Pagina del lavoro: https://arxiv.org/abs/2609.00499 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T06:57:22.007Z dalla pagina https://arxiv.org/catchup/math.LO/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).