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

Volker Diekert, Jürn Laun, Alexander Ushakov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

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 is decidable in polynomial time. 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. 3. The Word Problem of Higman's group is decidable in polynomial time. It is due to the last result that we were forced to advance the theory of power circuits. Thanks: Part of this work was done when the first two authors visited the Stevens Institute of Technology in September 2010 and March 2011. The support and the hospitality of the Stevens Institute is greatly acknowledged. The work of the third author was partially supported by NSF grant DMS-0914773.

Original languageEnglish
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Pages218-229
Number of pages12
DOIs
StatePublished - 2012
Event29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012 - Paris, France
Duration: 29 Feb 20123 Mar 2012

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume14
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Country/TerritoryFrance
CityParis
Period29/02/123/03/12

Keywords

  • Algorithmic group theory
  • Compression
  • Data structures
  • Word Problem

Fingerprint

Dive into the research topics of 'Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P'. Together they form a unique fingerprint.

Cite this