Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2006
EATTK 2006

11th Estonian Winter School in Computer Science (EWSCS)
XI Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 5-10, 2006

under the auspices of European Educational Forum

Jan Bergstra

Instituut voor Informatica
Universiteit van Amsterdam
Amsterdam, The Netherlands

From Program Algebra to Thread Algebra


A family of program algebras for imperative programming is presented together with some applications on programming language semantics, related to sequential OO programs. The meaning of a program is defined to be a thread. Threads themselves are organised in thread algebras. Thread algebras can be equipped with strategic interleaving operators and a series of such operators is developed. Examples of the use of strategic interleaving are given, in particular in connection with deadlocks occurring in multi-threaded OO program notations.

Maurer computers are introduced following a forgotten but promising proposal by W. D. Maurer from 1967. The action of threads and multi-threads on Maurer computers is analysed in detail. A perspective on the use of these techniques for microprocessor research is given.

Finally thread algebra is used to shed some new light on a classical observation by F. Cohen, who introduced the concept of a computer virus, dating from 1984: it is undecidable whether or not a program is a virus. This observation is formalized in thread algebra and now the diagonalization on which the observation of Cohen was based disappears and a number of positive results are found.

Course materials

About the Lecturer


Modified Apr 09, 2006 0:06 by ewscs06(at)