Taming the hydra: the word problem and extreme integer compression

DOI10.1142/S0218196718500583zbMATH Open1499.20084arXiv1509.02557OpenAlexW2962972140WikidataQ129481860 ScholiaQ129481860MaRDI QIDQ4554889FDOQ4554889

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)

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.

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

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

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)

Cites Work

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

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.
• Compression techniques in group theory
• Hydra groups.
• The word problem in Hanoi Towers groups.
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P

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)