EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P

DOI10.1142/S0218196712400085zbMath1264.20034OpenAlexW2115760473MaRDI QIDQ4904514

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

word problemcompressiondata structuresBaumslag groupHigman groupalgorithmic group theory

Mathematics Subject Classification ID

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

Related Items (2)

Improved parallel algorithms for generalized Baumslag groups ⋮ Unnamed Item

Uses Software

• CRAG

Cites Work

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

This page was built for publication: EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P