Rewriting techniques and applications

This volume contains the proceedings of the 15th International Conference on Rewriting Techniques and Applications (RTA 2004), which was held June 2– 5, 2004, at the RWTH Aachen in Germany. RTA is the major forum for the presentation of research on all aspects of rewriting. Previous RTA conferences took place in Dijon (1985), Bordeaux (1987), Chapel Hill (1989), Como (1991), Montreal (1993), Kaiserslautern (1995), Rutgers (1996), Sitges (1997), Tsukuba (1998), Trento (1999), Norwich (2000), Utrecht (2001), Copenhagen (2002), and Valencia (2003). The program committee selected 19 papers for presentation, including ?ve system descriptions, from a total of 43 submissions. In addition, there were invited talks by Neil Jones, Aart Middeldorp, and Robin Milner. Many people helped to make RTA 2004 a success. I am grateful to the m- bers of the program committee and the external referees for reviewing the s- missionsandmaintainingthehighstandardsoftheRTAconferences. Itisagreat pleasure to thank the conference chair Jurgen ¨ Giesl and the other members of the local organizing committee. They were in charge of the local organization of all events partaking in the Federated Conference on Rewriting, Deduction, and Programming (RDP). Apart from RTA 2004, these events were: – 2nd International Workshop on Higher-Order Rewriting (Delia Kesner, Femke van Raamsdonk, and Joe Wells), – 5th International Workshop on Rule-Based Programming (Slim Abdennadher and Christophe Ringeissen), – 13thInternationalWorkshoponFunctionaland(Constraint)LogicProgr- ming (Herbert Kuchen), – IFIP Working Group 1.