Stud.IP Uni Oldenburg
University of Oldenburg
25.10.2020 01:35:08
inf458 - Term Rewriting Systems (Complete module description)
Original version English Download as PDF
Module label Term Rewriting Systems
Module code inf458
Credit points 6.0 KP
Workload 180 h
Faculty/Institute Department of Computing Science
Used in course of study
  • Master's Programme Computing Science (Master) > Theoretische Informatik
  • Master's Programme Embedded Systems and Microrobotics (Master) > Akzentsetzungsmodule
Contact person
Module responsibility
Authorized examiners
Entry requirements
Skills to be acquired in this module
The objectives of this module are an introduction to (term) rewriting systems, termination and confluence, the undecidable sets of termination and confluence problems, verifcation procedures of termination and confluence

Professional competence
The students:
  • describe the basics of term rewriting systems
  • characterise the undecidability of termination and confluence problems
  • describe verification procedures of termination and confluence

Methodological competence
The students:
  • apply verification procedures of termination and confluence
  • apply Huet’s completion procedure

Social competence
The students:
  • solve problems in a team
  • present and discuss their results

The students:
  • reflect their actions with regard to term rewriting systems and the methods of those
Module contents
The module is an introduction to term rewriting systems and provides verification procedures for termination and confluence.
Term rewriting systems, termination and confluence are introduced, the undecidability of termination and confluence problems and the decidability for a set of special term rewriting systems are shown.
For this purpose reduction and simplification orders, critical pairs, orthogonality and Huet's completion procedure are introduced, examined and combined.
Reader's advisory
  • Franz Baader, Tobias Nipkow: Term Rewriting and All That. Cambridge University Press, Cambridge 1998.
  • Terese: Term Rewriting Systems, Cambridge University Press, Cambridge, 2003.
Language of instruction German
Duration (semesters) 1 Semester
Module frequency im 2-Jahres-Zyklus
Module capacity unlimited
Reference text
Modullevel AC (Aufbaucurriculum / Composition)
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Lern-/Lehrform / Type of program
Vorkenntnisse / Previous knowledge
Course type Comment SWS Frequency Workload attendance
Lecture 3.00 WiSe 42 h
Exercises 1.00 WiSe 14 h
Total time of attendance for the module 56 h
Examination Time of examination Type of examination
Final exam of module
At the end of the lecture period
exercises and oral or written exam