On Computing Geodesics in Baumslag-Solitar Groups
Time and place
4 PM on Friday, October 1st, 2010; GC 5417
Volker Diekert (Universität Stuttgart)
Abstract
Baumslag-Solitar groups enjoy many remarkable properties; the group BS(p,q) is a one-relator group defined by BS(p,q) presented as by {a ,t | a^p t^{-1}=a^q }.
In my lecture I will give a dynamic programming method for computing geodesic words. (A geodesic word for group element g describes a shortest path from 1 to g in the Cayley graph of BS(p,q).)
As a consequence of our method we will see that if p divides q, then the set of horocyclic elements (elements in the cyclic subgroup generated by a ) in length-lexicographical normal form is a deterministic (and unambiguous) linear context-free (one-counter) language; and it can be recognized in log-space. The growth series of the horocyclic subgroup is therefore a rational function (quotient of two polynomials) and can be calculated effectively. Rationality of the growth series is due to Freden et al. who showed it with a different method. The growth tells us how many group elements are in balls of a certain radius around the origin of the Cayley graph of BS(p,q).
If p divides q our main result is a square-time algorithm to compute the geodesic length of all group elements. This is a positive partial answer to a question raised by Elder et al. in 2009. In the case where p does not divide q it might be that the problem is actually Co-NP-complete. The investigation of the general case remains a challenging research project.
My lecture is based on a joint work with Jürn Laun to appear in IJAC.
