pith. sign in

arxiv: 2202.04060 · v5 · submitted 2022-02-08 · 🧮 math.GR · cs.DS

Streaming algorithms for groups and semigroups

Markus Lohrey , Lukas L\"uck , Alexander Thumm , Julio Xochitemol This is my paper

Pith reviewed 2026-05-24 12:26 UTC · model grok-4.3

classification 🧮 math.GR cs.DS
keywords streaming algorithmsword problemgroupssemigroupsdistinguisherslogarithmic spacelower boundssubgroup membership
0
0 comments X

The pith

Randomized streaming distinguishers decide word equality in linear semigroups and product constructions using logarithmic space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the concept of a distinguisher, a randomized streaming algorithm that checks whether two words represent the same element in a group or semigroup by processing them in parallel. It constructs such distinguishers that use only logarithmic space for finitely generated linear semigroups and for semigroups built from graph products, wreath products, and semilattice decompositions. For commutative semigroups and cancellative nilpotent ones, the space can be reduced to doubly logarithmic. These positive results are paired with lower bounds proving that some structures, including free inverse monoids and Thompson's group F, require linear space. The approach also extends to subgroup membership testing in free groups.

Core claim

We construct such distinguishers with low error probability using logarithmic, and in some cases doubly logarithmic, space. For example, our results apply to linear semigroups and to semigroups obtained under suitable restrictions via standard constructions such as graph products, wreath products, and semilattice decompositions. In case of commutative semigroups and cancellative nilpotent semigroups, we achieve space complexity O(log log n). We complement these upper bounds with lower bounds demonstrating that certain well-known semigroups do not admit sublinear-space distinguishers. This includes, for example, free inverse monoids of rank at least two and Thompson's group F.

What carries the argument

A distinguisher is 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.

Load-bearing premise

The target semigroups must be finitely generated and satisfy the structural restrictions such as linearity or being obtainable via the listed standard constructions.

What would settle it

A counterexample would be a finitely generated linear semigroup for which no logarithmic-space distinguisher exists, or a proof that Thompson's group F admits a sublinear-space distinguisher.

read the original abstract

We investigate deterministic and randomized streaming algorithms for word problems in finitely generated groups and semigroups. For this we introduce 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 low error probability using logarithmic, and in some cases doubly logarithmic, space. For example, our results apply to linear semigroups and to semigroups obtained (under suitable restrictions) via standard constructions such as graph products, wreath products, and semilattice decompositions. In case of commutative semigroups and cancellative nilpotent semigroups, we achieve space complexity $\mathcal{O}(\log \log n)$. We complement these upper bounds with lower bounds demonstrating that certain well-known semigroups do not admit sublinear-space distinguishers. This includes, for example, free inverse monoids of rank at least two and Thompson's group $F$. Finally, we study randomized streaming algorithms for subgroup membership problems in free groups and their direct products.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces 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 semigroup or group element and distinct states otherwise. It constructs such distinguishers using O(log n) or O(log log n) space for finitely generated linear semigroups and for semigroups obtained via graph products, wreath products, and semilattice decompositions (under suitable restrictions), as well as for commutative semigroups and cancellative nilpotent semigroups. The paper complements these upper bounds with lower bounds showing that free inverse monoids of rank at least two and Thompson's group F admit no sublinear-space distinguishers, and studies randomized streaming algorithms for subgroup membership in free groups and their direct products.

Significance. If the constructions and lower-bound arguments hold, the work advances the application of streaming algorithms to algebraic decision problems by supplying explicit low-space distinguishers for several natural classes of semigroups together with matching impossibility results for well-studied examples. The introduction of distinguishers supplies a clean framework for analyzing equality testing under the streaming model. The paper supplies explicit algorithmic constructions for the upper bounds and concrete lower-bound arguments for the impossibility results.

minor comments (2)
  1. [Abstract] The abstract refers to “suitable restrictions” on the standard constructions (graph products, wreath products, semilattice decompositions) without enumerating them; the introduction should list the precise hypotheses under which the logarithmic-space distinguishers are obtained.
  2. [Introduction] Notation for the input length n and for the error probability is used without an explicit global definition; a short preliminary section collecting all parameters would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces the distinguisher concept and constructs explicit streaming algorithms achieving logarithmic or doubly-logarithmic space for word problems in finitely generated linear semigroups and those closed under graph/wreath/semilattice products, plus matching lower bounds for free inverse monoids and Thompson's group F. These are algorithmic upper/lower bounds derived from structural properties of the semigroups rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The derivation chain is self-contained against external benchmarks in streaming complexity and semigroup theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from group and semigroup theory without introducing fitted numerical parameters or new postulated entities.

axioms (1)
  • standard math Finitely generated groups and semigroups are equipped with the standard word problem and the usual notions of generation and relations.
    Basic setup invoked throughout the abstract for defining the word problem and the distinguisher.

pith-pipeline@v0.9.0 · 5727 in / 1265 out tokens · 39043 ms · 2026-05-24T12:26:40.393662+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    The space com plexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space com plexity of approximating the frequency moments. Journal of Computer and System Sciences , 58(1):137–147, 1999

    work page 1999

  2. [2]

    Anissimov and Franz D

    Anatolij W. Anissimov and Franz D. Seifert. Zur algebrai schen Charakteristik der durch kontext-freie Sprachen definierten Gruppen. Elektron. Informationsverarbeit. Kybernetik , 11(10–12):695–702, 1975

    work page 1975

  3. [3]

    New results on noncommutative and commutative polynomial identity tes ting

    Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Sri nivasan. New results on noncommutative and commutative polynomial identity tes ting. Computational Complexity, 19(4):521–558, 2010. URL: https://doi.org/10.1007/s00037-010-0299-8 , doi:10.1007/s00037-010-0299-8

    work page doi:10.1007/s00037-010-0299-8 2010

  4. [4]

    Streaming algo- rithms for language recognition problems

    Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and G irish Varma. Streaming algo- rithms for language recognition problems. Theoretical Computer Science , 494:13–23, 2013

    work page 2013

  5. [5]

    The growth of grigorchuk’s torsion g roup

    Laurent Bartholdi. The growth of grigorchuk’s torsion g roup. International Mathematics Research Notices, 20:1049–1054, 1998. URL: https://doi.org/10.1155/S1073792898000622

    work page doi:10.1155/s1073792898000622 1998

  6. [6]

    Lower bounds on the growth of a group a cting on the binary rooted tree

    Laurent Bartholdi. Lower bounds on the growth of a group a cting on the binary rooted tree. International Journal of Algebra and Computation , 11(01):73–88, 2001. URL: https://doi.org/10.1142/S0218196701000395, doi:10.1142/S0218196701000395

    work page doi:10.1142/s0218196701000395 2001

  7. [7]

    Property tes ting of regular languages with applications to streaming property testing of visibly push down languages

    Gabriel Bathie and Tatiana Starikovskaya. Property tes ting of regular languages with applications to streaming property testing of visibly push down languages. In Proceed- ings of the 48th International Colloquium on Automata, Lang uages, and Programming, ICALP 2021 , volume 198 of LIPIcs, pages 119:1–119:17. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Inf...

    work page doi:10.4230/lipics.icalp.2021.119 2021

  8. [8]

    Cannon, William J

    John W. Cannon, William J. Floyd, and W alter R. Parry. Int roductory notes on Richard Thompson’s groups. L’Enseignement Math´ ematique, 42(3):215–256, 1996

    work page 1996

  9. [9]

    R andomness-optimal unique element isolation with applications to perfect matching and relate d problems

    Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. R andomness-optimal unique element isolation with applications to perfect matching and relate d problems. SIAM Journal on Com- puting, 24(5):1036–1050, 1995

    work page 1995

  10. [10]

    Topics in Geometric Group Theory

    Pierre de la Harpe. Topics in Geometric Group Theory . University of Chicago Press, 2000

    work page 2000

  11. [11]

    ¨Uber unendliche diskontinuierliche Gruppen

    Max Dehn. ¨Uber unendliche diskontinuierliche Gruppen. Mathematische Annalen , 71:116– 144, 1911. In German

    work page 1911

  12. [12]

    Streaming property testing of visibly pushdown languages

    Nathana¨ el Fran¸ cois, Fr´ ed´ eric Magniez, Michel de Rougemont, and Olivier Serre. Streaming property testing of visibly pushdown languages. In Proceedings of the 24th Annual Euro- pean Symposium on Algorithms, ESA 2016 , volume 57 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2016

    work page 2016

  13. [13]

    Ian Glaister and Jeffrey O. Shallit. Automaticity III: p olynomial automaticity and context- free languages. Computational Complexity , 7(4):371–387, 1998. doi:10.1007/s000370050016

    work page doi:10.1007/s000370050016 1998

  14. [14]

    Interleave d group products

    William Timothy Gowers and Emanuele Viola. Interleave d group products. SIAM Jour- nal on Computing , 48(2):554–580, 2019. URL: https://doi.org/10.1137/17M1126783, doi:10.1137/17M1126783

    work page doi:10.1137/17m1126783 2019

  15. [15]

    Grigorchuk

    Rostislav I. Grigorchuk. Burnside’s problem on period ic groups. Functional Analysis and Its Applications, 14:41–43, 1980. URL: https://doi.org/10.1007/BF01078416

    work page doi:10.1007/bf01078416 1980

  16. [16]

    Grigorchuk

    Rostislav I. Grigorchuk. On the gap conjecture concern ing group growth. Bulletin of Mathe- matical Sciences, 4(1):113–128, 2014. URL: https://doi.org/10.1007/s13373-012-0029-4

    work page doi:10.1007/s13373-012-0029-4 2014

  17. [17]

    Groups of polynomial growth and expand ing maps

    Mikhail Gromov. Groups of polynomial growth and expand ing maps. Publica- tions Math´ ematiques de L’Institut des Hautes Scientifique s, 53:53–78, 1981. URL: https://doi.org/10.1007/BF02698687

    work page doi:10.1007/bf02698687 1981

  18. [18]

    Guba and Mark V

    Victor S. Guba and Mark V. Sapir. On subgroups of the R. Th ompson group F and other diagram groups. Matematicheskii Sbornik , 190(8):3–60, 1999. URL: https://doi.org/10.1070/SM1999v190n08ABEH000419. 34 M. LOHREY, M. L ¨UCK, AND J. XOCHITEMOL

    work page doi:10.1070/sm1999v190n08abeh000419 1999

  19. [19]

    Holt, Sarah Rees, and Claas E

    Derek F. Holt, Sarah Rees, and Claas E. R¨ over. Groups, Languages and Automata , volume 88 of London Mathematical Society Student Texts . Cambridge University Press, 2017

    work page 2017

  20. [20]

    Kargapolov and Yurii I

    Mikhail I. Kargapolov and Yurii I. Merzljakov. Fundamentals of the Theory of Groups , vol- ume 62 of Graduate Texts in Mathematics . Springer-Verlag, New York, 1979

    work page 1979

  21. [21]

    Richard M. Karp. Some bounds on the storage requirement s of sequential machines and turing machines. Journal of the ACM , 14(3):478–489, 1967

    work page 1967

  22. [22]

    Evaluation of circuits over nilpotent and polycyclic groups

    Daniel K¨ onig and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459–1492, 2018

    work page 2018

  23. [23]

    Parallel identity tes ting for skew circuits with big powers and applications

    Daniel K¨ onig and Markus Lohrey. Parallel identity tes ting for skew circuits with big powers and applications. International Journal of Algebra and Computation , 28(6):979–1004, 2018. URL: https://doi.org/10.1142/S0218196718500431, doi:10.1142/S0218196718500431

    work page doi:10.1142/s0218196718500431 2018

  24. [24]

    Communication complexity

    Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997

    work page 1997

  25. [25]

    The co-word probl em for the Higman-Thompson group is context-free

    J¨ org Lehnert and Pascal Schweitzer. The co-word probl em for the Higman-Thompson group is context-free. Bulletin of the London Mathematical Society , 39(2):235–241, 02 2007. URL: https://doi.org/10.1112/blms/bdl043

    work page doi:10.1112/blms/bdl043 2007

  26. [26]

    Lipton and Yechezkel Zalcstein

    Richard J. Lipton and Yechezkel Zalcstein. W ord proble ms solvable in logspace. Journal of the Association for Computing Machinery , 24(3):522–526, 1977

    work page 1977

  27. [27]

    Decidability and complexity in automat ic monoids

    Markus Lohrey. Decidability and complexity in automat ic monoids. International Journal of Foundations of Computer Science , 16(4):707–722, 2005

    work page 2005

  28. [28]

    The Compressed Word Problem for Groups

    Markus Lohrey. The Compressed Word Problem for Groups . SpringerBriefs in Mathematics. Springer, 2014

    work page 2014

  29. [29]

    Recognizing well-parenthesized ex- pressions in the streaming model

    Fr´ ed´ eric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized ex- pressions in the streaming model. SIAM Journal on Computing , 43(6):1880–1905, 2014

    work page 1905

  30. [30]

    On a theorem of Marshall Hall

    Wilhelm Magnus. On a theorem of Marshall Hall. Annals of Mathematics. Second Series , 40:764–768, 1939

    work page 1939

  31. [31]

    How Groups Grow

    Avinoam Mann. How Groups Grow. London Mathematical Society Lecture Note Series. Cam- bridge University Press, 2011. doi:10.1017/CBO9781139095129

    work page doi:10.1017/cbo9781139095129 2011

  32. [32]

    Decision problems for groups – sur vey and reflections

    Charles F Miller III. Decision problems for groups – sur vey and reflections. In G. Baumslag and Charles F Miller III, editors, Algorithms and classification in combinatorial group theor y, pages 1–59. Springer, 1992

    work page 1992

  33. [33]

    Growth of finitely generated solvable grou ps

    John Milnor. Growth of finitely generated solvable grou ps. Journal of Differen- tial Geometry , 2(4):447 – 449, 1968. URL: https://doi.org/10.4310/jdg/1214428659, doi:10.4310/jdg/1214428659

    work page doi:10.4310/jdg/1214428659 1968

  34. [34]

    Muller and Paul E

    David E. Muller and Paul E. Schupp. Groups, the theory of ends, and context-free languages. Journal of Computer and System Sciences , 26:295–310, 1983

    work page 1983

  35. [35]

    The word and geodesic problems in free solvable groups

    Alexei Myasnikov, Vitaly Roman’kov, Alexander Ushako v, and AnatolyVershik. The word and geodesic problems in free solvable groups. Transactions of the American Mathematical Society, 362(9):4655–4682, 2010. URL: https://doi.org/10.1090/S0002-9947-10-04959-7

    work page doi:10.1090/s0002-9947-10-04959-7 2010

  36. [36]

    Introduction to Probabilistic Automata

    Azaria Paz. Introduction to Probabilistic Automata . Academic Press, 1971

    work page 1971

  37. [37]

    Michael O. Rabin. Probabilistic automata. Information and Control , 6(3):230–245, 1963

    work page 1963

  38. [38]

    Robinson

    Derek J.S. Robinson. A Course in the Theory of Groups, 2nd edition . Pearson international edition. Springer, 1996

    work page 1996

  39. [39]

    Automaticity I: pro perties of a measure of descriptional complexity

    Jeffrey Shallit and Yuri Breitbart. Automaticity I: pro perties of a measure of descriptional complexity. Journal of Computer and System Sciences , 53(1):10–25, 1996

    work page 1996

  40. [40]

    W ord problems for groups and contex tfree recognition

    Hans-Ulrich Simon. W ord problems for groups and contex tfree recognition. In Proceedings of Fundamentals of Computation Theory, FCT 1979 , pages 417–422. Akademie-Verlag, 1979

    work page 1979

  41. [41]

    Free subgroups in linear groups

    Jacques Tits. Free subgroups in linear groups. Journal of Algebra , 20:250–270, 1972

    work page 1972

  42. [42]

    Algorithmic theory of free solvabl e groups: Ran- domized computations

    Alexander Ushakov. Algorithmic theory of free solvabl e groups: Ran- domized computations. Journal of Algebra , 407:178–200, 2014. URL: https://www.sciencedirect.com/science/article/pii/S0021869314001173 , doi:https://doi.org/10.1016/j.jalgebra.2014.02.014

    work page doi:10.1016/j.jalgebra.2014.02.014 2014

  43. [43]

    The parallel complexity of some constru ctions in combinatorial group theory

    Stephan W aack. The parallel complexity of some constru ctions in combinatorial group theory. Journal of Information Processing and Cybernetics, EIK , 26:265–281, 1990

    work page 1990

  44. [44]

    Bertram A. F. W ehrfritz. On finitely generated soluble l inear groups. Mathematische Zeitschrift, 170:155–167, 1980. STREAMING WORD PROBLEMS 35

    work page 1980

  45. [45]

    A logspace solution to the word and conjugac y problem of generalized Baumslag- Solitar groups

    Armin W eiß. A logspace solution to the word and conjugac y problem of generalized Baumslag- Solitar groups. In Algebra and Computer Science , volume 677 of Contemporary Mathematics. American Mathematical Society, 2016

    work page 2016

  46. [46]

    Joseph A. W olf. Growth of finitely generated solvable gr oups and curvature of Rie- mannian manifolds. Journal of Differential Geometry , 2(4):421 – 446, 1968. URL: https://doi.org/10.4310/jdg/1214428658, doi:10.4310/jdg/1214428658. Email address : lohrey@eti.uni-siegen.de Email address : lukas.lueck@student.uni-siegen.de Email address : Julio.JXochitemol@...

    work page doi:10.4310/jdg/1214428658 1968