  Baumslag-Solitar groups were introduced in 1962 by Baumslag and Solitar as
examples for finitely presented non-Hopfian two-generator groups. Since then,
they served as examples for a wide range of purposes. As Baumslag-Solitar
groups are HNN extensions, there is a natural generalization in terms of graph
of groups.
  Concerning algorithmic aspects of generalized Baumslag-Solitar groups,
several decidability results are known. Indeed, a straightforward application
of standard algorithms leads to a polynomial time solution of the word problem
(the question whether some word over the generators represents the identity of
the group). The conjugacy problem (the question whether two given words
represent conjugate group elements) is more complicated; still decidability has
been established by Anshel and Stebe for ordinary Baumslag-Solitar groups and
for generalized Baumslag-Solitar groups independently by Lockhart and Beeker.
However, up to now no precise complexity estimates have been given.
  In this work, we give a LOGSPACE algorithm for both problems. More precisely,
we describe a uniform TC^0 many-one reduction of the word problem to the word
problem of the free group. Then we refine the known techniques for the
conjugacy problem and show that it can be solved in LOGSPACE. Moreover, for
ordinary Baumslag-Solitar groups also conjugacy is AC^0-Turing-reducible to the
word problem of the free group.
  Finally, we consider uniform versions (where also the graph of groups is part
of the input) of both word and conjugacy problem: while the word problem still
is solvable in LOGSPACE, the conjugacy problem becomes EXPSPACE-complete.
