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.
The following topics are discussed:
Foundations.
(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
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.
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.
