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