Term Rewriting Systems

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

Prof. Dr.-Ing. Franz Baader

Course Description

Term rewriting systems can be used to compute in structures that are defined by equations. They are thus an important tool in automated deduction, algebraic specification, and functional programming. The course introduces important properties such as termination and confluence in the framework of abstract reduction systems, gives a brief introduction into universal algebra, and then concentrates on confluence, termination, and completion of term rewriting systems.

Prerequisites: Basic notions from a course on discrete algebraic structures would be helpful.

Organization

The lecture takes place twice a week in room E05: Tuesday 16:40-18:10 and Thursday 16:40-18:10.

Exercise Group

The exercise group will be held by Barbara Morawska. It meets on Wednesdays 11:10-12:40 in E05.

The exercises can be downloaded in Postscript format (the exercises for next week will be available on Friday at noon this week, possibly earlier):

• exercises 1
• exercises 2
• exercises 3
• exercises 4
• exercises 5
• exercises 6
• exercises 7
• exercises 8
• exercises 9
• exercises 10
• exercises 11
• exercises 12
• exercises 13
• exercises 14
• exercises 15
• exercises 16

Credits / Examinations

1. present at least four exercises in front of the exercise group;
   
   
2. pass an oral examination at the end of the term performed by Prof. Baader.

Reference

• F. Baader, T. Nipkow. Term Rewriting and All That. ISBN 0-521-77920-0, Cambridge University Press, 1998