The RTA list of open problems

The RTA list of open problems summarizes open problems in the field of the International Conference on Rewriting Techniques and Applications (RTA). For the RTA 2002 conference, the topics of RTA were given as

• Applications: case studies; rule-based programming; symbolic and algebraic computation; theorem proving; functional and logic programming; proof checking.
• Foundations: matching and unification; completion techniques; strategies; constraint solving; explicit substitutions.
• Frameworks: string, term, and graph rewriting; lambda-calculus and higher-order rewriting; conditional rewriting; proof nets; constrained rewriting and deduction; categorical and infinitary rewriting.
• Implementation: compilation techniques; parallel execution; rewriting tools.
• Semantics: equational logic; rewriting logic.

The RTA list of open problems was created in 1991 by Nachum Dershowitz, Jean-Pierre Jouannaud and Jan Willem Klop on occasion of the RTA’91 conference. Updated lists have since been published at RTA’93, RTA’95 and RTA’98.

Since October 1997 the list of open problems is maintained as a web service. This effort is, at the moment, led by Nachum Dershowitz. The pages that you can access reflect an update of the lists presented to the RTA conferences. Currently, the list comprises 107 problems, 36 of which are solved. Note that problems marked as solved may still leave open the question of extensions or special cases.

Full text search in the problem database:

• All problems, one by one
• A compilation of all problems: [Postscript] [PDF]
• How to contribute, in particular
  • How to submit new problems.
  • How to submit a comment.
• List of recent changes.
• The bibliography:
  • The complete bibtex file The complete formatted bibliography
• The charta of the RTA List Of Open Problems.
• Maintenance of these pages.

Related Links on RTA

• The problem lists and updates as published 1998, 1995, 1993 and 1991.
• This paper, which appeared in the proceedings of RTA’05, tells the story of some selected problems.
• RTA Conferences.
• The Rewriting Home Page.

Related Lists of Open Problems

• The TLCA List of Open Problems