DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.80

Efficient Compression in Semigroups

Authors: Alexander Thumm and Armin Weiß

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Straight-line programs are a central tool in several areas of computer science, including data compression, algebraic complexity theory, and the algorithmic solution of algebraic equations. In the algebraic setting, where straight-line programs can be interpreted as circuits over algebraic structures such as semigroups or groups, they have led to deep insights in computational complexity. A key result by Babai and Szemerédi (1984) showed that finite groups afford efficient compression via straight-line programs, enabling the design of a black-box computation model for groups. Building on their result, Fleischer (2019) placed the Cayley table membership problem for certain classes (pseudovarieties) of finite semigroups in NPOLYLOGTIME, and in some cases even in FOLL. He also provided a complete classification of pseudovarieties of finite monoids affording efficient compression. In this work, we complete this classification program initiated by Fleischer, characterizing precisely those pseudovarieties of finite semigroups that afford efficient compression via straight-line programs. Along the way, we also improve several known bounds on the length and width of straight-line programs over semigroups, monoids, and groups. These results lead to new upper bounds for the membership problem in the Cayley table model: for all pseudovarieties that afford efficient compression and do not contain any nonsolvable group, we obtain FOLL algorithms. In particular, we resolve a conjecture of Barrington, Kadau, Lange, and McKenzie (2001), showing that the membership problem for all solvable groups is in FOLL.

Cite as

Alexander Thumm and Armin Weiß. Efficient Compression in Semigroups. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{thumm_et_al:LIPIcs.STACS.2026.80,
  author =	{Thumm, Alexander and Wei{\ss}, Armin},
  title =	{{Efficient Compression in Semigroups}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{80:1--80:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.80},
  URN =		{urn:nbn:de:0030-drops-255694},
  doi =		{10.4230/LIPIcs.STACS.2026.80},
  annote =	{Keywords: Semigroups, straight-line programs, compression, membership problem}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2025.156

Membership and Conjugacy in Inverse Semigroups

Authors: Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete in the partial bijection model by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general 𝖫-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and 𝖫-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semigroup and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.

Cite as

Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß. Membership and Conjugacy in Inverse Semigroups. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 156:1-156:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fleischer_et_al:LIPIcs.ICALP.2025.156,
  author =	{Fleischer, Lukas and Stober, Florian and Thumm, Alexander and Wei{\ss}, Armin},
  title =	{{Membership and Conjugacy in Inverse Semigroups}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{156:1--156:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.156},
  URN =		{urn:nbn:de:0030-drops-235330},
  doi =		{10.4230/LIPIcs.ICALP.2025.156},
  annote =	{Keywords: inverse semigroups, membership, conjugacy, finite automata}
}

Search Results

Documents authored by Thumm, Alexander

Efficient Compression in Semigroups

Abstract

Cite as

Membership and Conjugacy in Inverse Semigroups

Abstract

Cite as

Thanks for your feedback!

Could not send message