Term Rewriting Systems
(V3 resp. 4 + Ü2, SS 2011)
|
|
News
- A new version of the course notes is available, where some small errors have been fixed.
-
We have posted the exam of August 17, 2011,
along with a solution proposal.
-
The results of the exam of Wednesday, August 17, 2011,
after the inspection are now available in the
exercise management system
as Exercise -1.
You can use the following mapping from points to grades
to determine your final grade:
- 95 .. 120 points: 1.0
- 90 .. 94.5 points: 1.3
- 85 .. 89.5 points: 1.7
- 80 .. 84.5 points: 2.0
- 75 .. 79.5 points: 2.3
- 70 .. 74.5 points: 2.7
- 65 .. 69.5 points: 3.0
- 60 .. 64.5 points: 3.3
- 55 .. 59.5 points: 3.7
- 50 .. 54.5 points: 4.0
- 0 .. 49.5 points: 5.0
Some statistical data on the
obtained points and on the
obtained grades is available, too.
-
The exam inspection is scheduled for Thursday, August 25, 2011
from 2:00 pm to 3:00 pm.
It will take place in room 4201b (seminar room i2)
in the computer science building
at Ahornstraße 55.
Please bring your student ID and a valid document to prove your identity
(passport or national ID card) to the inspection!
-
The results of the exam of Wednesday, August 17, 2011,
are now available in the
exercise management system
as Exercise -1.
You can use the following mapping from points to grades
to determine your final grade:
- 95 .. 120 points: 1.0
- 90 .. 94.5 points: 1.3
- 85 .. 89.5 points: 1.7
- 80 .. 84.5 points: 2.0
- 75 .. 79.5 points: 2.3
- 70 .. 74.5 points: 2.7
- 65 .. 69.5 points: 3.0
- 60 .. 64.5 points: 3.3
- 55 .. 59.5 points: 3.7
- 50 .. 54.5 points: 4.0
- 0 .. 49.5 points: 5.0
Some statistical data on the
obtained points and on the
obtained grades is available, too.
-
The exam will take place at lecture hall AH 3 on
Wednesday, August 17th, 2011, at 1:30 pm for all
students. The exam will take 120 minutes. Please
be at the lecture hall on time!
There are no aids or auxiliary materials allowed for the exam.
Just bring a document-quality pen (not red or green), a valid
document to prove your identity (i.e., passport or
Personalausweis) and your student ID. Your resulting
grade for the exam will also be your final grade for the
whole course.
-
We have posted two old exams on term rewriting lectures
on this website which you can use to practice for our exam.
-
In order to be qualified for the written exam for Master and Bachelor
students, you must obtain at least 72.5 exercise points in total.
- The exercise courses on June 29 and July 6 are still relevant for all students. But the remaining lectures (from July 1 onwards)
are only needed for the 4-hour-version of the lecture. So they are
relevant for Diploma students, but they will not be part of the exams for Master and Bachelor students.
- If you want to attend the remaining lectures in July, please send an e-mail to Prof. Giesl
by Thursday, June 30, noon.
- If you want to solve exercise sheets for the remaining lectures in July, please send an e-mail to
tes11@i2.informatik.rwth-aachen.de by Thursday, June 30, noon.
- In the winter semester 2011/2012 we will offer two seminars related to the lecture:
Every participant of the current lecture is highly welcome to register for these seminars. Registration is possible at
http://web-info8.informatik.rwth-aachen.de/apse until July 3.
This is a 3-hour lecture for the following students (counting as 6 ECTS for students of computer science and SSE, and as 7 ECTS for students of mathematics):
- Master Informatik
- Master Software Systems Engineering
- Master Mathematik
- Bachelor Informatik
- Since this is an "introductory Master course", it can also be attended as
a "Bachelor-Wahlpflichtveranstaltung" (Theory) for students of Bachelor Informatik.
- It is also possible to attend this lecture already as a student of
Bachelor Informatik and to transfer the credits afterwards when enrolling in
the Master Informatik program.
This is a 4-hour lecture for the following students:
- Diplom Informatik
- Diplom Mathematik
Compared to the 4-hour lecture, the following material is missing
in the 3-hour lecture:
- Section 3.2 (congruence closure)
- Section 5.1 from Lemma 5.1.3 onwards (unification algorithm)
- Section 5.3 (confluence without termination)
- Section 6.3 (implicit induction)
If you have any questions, please contact the mailing list tes11@i2.informatik.rwth-aachen.de,
which is read by the three teaching assistants. More contact information can
be found on the homepage of LuFG I2.
Course Notes
The course notes are available here (in German): Course Notes (Version of September 22, 2011)
Contents
Term rewriting systems are used for computations and mechanized proofs with
equations. All functional programming languages are based on term
rewriting systems, too. Therefore, term rewriting systems are used
in many areas like mechanized program verification, specification
of programs and declarative programming. The following questions
will be discussed in the course.
- Is the result of a computation always unique (confluence)?
- Does a computation always stop after a finite number of steps (termination)?
- Does a program fulfill its specification (correctness)?
- How can the completion of an incomplete program be handled automatically?
Language
The course is given in English or German.
References
- J. Avenhaus. Reduktionssysteme. Springer-Verlag, 1995.
- F. Baader und T. Nipkow: Term Rewriting and All That, Cambridge University Press, 1998.
- R. Bündgen: Termersetzungssysteme, Vieweg, 1998.
- N. Dershowitz and J.-P. Jouannaud. Rewrite Systems. Handbook of Theoretical Computer Science, Vol. B, Chapter 6: Formal Methods and Semantics, J. van Leeuwen (ed.), North-Holland, pp. 243-320, 1990.
Area
Theoretical Computer Science, Area of Specialization
Here you find two exams from the 2004 and the 2006/2007 lectures on
term rewrite systems (in German). However, as the computer science
curriculum has been changed since these exams took place, the
conditions for these exams were different from the ones for the
exam we will have in this lecture. First, the old exams were not
designed to determine the final grade for the term rewrite systems
course, but only for the acquisition of the Übungsschein.
Second, they only took 90 minutes, while our exam will take 120 minutes.
Third, the exams covered the V4 version of the lecture, whereas for
this course the written exam will cover the V3 version of the lecture.
Keep these differences in mind when practicing with the old exams.
Furthermore, we strongly recommend that you solve the old exams
without looking into the solutions first and that you also respect
the time limit of 90 minutes.
The exam on the 2011 lecture is now available, too. The time limit
for the exam was 120 minutes.
For students of Diplom Informatik and Diplom Mathematik: To get a certificate for this course
(Übungsschein) you must reach at least 50% of the points on the exercise
sheets. In general, we advise all Diploma students to work towards the certificate.
Working on the exercises is a good preparation for the final oral exam.
For all other students 50% of the points on the exercise sheets are
needed in order to take part in the final exam.
In order to take part in the exercises, please sign
up here.
The exercise sheets can be downloaded here.
- Exercise 1,
Solution 1
- Exercise 2,
Solution 2
- Exercise 3 (English), Exercise 3 (German),
Solution 3
- Exercise 4,
Solution 4
- Exercise 5,
Solution 5
- Exercise 6,
Solution 6
- Exercise 7,
Solution 7
- Exercise 8,
Solution 8
- Exercise 9,
Solution 9
- Exercise 10,
Solution 10
- Exercise 11,
Solution 11
Here are the transparencies used in the lecture.
- Transparency 1 (April 8, 2011)
- Transparency 2 (April 11, 2011)
- Transparency 3 (April 15, 2011)
- Transparency 4 (April 15, 2011)
- Transparency 5 (April 18, 2011)
- Transparency 6 (April 29, 2011)
- Transparency 7 (April 29, 2011)
- Transparency 8 (May 2, 2011)
- Transparency 9 (May 6, 2011)
- Transparency 10 (May 6, 2011)
- Transparency 11 (May 13, 2011)
- Transparency 12 (May 13, 2011)
- Transparency 13 (May 13, 2011)
- Transparency 14 (May 16, 2011)
- Transparency 15 (May 23, 2011)
- Transparency 16 (May 23, 2011)
- Transparency 17 (June 6, 2011)
- Transparency 18 (June 6, 2011)
- Transparency 19 (June 8, 2011)
- Transparency 20 (June 10, 2011)
- Transparency 21 (June 10, 2011)
- Transparency 22 (June 20, 2011)
- Transparency 23 (June 20, 2011)
- Transparency 24 (June 20, 2011)
- Transparency 25 (July 1, 2011)
- Transparency 26 (July 4, 2011)
- Transparency 27 (July 8, 2011)
- Transparency 28 (July 11, 2011)
There will be a written exam on
the lecture. It takes place on
August 17, 2011. The second written exam will take place on September 26, 2011.
Registration for the Exam
- Students of Master Informatik, Master SSE, and Master Mathematik should have registered
for the exam via CampusOffice. The deadline for their registration was May 20, 2011.
- Students of Bachelor Informatik and Bachelor Mathematik should register by e-mail to
tes11@i2.informatik.rwth-aachen.de. The deadline for their registration is July 1, 2011.
