@InProceedings{	  die93fct,
  author	= "Volker Diekert",
  address	= "Heidelberg",
  booktitle	= "Proc. 9th Fundamentals of Computation Theory (FCT'93),
		  Szeged (Hungary) 1993",
  editor	= "Z. {\'E}sik",
  note		= "Invited Lecture",
  volume	= "710",
  pages		= "1--15",
  publisher	= "Springer-Verlag",
  series	= "Lecture Notes in Computer Science",
  title		= "Rewriting, semi-commutations, and {M}{\"o}bius functions",
  year		= "1993",
  abstract	= "The theory of rewriting over free partially commutative
		  monoids (trace rewriting) combines combinatorial aspects
		  from string rewriting (modulo a congruence) and graph
		  rewriting. It leads to feasible algorithms, but some
		  interesting complexity questions are still open. One of the
		  challenging open problems is to improve the known Ciobanuic
		  time bound for the non-uniform complexity of
		  length-reducing systems. For certain one-rule systems we
		  present here a new linear time algorithm for computing
		  irreducible descendants, but we are still not able to
		  handle the general case of multiple rules in linear time.
		  
		  Semi commutations can be treated from the viewpoint of
		  trace rewriting and there are strong connections to the
		  combinatorics of {M\"o}bius-functions.",
  doi		= "10.1007/3-540-57163-9_1"
}