Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2202.04060 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913054036328448 |
|---|---|
| author | Lohrey, Markus Lück, Lukas Thumm, Alexander Xochitemol, Julio |
| author_facet | Lohrey, Markus Lück, Lukas Thumm, Alexander Xochitemol, Julio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_04060 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Streaming algorithms for groups and semigroups Lohrey, Markus Lück, Lukas Thumm, Alexander Xochitemol, Julio Group Theory Data Structures and Algorithms 20F10, 68W27 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. |
| title | Streaming algorithms for groups and semigroups |
| topic | Group Theory Data Structures and Algorithms 20F10, 68W27 |
| url | https://arxiv.org/abs/2202.04060 |