DROPS

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.MFCS.2024.71

Streaming in Graph Products

Authors: Markus Lohrey and Julio Xochitemol

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

We investigate the streaming space complexity of word problems for groups. Using so-called distinguishers, we prove a transfer theorem for graph products of groups. Moreover, we use distinguishers to obtain a logspace streaming algorithm for the membership problem in a finitely generated subgroup of a free group.

Cite as

Markus Lohrey and Julio Xochitemol. Streaming in Graph Products. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2024.71,
  author =	{Lohrey, Markus and Xochitemol, Julio},
  title =	{{Streaming in Graph Products}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{71:1--71:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.71},
  URN =		{urn:nbn:de:0030-drops-206271},
  doi =		{10.4230/LIPIcs.MFCS.2024.71},
  annote =	{Keywords: word problems for groups, streaming algorithms, graph products}
}

Search Results

Documents authored by Xochitemol, Julio

Distinguishing Elements in Semigroups

Abstract

Cite as

Streaming in Graph Products

Abstract

Cite as

Thanks for your feedback!

Could not send message