Term Rewriting and Applications

1. Front Matter

   PDF

2. Confluent Term Rewriting Systems

   • Yoshihito Toyama

   Pages 1-1

3. Generalized Innermost Rewriting

   • Jaco van de Pol, Hans Zantema

   Pages 2-16

4. Orderings for Innermost Termination

   • Mirtha-Lina Fernández, Guillem Godoy, Albert Rubio

   Pages 17-31

5. Leanest Quasi-orderings

   • Nachum Dershowitz, E. Castedo Ellerman

   Pages 32-45

6. Abstract Modularity

   • Michael Abbott, Neil Ghani, Christoph Lüth

   Pages 46-60

7. Union of Equational Theories: An Algebraic Approach

   • Piotr Hoffman

   Pages 61-73

8. Equivariant Unification

   • James Cheney

   Pages 74-89

9. Faster Basic Syntactic Mutation with Sorts for Some Separable Equational Theories

   • Christopher Lynch, Barbara Morawska

   Pages 90-104

10. Unification in a Class of Permutative Theories

    • Thierry Boy de la Tour, Mnacho Echenim

    Pages 105-119

11. Dependency Pairs for Simply Typed Term Rewriting

    • Takahito Aoto, Toshiyuki Yamada

    Pages 120-134

12. Universal Algebra for Termination of Higher-Order Rewriting

    • Makoto Hamana

    Pages 135-149

13. Quasi-interpretations and Small Space Bounds

    • Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen

    Pages 150-164

14. A Sufficient Completeness Reasoning Tool for Partial Specifications

    • Joe Hendrix, Manuel Clavel, José Meseguer

    Pages 165-174

15. Tyrolean Termination Tool

    • Nao Hirokawa, Aart Middeldorp

    Pages 175-184

16. Call-by-Value Is Dual to Call-by-Name – Reloaded

    • Philip Wadler

    Pages 185-203

17. λμ-Calculus and Duality: Call-by-Name and Call-by-Value

    • Jérôme Rocheteau

    Pages 204-218

18. Reduction in a Linear Lambda-Calculus with Applications to Operational Semantics

    • Alex Simpson

    Pages 219-234

19. Higher-Order Matching in the Linear Lambda Calculus in the Absence of Constants Is NP-Complete

    • Ryo Yoshinaka

    Pages 235-249

20. Localized Fairness: A Rewriting Semantics

    • José Meseguer

    Pages 250-263

This volume contains the proceedings of the 16th International Conference on Rewriting Techniques and Applications (RTA2005),whichwasheldonApril19– 21, 2005, at the Nara-Ken New Public Hall in the center of the Nara National Park in Nara, Japan. RTA is the major forum for the presentation of research on all aspects of rewriting.PreviousRTAconferenceswereheldinDijon(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), Valencia (2003), and Aachen (2004). This year, there were 79 submissions from 20 countries, of which 31 papers were accepted for publication (29 regular papers and 2 system descriptions). The submissions came from France (10 accepted papers of the 23.1 submitted papers), USA (5.6 of 11.7), Japan (4 of 9), Spain (2.7 of 6.5), UK (2.7 of 4.7), The Netherlands (1.7 of 3.8), Germany (1.3 of 2.3), Austria (1 of 1), Poland (1 of 1), Israel (0.5 of 0.8), Denmark (0.5 of 0.5), China (0 of 4), Korea (0 of 4), Taiwan (0 of 1.3), Australia (0 of 1), Brazil (0 of 1), Russia (0 of 1), Switzerland (0 of 1), Sweden (0 of 1), and Italy (0 of 0.3). Each submission was assigned to at least three Program Committee m- bers, who carefully reviewed the papers, with the help of 111 external referees.

• automata
• automated deduction
• higher order rewriting
• lambda calculus
• logic programming
• programming calculi
• proving
• rewriting
• rewriting systems
• semantics
• term rewriting
• termination
• type inference
• unification
• verification

• LuFG Informatik 2, RWTH Aachen University, Germany

  Jürgen Giesl

Policies and ethics