Some geodesic problems in groups

DOI10.1515/GCC.2010.014zbMATH Open1222.20023arXiv0907.3258MaRDI QIDQ3085995FDOQ3085995

Murray Elder, Andrew Rechnitzer

Publication date: 1 April 2011

Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)

Abstract: We consider several algorithmic problems concerning geodesics in finitely generated groups. We show that the three geodesic problems considered by Miasnikov et al [arXiv:0807.1032] are polynomial-time reducible to each other. We study two new geodesic problems which arise in a previous paper of the authors and Fusy [arXiv:0902.0202] .

Full work available at URL: https://arxiv.org/abs/0907.3258

Recommendations

• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• On Weighted Geodesics in Groups
• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• Non-commutative lattice problems
• The Length of Elements in Free Solvable Groups
• Average-case complexity and decision problems in group theory.
• The complexity of Dehn's algorithm for word problems in groups
• COMPUTATION IN WORD-HYPERBOLIC GROUPS
• A characterisation of virtually free groups.
• On computing geodesics in Baumslag-Solitar groups.

zbMATH Keywords

finitely generated groupsgeodesicsword problemalgorithmic problemsgeodesic problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Automatic structures, rational growth, and geometrically finite hyperbolic groups
• Minimal length elements of Thompson's group \(F\)
• FOREST DIAGRAMS FOR ELEMENTS OF THOMPSON'S GROUP F
• Minimal length normal forms for some soluble groups
• Counting elements and geodesics in Thompson's group \(F\).

Cited In (5)

• \(\mathcal C\)-graph automatic groups.
• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• Logspace computations in graph products
• On Weighted Geodesics in Groups
• Growth in Baumslag–Solitar groups II: The Bass–Serre tree

This page was built for publication: Some geodesic problems in groups

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