Compressed decision problems in hyperbolic groups

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)

zbMATH Keywords

word problemhyperbolic groupstraight-line programsalgorithmic group theory

Mathematics Subject Classification ID

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