@InProceedings{	  dkl12conm,
  title		= "Logspace computations in {C}oxeter groups and graph
		  groups",
  year		= "2012",
  volume	= "582",
  pages		= "77--94",
  publisher	= "Amer. Math. Soc.",
  series	= "Contemporary Mathematics",
  booktitle	= "Computational and Combinatorial Group Theory and
		  Cryptography",
  author	= "Diekert, Volker and Kausch, Jonathan and Lohrey, Markus",
  note		= "Journal version of LATIN 2012, 243--254, LNCS 7256, 2012 ",
  abstract	= "Computing normal forms in groups (or monoids) is
		  computation- ally harder than solving the word problem
		  (equality testing), in general. How- ever, 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 actually
		  compute the shortlex normal form in logspace. 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 con- sequence 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."
}