185.224 Term Rewriting Systems
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2023S, VU, 2.0h, 3.0EC, to be held in blocked form


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to understand the basics of term rewrite systems as well as selected advanced topics. The foundations at least amout to (i) (i) Abstract Rewrite Systems; (ii) (First-Order) Term Rewrite Systems; (iii)  Completion, Complexity, Confluence and Termination, as well as some selected topics of advanced material.

Subject of course

The following topics are discussed:


(i)  Abstract Rewrite Systems: definitions, properties, Newman's Lemma, commutation, strategies; (ii) (First-Order) Term Rewrite Systems: definitions, properties, equational reasoning, word problem; (iii)  Completion, Complexity, Confluence and Termination: critical pair lemma, Gröbner basis, derivational complexity, connection to subrecursive hierarchies, (beyond) orthogonality, decreasing diagrams, polynomial and matrix interpretations, dependency pairs.

Advanced Topics.

Probabilistic Term Rewriting

Teaching methods

The course is taught in English and will be held online, with all supporting materials (lecture notes, slides, recordings) available till end of June and an (online) discusson forum from September 18 to 22. During the forum, selected exercises will be discussed and further information to topics of special interest will be provided. Supporting material, slides, recordings, as well exercises will be made available on TUWEL. Please register timely for the course.

Mode of examination


Additional information

The course is partly based on the following lecture notes:

  • Term Rewrite Systems, Aart Middeldorp, lecture notes, University of Innsbruck.

Additional material can also be found on the course homepage.



Examination modalities

Evaluation of exercises and discussion.

Course registration

Begin End Deregistration end
13.02.2023 00:00 06.07.2023 23:59



No lecture notes are available.