COMPUTER SCIENCE RESEARCH SEMINARS AUTUMN TERM 1994 Programme Coordinator: Aaron Sloman (A.Sloman@cs.bham.ac.uk) (Temporary, until a new volunteer is found) CONTENTS - (Use g to access required sections) -- 11th October: Dr Jonathan Nash -- 18th October: Prof Mathai Joseph -- 25th October: Aaron Sloman -- 1st November: No seminar -- 8th November: No seminar -- 15th November: Tom Axford -- 22nd November: Ian Ferguson Sunderland University -- 29th November: Achim Jung (Technische Hochschule Darmstadt) -- 6th December: Alan Sexton -- 13th December: No seminar (school meeting) -- 20th December: Iain Stewart (Swansea) Time/Venue: 1400hr, each Tuesday during term time, in G33. (Lecture Room 7, Aston Webb) (Occasionally a speaker is available who cannot manage the regular seminar date/time, in which case alternative arrangements can be made) All proposals for visiting speakers should be discussed with the Programme Coordinator to ensure that there is no time-table clash. Whoever invites a speaker is expected to "host" the speaker on the day, as well as obtaining a title and abstract in good time for prior circulation. The host can also take the speaker and one or two other people to lunch before the seminar and charge the cost to the School seminar budget. Travel expenses for speakers will also be covered. Do not invite anyone to travel from overseas without first discussing budgetary arrangements with the Coordinator, who will consult as necessary with the Head of School. PROGRAMME FOR THE AUTUMN TERM, 1994 -- 11th October: Dr Jonathan Nash Scalable Systems and Algorithms Group School of Computer Studies, Leeds Title: Scalable and Portable Computing using the WPRAM Model Abstract: The takeup of parallel computers has been considerably hindered by two important defficiencies. The first is the lack of a portable platform on which to base the implementation of parallel algorithms. Without this, applications need to be rewritten when moving to a new machine. The second is the lack of sufficient information on the performance of the primitives being used to write an algorithm. In particular, the performance of the primitives should scale with the number of processors in the given machine in a predictable manner. This talk describes a parallel model of computation, called the WPRAM, which aims to tackle the above deficiencies. The model is based around a shared address abstraction, but with the ability to place data locally if desired. The concurrent access and updating of shared data is also supported. The WPRAM model is aimed at the ermerging class of distributed memory message passing machines with scalable network throughput characteristics. A discrete event simulator has been written for the WPRAM, with performance figures based around the Inmos T9000 processor and C104 packet router. Examples of algorithm design and performance analysis using the WPRAM are provided through the implementation of a shared queue data type and a parallel implementation of the simplex method for linear programming. -- 18th October: Prof Mathai Joseph Computer Science Dept, Warwick Univ. Title: "Fault-tolerance by Transformation". Abstract: Software fault-tolerance can be used to attempt to deal with failures of the software due to design errors, or failures caused by faults occurring in the underlying execution platform. In this talk, I will consider how software can be specified and verified for correct execution when any of a specified set of faults can occur in the underlying platform. Such faults are typically random and tolerance to their occurrence requires proof that the program will execute correctly under any possible set of faults. I will first consider how both the program and the fault environment can be specified and show how the failure properties of the program can be derived. The program is then transformed by incorporating recovery actions and it is shown how these can be used to overcome the effects of the faults. The method is illustrated using a small example. -- 25th October: Aaron Sloman Title: Logical and non-logical representations Abstract: The talk will introduce the long standing dispute among philosophers and others about the role of logic as a language for representation and as a tool for reasoning in mathematics, programming and general problem solving -- as contrasted with the use of diagrams, pictures, 3-D models, and other more more or less ad hoc forms of representation. An example involving reasoning about programs will be discussed, and some hard unsolved problems about spatial and visual representations and processes introduced. -- 1st November: No seminar -- 8th November: No seminar -- 15th November: Tom Axford Title ----- Aladin: an Abstract Machine for Integrating Functional and Procedural Programming Abstract -------- Functional programming languages have not been very successful at mixing the functional programming approach with more conventional procedural programming. The Aladin machine is an attempt to allow the two styles to be used cooperatively without compromising the referential transparency and other key features of functional languages. This seminar will describe the Aladin abstract machine and progress with its implementation, which is still in its early stages. -- 22nd November: Ian Ferguson Sunderland University cs0rfe@isis.sunderland.ac.uk Title: "MOOSE - Large furry quadruped or Method for Object-Oriented Software Engineering ?" Abstract: Methods for Object Oriented Software Engineering proliferate but many either fail to address the complete Software Development Life cycle or omit vital parts of the OO paradigm. Work on a simple and intuitive method will be descibed along with details of its supporting CASE tool set and a novel method for encouraging software reuse. -- 29th November: Achim Jung (Technische Hochschule Darmstadt) Title: Results and future research directions in the Semantics of Programming Languages. Abstract: In Semantics of Programming Languages we try to understand better the behaviour of programs by constructing mathematical models and logical systems. Since computation on the one hand and mathematical set theory on the other are very different viewpoints, this can be rather challenging. In the talk I will try to explain the basic notions, questions, techniques, and results of Semantics. We will see some of its successes and some of the remaining riddles. Finally, I will outline some of the more promissing lines of research in this field. -- 6th December: Alan Sexton Title: A New Query Execution System for Databases Abstract: Current query execution systems use a divide and conquer approach to split up queries into a graph structure of simpler subqueries. This graph is then applied, in a dataflow style, to the data to evaluate the query. All major commercial relational database systems use this approach. However this approach causes a number of problems: dynamic execution plans, good performance in ad hoc querying, use of negative information in indices and handling skew in the distribution of the underlying data are all difficult to do in this context. In this seminar, we present an entirely new approach to query execution, also based on divide and conquer, but of the data rather than of the query, and show how, with the use of multidimensional access methods, the above mentioned problems can be attacked. Furthermore, it will be shown that this new execution approach can be combined in a natural way with more traditional methods so that the best advantages of both approaches can be obtained. -- 13th December: No seminar (school meeting) -- 20th December: Iain Stewart (Swansea) Tuesday 20th at 12 Noon in Lecture Room 7 Aston Webb Speaker: Dr. Iain Stewart (Swansea) Title: Descriptive Complexity Theory: an Introduction Abstract: "I will provide an introduction to finite model theory and descriptive complexity theory, and detail some recent important results. Finite model theory is model theory restricted to finite structures and was previously thought to be uninteresting by most logicians before close links were established with complexity theory by Ron Fagin in 1974, and descriptive complexity theory is that branch of finite model theory dealing with the explicit relationship between logic and complexity theory. Descriptive complexity theory seeks to classify problems according to how easy they are to describe in some logic as opposed to how much computational resource they require for their solution on some model of computation (there are, however, very close links between the two approaches). I will also mention applications in and links with other areas of computer science and mathematics such as database theory, logic programming and random graph theory. The talk will be aimed at the novice in the field." Dr Stewart will make sure the talk will be accessible to a varied audience. Some mathematicians, especially those with a logical bent, might find it interesting.