Rewriting Systems (TDDB40)

Lectures:
28 h

Recommended for
Ph. D. students in Computer Science and Computer Systems.

The course was last given:
Fall 1997

Goals
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. The practical relevance of the presented concepts will be illustrated: (1) by some known formalisms for defining operational semantics of programming languages and (2) by a currently developed programming language integrating functional programming with logic programming.

Prerequisites
Some knowledge of discrete mathematics.

Organization
The course will consist of lectures, and seminars (for more details see home page http://www.ida.liu.se/~janma/rewr.html). Examination in the form of seminar presentations and obligatory homework. The course is offered also for C-line students as TDDB40.

Contents
Abstract Rewriting Systems.
Functional computations as rewriting. Term rewriting. Lambda calculus and combinatory logic as examples of rewriting systems.
Computing relations through rewriting. Generalisation of context-free grammars to logic programs, attribute grammars and two-level grammars.
Defining operational semantics of programming languages in terms of rewriting.
Equational unification. Integration of functional and relational languages.

Literature
Johan Boye, Jan Maluszynski, Ulf Nilsson Rewriting Systems
These draft lecture notes under revision are available on the net.

Some existing slides are accessible. They may be subject of revision. Batch 1 concerns term rewriting and narrowing. Batch 2 gives a unified view of various grammatical formalisms and logic programming.

A seminar on Constraint Logic Programming will be based on the paper: J. Jaffar and M. Maher. Constraint Logic Programming: A Survey, J. Logic Programming 19-20, 1994

The view of computation as rewriting may be used for integration of the declarative programming paradigms: functional programming and logic programming. A seminar on this topic will be based on the material of the tutorial given by Michael Hanus in October 1997 at ILPS'97 conference. Example of such a language is the functional logic programming language Curry , which is being developed by an international group of researchers led by Michael Hanus. One can try Curry on the net.

Teachers
Jan Maluszynski.

Examiner
Jan Maluszynski.

Schedule
October 1999 - January 2000.

Examination
One homework assignment.
A contribution to a seminar.

Credit
4 credits

Page responsible: Director of Graduate Studies