Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

DOI10.4230/LIPIcs.STACS.2012.218zbMath1245.68103arXiv1103.1232OpenAlexW2266715429MaRDI QIDQ2904763

Volker Diekert, Alexander Ushakov, Jürn Laun

Publication date: 23 August 2012

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

zbMATH Keywords

word problemcompressiondata structuresalgorithmic 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 (6)

Taming the hydra: The word problem and extreme integer compression ⋮ 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 ⋮ Conjugacy in Baumslag's group, generic case complexity, and division in power circuits ⋮ The conjugacy problem for Higman’s group ⋮ Compression techniques in group theory

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