  Computing normal forms in groups (or monoids) is in general harder than
solving the word problem (equality testing). However, normal form computation
has a much wider range of applications. It is therefore interesting to
investigate the complexity of computing normal forms for important classes of
groups.
  For Coxeter groups we show that the following algorithmic tasks can be solved
by a deterministic Turing machine using logarithmic work space, only: 1.
Compute the length of any geodesic normal form. 2. Compute the set of letters
occurring in any geodesic normal form. 3. Compute the Parikh-image of any
geodesic normal form in case that all defining relations have even length
(i.e., in even Coxeter groups.) 4. For right-angled Coxeter groups we can do
actually compute the short length normal form in logspace. (Note that short
length normal forms are geodesic.)
  Next, we apply the results to right-angled Artin groups. They are also known
as free partially commutative groups or as graph groups. As a consequence of
our result on right-angled Coxeter groups we show that shortlex normal forms in
graph groups can be computed in logspace, too. Graph groups play an important
role in group theory, and they have a close connection to concurrency theory.
As an application of our results we show that the word problem for free
partially commutative inverse monoids is in logspace. This result generalizes a
result of Ondrusch and the third author on free inverse monoids. Concurrent
systems which are deterministic and co-deterministic can be studied via inverse
monoids.
