License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.218
URN: urn:nbn:de:0030-drops-34204
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3420/
Go to the corresponding LIPIcs Volume Portal

Diekert, Volker ; Laun, Jürn ; Ushakov, Alexander

Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

pdf-format:
36.pdf (0.7 MB)

Abstract

Power circuits are data structures which support efficient algorithms
for highly compressed integers. Using this new data structure it has
been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic group theory: 1. We define a modified reduction procedure on power circuits which runs in quadratic time thereby improving the known cubic time complexity. 2. We improve the complexity of the Word Problem for the Baumslag group to cubic time thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) 3. The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of Power Circuits.

BibTeX - Entry

@InProceedings{diekert_et_al:LIPIcs:2012:3420,
  author =	{Volker Diekert and J{\"u}rn Laun and Alexander Ushakov},
  title =	{{Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{218--229},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3420},
  URN =		{urn:nbn:de:0030-drops-34204},
  doi =		{10.4230/LIPIcs.STACS.2012.218},
  annote =	{Keywords: Algorithmic group theory, Data structures, Compression, Word Problem}
}

Keywords: Algorithmic group theory, Data structures, Compression, Word Problem
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

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