Some geodesic problems in groups

DOI10.1515/GCC.2010.014MaRDI QIDQ3085995zbMATH OpenFDO

Authors Andrew Rechnitzer, Murray Elder

Publication date 1 April 2011

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

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

zbMATH Keywords

algorithmic problemsfinitely generated groupsgeodesic problemsgeodesicsword problem

Mathematics Subject Classification ID

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

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] .

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.

Cites work

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

Cited in

(9)

• Non-commutative lattice problems
• On computing geodesics in Baumslag-Solitar groups.
• On Weighted Geodesics in Groups
• C-graph automatic groups.
• The word and geodesic problems in free solvable groups.
• Growth in Baumslag-Solitar groups. II: The Bass-Serre tree
• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• Logspace computations in graph products
• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.

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)