Subsemigroups and complexity via the Presentation Lemma

Beverly Austin, Karsten Henckell, Chrystopher Nehaniv, John Rhodes

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


The Krohn-Rhodes Theorem shows that any finite semigroup S can be built by cascading (via wreath product) the simple groups which divide S with trivial combinatorial "flip-flops". The complexity of a semigroup is essentially the length of a shortest such decomposition (counting alternations of groups). It is an important open question whether complexity of finite semigroups is decidable. In this paper, after reviewing some local and semi-local structure theory of finite semigroups which distills the insights of the Rees-Sushkevych Theorem, we prove the Presentation Lemma. The Presentation Lemma gives a characterization of complexity n in terms of semi-local mapping properties and relational morphisms to transformation semigroups of lower complexity. Thus the Presentation Lemma is a bridge linking the local Green-Rees-Sushkevych coordinate picture of a single J-class to the global properties of the semigroup. As an application, we derive sufficient conditions for complexity of a finite semigroup S to be effectively computable by examining its local subsemigroups (those of the form eSe where e2 = e GS). The Almost-Disjoint Semigroup Theorem, proved via the Presentation Lemma, and its corollaries enable one to determine the complexity of a large class of examples. A simple application of the Presentation Lemma also allows us to recover Tilson's theorem that the complexity of semigroups with two or fewer non-zero J-classes is effectively computable. Conditions, in terms of subsemigroups, guaranteeing parallelizability of computation are also obtained. A counterexample constructed using deep insights obtained from the Presentation Lemma shows that complexity need not be locally determined. Also a reformulation of the Presentation Lemma in the language of categories and functors is given. The Presentation Lemma will be used in future papers as a tool to attack the decidability of complexity and for constructing pseudo-varieties of semigroups with undecidable membership problem from those with decidable membership problem using the pseudo-variety operations, *, *r, and m.

Original languageEnglish
Pages (from-to)245-289
Number of pages45
JournalJournal of Pure and Applied Algebra
Issue number3
Publication statusPublished - 23 Jun 1995
Externally publishedYes


  • Cascade synthesis of transformation semigroups
  • Complexity
  • Decidability
  • Finite semigroups
  • Krohn-Rhodes Theorem
  • Rees-Sushkevych
  • Subsemigroups
  • Wreath products


Dive into the research topics of 'Subsemigroups and complexity via the Presentation Lemma'. Together they form a unique fingerprint.

Cite this