@InProceedings{	  dmr95,
  author	= "Volker Diekert and Anca Muscholl and Klaus Reinhardt",
  address	= "Heidelberg",
  booktitle	= "Proc. 12th Annual Symposium on Theoretical Aspects of
		  Computer Science (STACS'95), Munich (Germany)",
  editor	= "E. W. Mayr and C. Puech",
  volume	= "900",
  pages		= "385--396",
  publisher	= "Springer-Verlag",
  series	= "Lecture Notes in Computer Science",
  title		= "On Codings of Traces",
  year		= "1995",
  abstract	= "The paper solves the main open problem of \cite{bfg94}. We
		  show that given two dependence alphabets $(\Sigma, D)$ and
		  $(\Sigma', D')$, it is decidable whether there exists a
		  strong coding $h: M(\Sigma, D) \longrightarrow M(\Sigma',
		  D')$ between the associated trace monoids. In fact, we show
		  that the problem is NP-complete. (A coding is an injective
		  homomorphism, it is strong if independent letters are
		  mapped to independent traces.) We exhibit an example of
		  trace monoids where a coding between them exists, but no
		  strong coding. The decidability of codings remains open, in
		  general. We have a lower and an upper bound, which show
		  both to be strict. We further discuss encodings of free
		  products of trace monoids and give almost optimal
		  constructions.
		  
		  In the final section, we state that the coding property is
		  undecidable in a naturally arising class of homomorphisms.",
  doi		= "10.1007/3-540-59042-0_90"
}