Search Results

Documents authored by Thumm, Alexander

Document
DOI: 10.4230/LIPIcs.MFCS.2026.30
Distinguishing Elements in Semigroups

Authors: Markus Lohrey, Alexander Thumm, and Julio Xochitemol

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
We investigate randomized streaming algorithms for word problems in finitely generated semigroups. For this we use the notion of a distinguisher: a randomized streaming algorithm that processes two input words in parallel and, with high probability, reaches identical memory states if the words represent the same element, and distinct states otherwise. We construct such distinguishers with space complexity 𝒪(log log n) for finitely generated commutative semigroups. Moreover, we show a transfer result for semilattice decompositions that allows to construct a distinguisher for a finitely generated semigroup from distinguishers for the components of its semilattice decomposition. Thereby the space complexity and the error probability of the distinguisher increase only by a constant factor. We use this result to obtain distinguishers with space complexity 𝒪(log n) for free Clifford semigroups and distinguishers with space complexity 𝒪(log log n) for finitely generated regular nilpotent semigroups. We complement these upper bounds with lower bounds demonstrating that certain well-known semigroups do not admit distinguishers with sublinear space complexity. This includes, for example, free inverse monoids of rank at least two and polycyclic semigroups.
Cite as

Markus Lohrey, Alexander Thumm, and Julio Xochitemol. Distinguishing Elements in Semigroups. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2026.30,
  author =	{Lohrey, Markus and Thumm, Alexander and Xochitemol, Julio},
  title =	{{Distinguishing Elements in Semigroups}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.30},
  URN =		{urn:nbn:de:0030-drops-274114},
  doi =		{10.4230/LIPIcs.MFCS.2026.30},
  annote =	{Keywords: Streaming algorithms, semigroups, word problem, space complexity}
}
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}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact