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

DOI10.1142/S0218196712400085MaRDI QIDQ4904514zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Jürn Laun, Alexander Ushakov

Publication date 30 January 2013

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

Full work available at URL https://doi.org/10.1142/s0218196712400085

zbMATH Keywords

algorithmic group theoryBaumslag groupcompressiondata structuresHigman groupword problem

Mathematics Subject Classification ID

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)

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
• Compressed word problems in HNN-extensions and amalgamated products

Cites work

• A Finitely Generated Infinite Simple Group
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• ALMOST EVERY GROUP IS HYPERBOLIC
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Generic-case complexity, decision problems in group theory, and random walks.
• Introduction to algorithms.
• Isoperimetric and isodiametric functions of groups
• Polynomial-time word problems.
• Pseudo-natural algorithms for finitely generated presentations of monoids and groups
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• The word problem
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Word Problems and Membership Problems on Compressed Words

Cited in

(9)

• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
• 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
• Compressed decision problems in hyperbolic groups
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Improved parallel algorithms for generalized Baumslag groups
• Compressed decision problems in hyperbolic groups

Describes a project that uses

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 Q4904514)