DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.74

Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group

Authors: Caroline Mattes and Armin Weiß

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and (x,y) ↦ x⋅2^y. The same authors applied power circuits to give a polynomial-time solution to the word problem of the Baumslag group, which has a non-elementary Dehn function. In this work, we examine power circuits and the word problem of the Baumslag group under parallel complexity aspects. In particular, we establish that the word problem of the Baumslag group can be solved in NC - even though one of the essential steps is to compare two integers given by power circuits and this, in general, is shown to be 𝖯-complete. The key observation is that the depth of the occurring power circuits is logarithmic and such power circuits can be compared in NC.

Cite as

Caroline Mattes and Armin Weiß. Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mattes_et_al:LIPIcs.MFCS.2021.74,
  author =	{Mattes, Caroline and Wei{\ss}, Armin},
  title =	{{Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.74},
  URN =		{urn:nbn:de:0030-drops-145148},
  doi =		{10.4230/LIPIcs.MFCS.2021.74},
  annote =	{Keywords: Word problem, Baumslag group, power circuit, parallel complexity}
}

Search Results

Documents authored by Mattes, Caroline

Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group

Abstract

Cite as

Thanks for your feedback!

Could not send message