\title{On Codings of Traces\\Extended Abstract}

\author{Volker Diekert \qquad Anca Muscholl \qquad Klaus Reinhardt}

\institute{Institut f\"ur Informatik, Universit\"at Stuttgart\\
Breitwiesenstr.~20-22, D-70565 Stuttgart}


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.