BRICS Notes Series, Abstracts, 1995

March 22, 2004

This document is also available as PostScript and DVI.

References

[NS-95-6] Aravind Srinivasan.

The Role of Randomness in Computation. November 1995. iv+99 pp. Abstract: The course was intended to serve both as a tutorial in-

troduction to the role of randomness in computation, specifically in algorithms and complexity, and as a forum for the discussion of the most recent research in the area. The course was organised into a sequence of 6 lectures:

1. Introduction,

2. Randomness in Distributed Computing,

3. Derandomisation,

4. Random Sampling,

5. The Lovasz Local Lemma,

6. Weak Random Sources.

In addition, the course was supplemented by a talk on “Improved Approximation Algorithms for Packing and Covering Problems”.

[NS-95-5] Robert Paige.

Analysis and Transformation of Set-Theoretic Languages. Mini-

Course. August 1995. iv+157 pp. Abstract: The course was on how types and transformations can be

used to integrate algorithm design and analysis, program development, and high level compilation of set theoretic programming languages. Topics:

• Introduction to SETL and sources of inefficiency; program improvement by finite differencing,

• Program improvement by real-time simulation of a typed set machine (equipped with high level input/output) on a RAM, • Reconstruction and extension of the linear time fragment of

Willard’s database predicate retrieval theory,

• Design of A linear time fixed point language; experiments in productivity of algorithm implementation.

.

[NS-95-4] PostScript.

Yuri Gurevich and Egon Brger. Evolving Algebras. Mini-Course. July 1995. iv+222 pp. Abstract: Professors Egon Brger (Univ. of Pisa) and Yuri Gurevich

(Univ. of Michigan) visited BRICS during August 1995. From 7– 10 August they held an intensive mini-course of 14 double lectures on Evolving Algebras: their framework for modelling algorithms and languages, with links to both Complexity Theory and Semantics. The background and interests of both lecturers fitted particularly well with the BRICS idea of synergy between Algorithms and Complexity Theory, Semantics, and Logic. The course was attended by 12 PhD students. Gurevich’s lectures on the basic concepts and definitions of evolving algebras were all prepared specially for the course, and supported by a large collection of papers from the literature. Brger’s lectures on applications of evolving algebras were based on some of his latest papers. The course was organized by Peter D. Mosses. BRICS is very grateful to the lecturers for their efforts, during what turned out to be quite a hot week!

[NS-95-3] PostScript, DVI. Andrew D. Gordon. Bisimilarity as a Theory of Functional Programming. Mini-Course. July 1995. iv+59 pp. Abstract: Operational intuition is central to computer science.

These notes introduce functional programmers to operational semantics and operational equivalence. We show how the idea of bisimilarity from CCS may be applied to deterministic functional languages. On elementary operational grounds it justifies equational reasoning and proofs about infinite streams.

[NS-95-2] PostScript.

Uffe H. Engberg, Kim G. Larsen, and Arne Skou, editors. Proceedings of the Workshop on Tools and Algorithms for The Con-

struction and Analysis of Systems, TACAS (Aarhus, Denmark, 19–20 May, 1995), May 1995.

vi+334 pp. Selected papers appears in Brinksma, Cleaveland, Larsen, Margaria and Steffen, editors, Tools and Algorithms for The Construction and Analysis of Systems: International Workshop, TACAS ’95 Selected Papers, LNCS 1019, 1995.

Abstract: The aim of the workshop on Tools and Algorithms for the Construction and Analysis of Systems, TACAS, is to bring together researchers and practitioners interested in the development and application of tools and algorithms for specification, verification, analysis and construction of distributed systems. The overall goal of the workshop is to compare the various methods and the degree to which they are supported by interacting or fully automatic tools. The 23 papers of the proceedings cover the following topics: refinement-based verification and construction techniques; compositional verification methodologies; analysis and verification via theorem-proving; decision procedures for verification and analysis; specification formalisms, including process algebras and temporal and modal logics; analysis techniques for real-time and/or probabilistic systems; approaches for value-passing systems, tool sets for verification and analysis case studies. There were special sessions for demonstration of verification tools.

[NS-95-1] PostScript. Igor Walukiewicz. Notes on the Propositional μ-calculus: Completeness and Related Re-

sults. February 1995. 54 pp. Abstract: In this notes we consider propositional μ-calculus as in-

troduced by Kozen. The main purpose of these notes is to present the completeness proof of the Kozen’s axiomatisation of the μcalculus. To achieve this goal we develop tools which allow us to give relatively simple proofs of results for the logic like:

• syntactic characterisation of satisfiability and validity,

• small model theorem,

• decidability,

• equivalence of the μ-calculus over binary trees and Rabin automata,

• a notion of disjunctive formula and the proof that every formula is equivalent to a disjunctive formula,

• linear satisfiability checking algorithm for disjunctive formulas.

These notes are intended to supplement a 6 hours course given in February 1995 at BRICS centre.