Taming the hydra: the word problem and extreme integer compression

DOI10.1142/S0218196718500583MaRDI QIDQ4554889zbMATH OpenOpenAlexWikidataFDO

Authors Will Dison, Eduard Einstein, Timothy Riley

Publication date 12 November 2018

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

hydrapolynomial timeword problemAckermann functionssubgroup distortionmembership problemDehn function

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algorithms on strings (68W32)

Abstract: For a finitely presented group, the word problem asks for an algorithm which declares whether or not words on the generators represent the identity. The Dehn function is a complexity measure of a direct attack on the word problem by applying the defining relations. Dison & Riley showed that a "hydra phenomenon" gives rise to novel groups with extremely fast growing (Ackermannian) Dehn functions. Here we show that nevertheless, there are efficient (polynomial time) solutions to the word problems of these groups. Our main innovation is a means of computing efficiently with enormous integers which are represented in compressed forms by strings of Ackermann functions.

Recommendations

• Ackermannian integer compression and the word problem for hydra groups
• 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 algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Efficient Computation in Groups Via Compression

Cites work

• scientific article; zbMATH DE number 412172 (Why is no real title available?)
• scientific article; zbMATH DE number 3114412 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 475447 (Why is no real title available?)
• scientific article; zbMATH DE number 1770491 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 848025 (Why is no real title available?)
• scientific article; zbMATH DE number 3086775 (Why is no real title available?)
• scientific article; zbMATH DE number 3090996 (Why is no real title available?)
• A Finitely Generated Infinite Simple Group
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Algorithmically complex residually finite groups
• Asymptotic invariants, complexity of groups and related problems.
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Compressed word problems for inverse monoids
• Compressed word problems in HNN-extensions and amalgamated products
• Efficient Computation in Groups Via Compression
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
• Hydra groups.
• Isoperimetric function of the Baumslag-Gersten group.
• Papers on group theory and topology. Translated and introduced by John Stillwell
• Polynomial-time word problems.
• Power circuits, exponential algebra, and time complexity
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• The Compressed Word Problem for Groups
• The geometry of the word problem for finitely generated groups.
• Word Problems and Membership Problems on Compressed Words

Cited in

(10)

• 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
• Compressed decision problems in hyperbolic groups
• Ackermannian integer compression and the word problem for hydra groups
• Hydra group doubles are not residually finite.
• Hydra groups.
• Compression techniques in group theory
• The word problem in Hanoi Towers groups.
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P

Describes a project that uses

Uses Software

• CRAG

This page was built for publication: Taming the hydra: the word problem and extreme integer compression

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