DROPS

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

Streaming in Graph Products

Abstract

Cite as

Thanks for your feedback!

Could not send message