A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.

MaRDI QIDQ716392zbMATH OpenFDO

Authors Murray Elder

Publication date 28 April 2011

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.0216, https://projecteuclid.org/euclid.ijm/1299679740

zbMATH Keywords

NP-complete problemsdeterministic algorithmslinear-time algorithmsBaumslag-Solitar groupsmetabelian groupsgeodesic lengthsgeodesic 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) Solvable groups, supersolvable groups (20F16)

Abstract: We present an algorithm to convert a word of length $n$ in the standard generators of the solvable Baumslag-Solitar group $BS(1,p)$ into a geodesic word, which runs in linear time and $O(nlogn)$ space on a random access machine.

Recommendations

• On computing geodesics in Baumslag-Solitar groups.
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Some geodesic problems in groups
• The word and geodesic problems in free solvable groups.
• A new proof of the growth rate of the solvable Baumslag-Solitar groups

Cited in

(11)

• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• C-graph automatic groups.
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• Growth in Baumslag-Solitar groups. II: The Bass-Serre tree
• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• The word and geodesic problems in free solvable groups.
• Some geodesic problems in groups
• Logspace computations in graph products
• On computing geodesics in Baumslag-Solitar groups.
• On Weighted Geodesics in Groups
• Conjugation curvature in solvable Baumslag–Solitar groups

This page was built for publication: A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.

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