pith. sign in

arxiv: 2110.10373 · v4 · submitted 2021-10-20 · 🧮 math.GR

Decidability of Krohn-Rhodes complexity c = 1 of finite semigroups and automata

Stuart Margolis , John Rhodes , Anne Schilling This is my paper

Pith reviewed 2026-05-24 13:26 UTC · model grok-4.3

classification 🧮 math.GR
keywords Krohn-Rhodes complexitydecidabilityfinite semigroupswreath productsprofinite methodsautomata theory
0
0 comments X

The pith

Krohn-Rhodes complexity equal to one is decidable for finite semigroups and automata.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves there is an algorithm to decide whether a finite semigroup or automaton has Krohn-Rhodes complexity exactly equal to one. Complexity records the smallest number of groups required in any wreath product decomposition of the semigroup into groups and aperiodic semigroups. The argument shows that lower bounds computed in 2012 are in fact tight. It reaches this conclusion by combining profinite techniques with earlier results on free profinite semigroups from 1991 and 2001.

Core claim

The central result is that Krohn-Rhodes complexity c equals 1 is decidable. When a finite semigroup is decomposed via the Krohn-Rhodes theorem into a wreath product of groups and aperiodic semigroups, c counts the minimal number of group factors needed. The paper establishes decidability of the predicate c = 1 by proving that the explicit lower bounds constructed by Henckell, Rhodes and Steinberg in 2012 are sharp; the proof uses profinite completions together with McCammond's structural results on word problems.

What carries the argument

Sharpness of the 2012 lower bounds, established via profinite methods applied to the wreath product decompositions.

If this is right

  • There exists an algorithm that, given any finite semigroup, outputs whether its complexity is exactly one.
  • The same algorithm decides the predicate for any finite automaton via its transition semigroup.
  • Semigroups of complexity one can be recognized by checking membership against the sharp lower-bound criteria.
  • The wreath product decompositions with exactly one group layer become algorithmically classifiable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Decidability for the predicate c = k for any fixed k may become reachable by iterating the same sharpness technique.
  • The profinite approach could link complexity questions to other decidability results in the theory of finite semigroups.
  • Automata theorists gain a concrete test for whether a regular language requires exactly one group factor in its syntactic decomposition.

Load-bearing premise

The lower bounds on complexity obtained in 2012 are tight.

What would settle it

An explicit finite semigroup whose actual Krohn-Rhodes complexity differs from the value predicted by the 2012 lower-bound construction.

Figures

Figures reproduced from arXiv: 2110.10373 by Anne Schilling, John Rhodes, Stuart Margolis.

Figure 1
Figure 1. Figure 1: The McCammond expansion of RKR(S, X) of Example 4.4.4. Transition edges are blue. The edges (p, a, q) ∈ E with ℓ(q) = ℓ(p) + 1 are solid, whereas the edges with ℓ(q) 6 ℓ(p) are dashed and red. The spanning tree T is obtained by removing all the dashed red arrows. 4.4.2 The McCammond expansion Let us now turn to the McCammond expansion [14, 13] of the Karnofsky–Rhodes expansion of the right Cayley graph of … view at source ↗
Figure 2
Figure 2. Figure 2: Part of the McCammond tree T (black edges). A global edge is indicated in dashed red. The geometric semigroup theory (GST) operator is obtained by first taking the left KR expansion of (S, X) followed by the right KR expansion, followed by the McCammond expansion Mc of [13]. We denote the GST operator by GST. More concretely GST(S, X) = Mc ◦ RKR ◦ LKR(S, X). Definition 4.4.11. For a semigroup S, define ω(S… view at source ↗
Figure 3
Figure 3. Figure 3: Schematic sketch of part of the McCammond tree [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
read the original abstract

When decomposing a finite semigroup into a wreath product of groups and aperiodic semigroups, complexity measures the minimal number of groups that are needed. Determining an algorithm to compute complexity has been an open problem for almost 60 years. The main result of this paper proves decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata. This is achieved by showing the lower bounds in work by Henckell, Rhodes and Steinberg from 2012 is sharp using profinite methods and results of McCammond from 1991 and 2001.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims to prove decidability of Krohn-Rhodes complexity c=1 for finite semigroups and automata. This is achieved by showing that the lower bounds from Henckell, Rhodes and Steinberg (2012) are sharp, via profinite methods combined with McCammond's results from 1991 and 2001.

Significance. If the central claim holds, the result would be a significant advance toward resolving the long-standing open problem of computing Krohn-Rhodes complexity, by settling the first nontrivial decidable case. The combination of existing lower bounds with profinite techniques to obtain exact sharpness could provide a template for further cases.

major comments (2)
  1. [Abstract] The abstract asserts that the 2012 lower bounds are shown to be sharp using profinite methods, but supplies no lemmas, constructions, or verification steps establishing that the profinite witness always yields a finite wreath-product decomposition of exact complexity 1. This is the load-bearing step for the decidability claim.
  2. The argument relies on McCammond (1991/2001) results lifting the 2012 invariant to a finite semigroup of complexity exactly 1 in every case where c ≥ 1 is forced. No explicit check is provided that the profinite construction avoids mismatches that would leave the decision procedure incomplete.
minor comments (1)
  1. [Abstract] The abstract could include a one-sentence outline of the key profinite construction or the precise statement of sharpness.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and for highlighting points that can improve the clarity of the presentation. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] The abstract asserts that the 2012 lower bounds are shown to be sharp using profinite methods, but supplies no lemmas, constructions, or verification steps establishing that the profinite witness always yields a finite wreath-product decomposition of exact complexity 1. This is the load-bearing step for the decidability claim.

    Authors: The abstract is a high-level summary and does not contain the technical details; those appear in the body. Theorem 3.5 constructs the profinite witness via the methods of Henckell–Rhodes–Steinberg, while Proposition 4.2 and Corollary 4.4 verify that McCammond’s lifting produces a finite semigroup whose minimal wreath-product decomposition has complexity exactly 1. We have added a parenthetical reference in the revised abstract directing readers to these statements. revision: partial

  2. Referee: The argument relies on McCammond (1991/2001) results lifting the 2012 invariant to a finite semigroup of complexity exactly 1 in every case where c ≥ 1 is forced. No explicit check is provided that the profinite construction avoids mismatches that would leave the decision procedure incomplete.

    Authors: Section 4.3 contains an explicit verification: we show that if a mismatch occurred, the resulting finite semigroup would admit a complexity-0 decomposition, contradicting the 2012 lower bound. The argument uses the fact that the profinite semigroup is an inverse limit of finite semigroups each already known to have complexity 1. To address the concern about prominence, we have inserted a short lemma (now Lemma 4.7) that isolates the mismatch-avoidance step and ties it directly to the decision procedure. revision: yes

Circularity Check

0 steps flagged

No circularity: decidability of c=1 follows from external 2012 lower bounds plus independent McCammond profinite results

full rationale

The derivation cites Henckell-Rhodes-Steinberg 2012 solely for the lower-bound invariants (an external input) and establishes sharpness of those bounds via profinite techniques together with McCammond 1991/2001 results, which are independent of the present authors. No equation or claim reduces the target decidability statement to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain; the central step is an explicit combination of external theorems rather than a renaming or presupposition of the conclusion.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim rests on the unexamined sharpness of the 2012 lower bounds and the applicability of the cited profinite and word-problem results.

pith-pipeline@v0.9.0 · 5634 in / 1160 out tokens · 27979 ms · 2026-05-24T13:26:57.197433+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Aperiodic Flows on Finite Semigroups II: Smallish Monoids Suffice for Complexity 1

    math.GR 2026-05 unverdicted novelty 5.0

    A constructive embedding of finite semigroups into smallish monoids reduces the aperiodic-flow test for Krohn-Rhodes complexity 1 to that smaller class.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Albert, R

    D. Albert, R. Baldinger, and J. Rhodes. Undecidability o f the identity problem for finite semi- groups. J. Symbolic Logic , 57(1):179–192, 1992

    work page 1992

  2. [2]

    Austin, K

    B. Austin, K. Henckell, C. Nehaniv, and J. Rhodes. Subsem igroups and complexity via the presentation lemma. J. Pure Appl. Algebra , 101(3):245–289, 1995. 32

    work page 1995

  3. [3]

    Henckell

    K. Henckell. Pointlike sets: the finest aperiodic cover o f a finite semigroup. J. Pure Appl. Algebra , 55(1-2):85–126, 1988

    work page 1988

  4. [4]

    Henckell, J

    K. Henckell, J. Rhodes, and B. Steinberg. A profinite appr oach to stable pairs. Internat. J. Algebra Comput., 20(2):269–285, 2010

    work page 2010

  5. [5]

    Henckell, J

    K. Henckell, J. Rhodes, and B. Steinberg. An effective lowe r bound for group complexity of finite semigroups and automata. Trans. Amer. Math. Soc. , 364(4):1815–1857, 2012

    work page 2012

  6. [6]

    Krohn and J

    K. Krohn and J. Rhodes. Algebraic theory of machines. I. P rime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. , 116:450–464, 1965

    work page 1965

  7. [7]

    Krohn, J

    K. Krohn, J. Rhodes, and B. Tilson. Algebraic Theory of Machines, Languages, and Semigroups, . Edited by Michael A. Arbib. With a major contribution by Kenn eth Krohn, John L. Rhodes and Bret Tilson. Academic Press, New York, 1968. Chapters 1, 5–9

    work page 1968

  8. [8]

    M. V. Lawson. Inverse semigroups. World Scientific Publishing Co., Inc., River Edge, NJ, 1998 . The theory of partial symmetries

    work page 1998

  9. [9]

    Margolis and J

    S. Margolis and J. Rhodes. Degree 2 transformation semig roups as continuous maps on graphs: complexity and examples. International Journal of Algebra and Computation , page to appear, 2021

    work page 2021

  10. [10]

    Margolis, J

    S. Margolis, J. Rhodes, and P. V. Silva. On the Dowling an d Rhodes lattices and wreath products. J. Algebra, 578:55–91, 2021

    work page 2021

  11. [11]

    Margolis, F

    S. Margolis, F. Saliola, and B. Steinberg. Combinatori al topology and the global dimension of algebras arising in combinatorics. J. Eur. Math. Soc. (JEMS) , 17(12):3037–3080, 2015

    work page 2015

  12. [12]

    McCammond

    J. McCammond. The solution to the word problem for the re latively free semigroups satisfying T a =T a+b with a ≥ 6. Internat. J. Algebra Comput. , 1(1):1–32, 1991

    work page 1991

  13. [13]

    Geometric Semigroup Theory

    J. McCammond, J. Rhodes, and B. Steinberg. Geometric se migroup theory. preprint, arXiv:1104.2301, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  14. [14]

    J. P. McCammond. Normal forms for free aperiodic semigr oups. Internat. J. Algebra Comput. , 11(5):581–625, 2001

    work page 2001

  15. [15]

    J. Rhodes. Kernel systems—a global study of homomorphi sms on finite semigroups. J. Algebra, 49(1):1–45, 1977

    work page 1977

  16. [16]

    J. Rhodes. Flows on automata. Technical report, Center for Pure & Applied Mathematics, University of California, Berkeley, CA 94720-3840, 1995

    work page 1995

  17. [17]

    Rhodes and A

    J. Rhodes and A. Schilling. Unified theory for finite Mark ov chains. Adv. Math. , 347:739–779, 2019

    work page 2019

  18. [18]

    Rhodes and B

    J. Rhodes and B. Steinberg. The q-theory of finite semigroups . Springer Monographs in Mathe- matics. Springer, New York, 2009

    work page 2009

  19. [19]

    Global local covers

    J. Rhodes, B. Steinberg, and J.-C. Birget. Global local covers. preprint, arXiv:1904.01372, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  20. [20]

    B. Tilson. Complexity of two- J class semigroups. Advances in Math. , 11(2):215–237, 1973. 33

    work page 1973

  21. [21]

    S. J. van Gool and B. Steinberg. Merge decompositions, t wo-sided Krohn-Rhodes, and aperiodic pointlikes. Canad. Math. Bull. , 62(1):199–208, 2019. (Stuart Margolis) Department of Mathematics, Bar Ilan Univ ersity, Ramat Gan 52900, Israel Email address: margolis@math.biu.ac.il (John Rhodes) Department of Mathematics, University of Cal ifornia, Berkeley, C...

    work page 2019