Compressed decision problems in hyperbolic groups
From MaRDI portal
Publication:6619327
DOI10.4171/ggd/809MaRDI QIDQ6619327
Derek F. Holt, Saul Schleimer, Markus Lohrey
Publication date: 15 October 2024
Published in: Groups, Geometry, and Dynamics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hydra groups.
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
- The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
- The simultaneous conjugacy problem in groups of piecewise linear functions.
- The isomorphism problem for all hyperbolic groups.
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Knapsack problems in products of groups
- Polynomial-time word problems.
- Coxeter groups are virtually special
- Research announcement: The structure of groups with a quasiconvex hierarchy.
- The complexity of Grigorchuk groups with application to cryptography
- Rational subgroups of biautomatic groups
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Über unendliche diskontinuierliche Gruppen.
- Knapsack in graph groups
- Evaluation of circuits over nilpotent and polycyclic groups
- Canonical representatives and equations in hyperbolic groups
- A short proof that a subquadratic isoperimetric inequality implies a linear one
- Equations in acylindrically hyperbolic groups and verbal closedness
- The complexity of solution sets to equations in hyperbolic groups
- The compressed word problem in relatively hyperbolic groups
- An automaton group with \textsf{PSPACE}-complete word problem
- Faster Fully Compressed Pattern Matching by Recompression
- THE CONJUGACY PROBLEM IN HYPERBOLIC GROUPS FOR FINITE LISTS OF GROUP ELEMENTS
- Algorithmics on SLP-compressed strings: A survey
- Algebra and Computer Science
- Knapsack Problems for Wreath Products
- The Smallest Grammar Problem
- Foliations for solving equations in groups: free, virtually free, and hyperbolic groups
- COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
- Some two-generator one-relator non-Hopfian groups
- HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
- ALMOST EVERY GROUP IS HYPERBOLIC
- Finite Monoids: From Word to Circuit Evaluation
- Taming the hydra: The word problem and extreme integer compression
- Ackermannian Integer Compression and the Word Problem for Hydra Groups.
- POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
- COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS
- EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P
- Low-complexity computations for nilpotent subgroup problems
- Reducibility among Combinatorial Problems
- SLP compression for solutions of equations with constraints in free and hyperbolic groups
- The Compressed Word Problem for Groups
- Word Problems and Membership Problems on Compressed Words
- THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
- Knapsack problems in groups
- A non-cyclic one-relator group all of whose finite quotients are cyclic
- CONJUGACY OF FINITE SUBSETS IN HYPERBOLIC GROUPS
- A Finitely Generated Infinite Simple Group
- Knapsack in hyperbolic groups
- Improved parallel algorithms for generalized Baumslag groups
This page was built for publication: Compressed decision problems in hyperbolic groups
