The Compressed Word Problem for Groups

DOI10.1007/978-1-4939-0748-9zbMath1391.20003OpenAlexW636399398MaRDI QIDQ5405102

Markus Lohrey

Publication date: 31 March 2014

Published in: SpringerBriefs in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4939-0748-9

zbMATH Keywords

finitely generated groupsword problemcomplexity of algorithmscompressed word problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Automorphism groups of groups (20F28) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Research exposition (monographs, survey articles) pertaining to group theory (20-02)

Related Items (30)

Equivalence of Linear Tree Transducers with Output in the Free Group ⋮ Equality Testing of Compressed Strings ⋮ The compressed word problem in relatively hyperbolic groups ⋮ Taming the hydra: The word problem and extreme integer compression ⋮ Evaluating Matrix Circuits ⋮ The power word problem in graph products ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ Algorithms for contractibility of compressed curves on 3-manifold boundaries ⋮ The word problem for finitary automaton groups ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Knapsack in graph groups ⋮ Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Cadences in grammar-compressed strings ⋮ Tree compression using string grammars ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Complexity of word problems for HNN-extensions ⋮ Complexity of word problems for HNN-extensions ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time ⋮ Compression techniques in group theory

This page was built for publication: The Compressed Word Problem for Groups