TDDB40 Introduction to Rewriting Systems, ECTS-points
/INTRODUKTION TILL OMSKRIVNINGSSYSTEM/

Advancement level:
D

Aim:
Any kind of computation can be seen as a rewriting process. The aim of the course is to give a uniform view of various rewriting systems and in this way provide a unified basis for studying and classifying various computing paradigms.

Prerequisites:
TDDA89 Formal Languages and Automata Theory TDDA41 Logic Programming

Course organization:
Lectures

Course content:
- Abstract Rewriting Systems - Functional computation as rewriting. Term rewriting. Lambda calculus and combinatory logic. Abstract data types - Computing relations through rewriting. Generalisation of context-free grammars to logic programs, attribute grammars and two-level grammars. This gives a uniform approach to computation of type 0, type 1 and type 2 languages. - Defining semantics of programming languages through rewriting systems. - Integration of functional and relational languages. Equational unification and narrowing.

Course literature:
Lecture Notes, Johan Boye and Jan Maluszynski "Rewriting Systems"

UPG1Hand-in assignments and activ participation
Course language is Swedish.