@Article{	  hm97,
  author	= "Hendrik Jan Hoogeboom and Anca Muscholl",
  journal	= "Theoretical Computer Science",
  pages		= "309--321",
  title		= "The code problem for traces -- improving the boundaries",
  volume	= "172",
  number	= "1-2",
  year		= "1997",
  doi		= "10.1016/S0304-3975(96)00216-2",
  abstract	= "The code problem for trace monoids is known to be
		  undecidable if the graph associated to the independence
		  alphabet $(\Sigma,I)$ contains an induced $C_{4}$
		  (chordless cycle on four vertices); it is decidable
		  whenever this graph contains neither $C_{4}$ nor $P_{4}$
		  (the chordless path on four vertices) as induced subgraph.
		  
		  Due to the close connection between the code problem and
		  the intersection problem for rational trace languages one
		  may expect to have the same boundaries w.r.t.~decidability
		  for both problems. We show in this paper that this is not
		  the case. We have two surprising results, which are in some
		  sense negative. First, not all remaining cases are
		  undecidable, in particular the code problem is decidable
		  when $(\Sigma,I)$ is exactly $P_{4}$. Independently,
		  Yu.~Matiyasevich observed the decidability of the code
		  problem in this particular case. Second, we exhibit
		  independence alphabets $(\Sigma,I)$ containing $P_{4}$, but
		  no $C_{4}$ as induced subgraph, for which the code problem
		  is undecidable. This shows for the first time that not all
		  cases without induced $C_{4}$ are decidable."
}