2011/03/07 by Volker Diekert, Diekert, Volker, Jürn Laun +3 · 1 citation
Computer Science · Mathematics · #20-04 #Algorithms and Data Compression #Cryptography and Residue Arithmetic #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1103.1232
openalex publication_date 2011/03/07 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
Power circuits are data structures which support efficient algorithms for\nhighly compressed integers. Using this new data structure it has been shown\nrecently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator\nBaumslag group is in P. Before that the best known upper bound has been\nnon-elementary. In the present paper we provide new results for power circuits\nand we give new applications in algorithmic algebra and algorithmic group\ntheory: 1. We define a modified reduction procedure on power circuits which\nruns in quadratic time thereby improving the known cubic time complexity. The\nimprovement is crucial for our other results. 2. We improve the complexity of\nthe Word Problem for the Baumslag group to cubic time thereby providing the\nfirst practical algorithm for that problem. 3. The main result is that the Word\nProblem of Higman's group is decidable in polynomial time. The situation for\nHigman's group is more complicated than for the Baumslag group and forced us to\nadvance the theory of power circuits.\n