@InProceedings{	  dmm97icalp,
  author	= "Volker Diekert and {\relax Yu}ri Matiyasevich and Anca
		  Muscholl",
  address	= "Heidelberg",
  booktitle	= "Proc. 24th International Colloquium Automata, Languages
		  and Programming (ICALP'97), Bologna",
  editor	= "P. Degano and R. Gorrieri and A. Marchetti-Spaccamela",
  volume	= "1256",
  pages		= "336--347",
  publisher	= "Springer-Verlag",
  series	= "Lecture Notes in Computer Science",
  title		= "Solving trace equations using lexicographical normal
		  forms",
  year		= "1997",
  doi		= "10.1007/3-540-63165-8_190",
  abstract	= "Very recently, the second author showed that the question
		  whether an equation over a trace monoid has a solution or
		  not is decidable \cite{mat96lfcs,mat97lfcs}. In the
		  original proof this question is reduced to the solvability
		  of word equations with constraints, by induction on the
		  size of the commutation relation. In the present paper we
		  give another proof of this result using lexicographical
		  normal forms. Our method is a direct reduction of a trace
		  equation system to a word equation system with regular
		  constraints, using a new result on lexicographical normal
		  forms."
}