TY - JOUR
T1 - Efficient algorithms for highly compressed data
T2 - The word problem in Higman's group is in P
AU - Diekert, Volker
AU - Laun, Jürn
AU - Ushakov, Alexander
PY - 2012/12
Y1 - 2012/12
N2 - 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 algebra and 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. The improvement is crucial for our other results. (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.
AB - 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 algebra and 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. The improvement is crucial for our other results. (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.
KW - Data structures
KW - Word Problem
KW - algorithmic group theory
KW - compression
UR - http://www.scopus.com/inward/record.url?scp=84871770684&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871770684&partnerID=8YFLogxK
U2 - 10.1142/S0218196712400085
DO - 10.1142/S0218196712400085
M3 - Article
AN - SCOPUS:84871770684
SN - 0218-1967
VL - 22
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 8
M1 - 1240008
ER -