Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
From MaRDI portal
Publication:2254512
Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) 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) Analysis of algorithms and problem complexity (68Q25)
Abstract: This paper continues the 2012 STACS contribution by Diekert, Ushakov, and the author. We extend the results published in the proceedings in two ways. First, we show that the data structure of power circuits can be generalized to work with arbitrary bases q>=2. This results in a data structure that can hold huge integers, arising by iteratively forming powers of q. We show that the properties of power circuits known for q=2 translate to the general case. This generalization is non-trivial and additional techniques are required to preserve the time bounds of arithmetic operations that were shown for the case q=2. The extended power circuit model permits us to conduct operations in the Baumslag-Solitar group BS(1,q) as efficiently as in BS(1,2). This allows us to solve the word problem in the generalization H_4(1,q) of Higman's group, which is an amalgamated product of four copies of the Baumslag-Solitar group BS(1,q) rather than BS(1,2) in the original form. As a second result, we allow arbitrary numbers f>=4 of copies of BS(1,q), leading to an even more generalized notion of Higman groups H_f(1,q). We prove that the word problem of the latter can still be solved within the O(n^6) time bound that was shown for H_4(1,2).
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 Higman's group is in P.
- Efficient Computation in Groups Via Compression
- Taming the hydra: the word problem and extreme integer compression
- Compressed word problems in HNN-extensions and amalgamated products
Cites work
- A Finitely Generated Infinite Simple Group
- An essay on free products of groups with amalgamations
- Combinatorial group theory.
- Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- Introduction to algorithms.
- Power circuits, exponential algebra, and time complexity
- The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
- Triangles of Baumslag-Solitar groups.
Cited in
(11)- Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Taming the hydra: the word problem and extreme integer compression
- Ackermannian integer compression and the word problem for hydra groups
- Power circuits, exponential algebra, and time complexity
- Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
- The conjugacy problem for Higman’s group
- The word problem in Hanoi Towers groups.
- The Compressed Word Problem for Groups
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- Improved parallel algorithms for generalized Baumslag groups
This page was built for publication: Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254512)
