License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.72
URN: urn:nbn:de:0030-drops-168707
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16870/
Go to the corresponding LIPIcs Volume Portal

Lohrey, Markus ; Lück, Lukas

Streaming Word Problems

pdf-format:
LIPIcs-MFCS-2022-72.pdf (0.7 MB)

Abstract

We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, direct products, free products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson’s group F.

BibTeX - Entry

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.72,
  author =	{Lohrey, Markus and L\"{u}ck, Lukas},
  title =	{{Streaming Word Problems}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{72:1--72:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16870},
  URN =		{urn:nbn:de:0030-drops-168707},
  doi =		{10.4230/LIPIcs.MFCS.2022.72},
  annote =	{Keywords: word problems for groups, streaming algorithms}
}

Keywords: word problems for groups, streaming algorithms
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI