Efficient algorithms for highly compressed data: the word problem in Higman's group is in P

DOI10.4230/LIPICS.STACS.2012.218zbMATH Open1245.68103arXiv1103.1232OpenAlexW2266715429MaRDI QIDQ2904763FDOQ2904763

Authors: Volker Diekert, Jürn Laun, Alexander Ushakov 

Publication date: 23 August 2012

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 has been 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. 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.

Full work available at URL: https://arxiv.org/abs/1103.1232

Recommendations

• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Efficient Computation in Groups Via Compression
• Taming the hydra: the word problem and extreme integer compression
• The Compressed Word Problem for Groups

zbMATH Keywords

data structurescompressionword problemalgorithmic group theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cited In (9)

• The conjugacy problem for Higman’s group
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Power circuits, exponential algebra, and time complexity
• Ackermannian integer compression and the word problem for hydra groups
• Compression techniques in group theory
• Compressed word problems in HNN-extensions and amalgamated products
• Taming the hydra: the word problem and extreme integer compression

Uses Software

• CRAG

This page was built for publication: Efficient algorithms for highly compressed data: the word problem in Higman's group is in P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904763)