The Compressed Word Problem for Groups

DOI10.1007/978-1-4939-0748-9MaRDI QIDQ5405102zbMATH OpenOpenAlexFDO

Authors 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

complexity of algorithmscompressed word problemfinitely generated groupsword problem

Mathematics Subject Classification ID

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

Recommendations

• The compressed word problem in relatively hyperbolic groups
• Word Problems and Membership Problems on Compressed Words
• Space complexity and word problems of groups
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• Ackermannian integer compression and the word problem for hydra groups
• An Introduction to Combinatorial Group Theory and the Word Problem
• The complexity of Dehn's algorithm for word problems in groups
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• scientific article; zbMATH DE number 5785814
• The fully compressed subgroup membership problem

Cited in

(49)

• Knapsack in graph groups
• Evaluation of circuits over nilpotent and polycyclic groups
• On the complexity of the smallest grammar problem over fixed alphabets
• Compression techniques in group theory
• The compressed word problem in relatively hyperbolic groups
• The power word problem in graph products
• Cadences in grammar-compressed strings
• An automaton group with \textsf{PSPACE}-complete word problem
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
• Parallel identity testing for skew circuits with big powers and applications
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• Evaluating matrix circuits
• Solutions to twisted word equations and equations in virtually free groups
• Compressed Word Problems in HNN-Extensions and Amalgamated Products
• Equality Testing of Compressed Strings
• Efficient Computation in Groups Via Compression
• Compressed words and automorphisms in fully residually free groups.
• Taming the hydra: the word problem and extreme integer compression
• Parallel identity testing for skew circuits with big powers and applications
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Low-complexity computations for nilpotent subgroup problems
• Equivalence of Linear Tree Transducers with Output in the Free Group
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• Compressed decision problems in hyperbolic groups
• The power word problem
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Word Problems and Membership Problems on Compressed Words
• Complexity of word problems for HNN-extensions
• Complexity of word problems for HNN-extensions
• 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
• Compressed word problems in HNN-extensions and amalgamated products
• The power word problem in graph products
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Compressed decision problems in hyperbolic groups
• Identity testing for radical expressions
• The complexity of knapsack problems in wreath products
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Membership problems in infinite groups
• Subgroup membership in GL\((2,\mathbb{Z})\)
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Streaming in graph products
• Streaming word problems
• Polynomial-time word problems.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405102)