2026-08-21T18:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27411 2026-08-21T14:42:38Z ddc:004 open_access

Distinguishing Elements in Semigroups Lohrey, Markus Thumm, Alexander Xochitemol, Julio Streaming algorithms semigroups word problem space complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Alexander Thumm and Julio Xochitemol 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.30 urn:nbn:de:0030-drops-274114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode