On computing geodesics in Baumslag-Solitar groups.

DOI10.1142/S0218196711006108MaRDI QIDQ2996841zbMATH OpenFDO

Authors Volker Diekert, Jürn Laun

Publication date 3 May 2011

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

NP-complete problemsdeterministic algorithmsnormal form theoremspolynomial 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 introduce the peak normal form of elements of the Baumslag-Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element $u^{-1}v$ yields the shortest path between $u$ and $v$ in the Cayley graph. For horocyclic elements the peak normal form and the length-lexicographical normal form coincide. The main result of this paper is that we can compute the peak normal form in polynomial time if $p$ divides $q$. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in Elder et al. 2009, arXiv.org:0907.3258. For arbitrary $p$ and $q$ it is possible to compute the peak normal form (length-lexicolgraphical normal form resp.) also for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the $t$-sequence starts with $t^{-1}$ and ends with $t$. To solve the general case in polynomial time for arbitrary $p$ and $q$ remains a challenging open problem.

Recommendations

• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• Minimal length normal forms for some soluble groups
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• Growth in Baumslag-Solitar groups. I: Subgroups and rationality.
• Some geodesic problems in groups

Cites work

• On the entropy of context-free languages
• Some two-generator one-relator non-Hopfian groups

Cited in

(7)

• Metric properties of Baumslag-Solitar groups.
• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar 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
• Limits of Baumslag-Solitar groups and dimension estimates in the space of marked groups.
• Some geodesic problems in groups
• Conjugation curvature in solvable Baumslag–Solitar groups

This page was built for publication: On computing geodesics in Baumslag-Solitar groups.

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