Estonian Winter Schools in Computer Science
Eesti arvutiteaduse talvekoolid
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.
Modified Apr 09, 2006 0:06 by ewscs06(at)cs.ioc.ee