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

Baumslag-Solitar groupsdeterministic algorithmsgeodesic lengthsgeodesic problemslinear-time algorithmsmetabelian groupsNP-complete problems

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) Solvable groups, supersolvable groups (20F16) Geometric group theory (20F65) Analysis of algorithms and problem complexity (68Q25)

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.

Review text

Recently \textit{A. Myasnikov, V. Roman'kov, A. Ushakov} and \textit{A. Vershik} [Trans. Am. Math. Soc. 362, No. 9, 4655-4682 (2010; Zbl 1207.20026)] proved that for free metabelian groups with standard generating sets, the following `bounded geodesic problem' is NP-complete: given a word in the generators and an integer \(k\), decide whether the geodesic length of the word is less than \(k\). The author and \textit{A. Rechnitzer} [Groups Complex. Cryptol. 2, No. 2, 223-229 (2010; Zbl 1222.20023)] show that this problem is equivalent to the `geodesic problem' (find for a word a geodesic word representing the same element) and simultaneously to the `length geodesic problem' (find for a word its geodesic length). A deterministic algorithm is given which takes as input a word of length \(n\) in the generators in the Baumslag-Solitar group \(B(1,p)=\langle a,t\mid tat^{-1}=a^p\rangle\) for any integer \(p\geq 2\), and outputs a geodesic word representing the same element, in time \(O(n)\). Consequently, the three problems mentioned above are solvable in linear time. Recent work of \textit{V. Diekert} and \textit{J. Laun} [Int. J. Algebra Comput. 21, No. 1-2, 119-145 (2011; Zbl 1235.20041)] extends the result of this paper to groups of the form \(\langle a,t\mid ta^pt^{-1}=a^q\rangle\) when \(p\) divides \(q\). Their algorithm runs in quadratic time, but in the case \(p=1\) the time reduces to linear, although their algorithm is qualitatively different.

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

(12)

• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• On computing geodesics in Baumslag-Solitar groups.
• Some geodesic problems in 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
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• Logspace computations in graph products
• Conjugation curvature in solvable Baumslag–Solitar groups
• Rational subsets of 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)