DEPARTMENTAL SEMINAR (COMPUTER & COGNITIVE SCIENCES) SUMMER TERM 1999 TIME AND PLACE: Thursdays 4pm (Unless otherwise stated) Lecture Room 7, School of Computer Science ORGANISER: Marta Kwiatkowska (M.Z.Kwiatkowska@cs.bham.ac.uk, ext 7264) Sammie Snow (S.Snow@cs.bham.ac.uk, ext 4774) SPEAKERS and TITLES -- Mon 19 Apr Prof. dr. John-Jules Charles Meyer, Utrecht University The KARO Framework for Specifying Intelligent Agents *5pm LR7* -- Fri 23 Apr Edmund Furse, University of Glamorgan Programming by Imitation -- Thu 29 Apr Dr Peter Wallis, University of Bath Decribing Something Complicated -- Thu 6 May Prof. Tony Hey, Dept of Electronics and Computer Science, University of Southampton: Quantum Computing: An Introduction -- Thu 13 May Dr Alex Yakovlev, University of Newcastle upon Tyne Petri nets and asynchronous hardware design -- Thu 20 May Prof. Chris Hankin, Imperial College Principles of Program Analysis -- Thu 27 May Dr Manfred Kerber, University of Birmingham Beyond Incompleteness *Postponed till later date* Dr Jeremy Wyatt, University of Birmingham Skinner's ghost: robots that learn from rewards -- Thu 3 Jun Dr Geoff Barnbrook, Department of English, University of Birmingham How we say what we mean: parsing Cobuild definitions -- Wed 9 Jun *Note different day*, 4pm LR7 Dr Miklos Cserzo, School of Biochemistry, University of Birmingham Bioinformatics: when biology meets computer science ABSTRACTS ----------------------------------------------------------------------------- -- Mon 19 Apr Prof. dr. John-Jules Charles Meyer, Utrecht University The KARO Framework for Specifying Intelligent Agents *5pm LR7* The KARO framework is a blend of various modal logics for describing the informational and motivational attitudes of intelligent agents. It comprises the agent's (manipulation of) knowledge, belief, wishes and goals, as well as the results of performing actions (and having ability and opportunity to do so). A core part of the logic consists of dynamic logic which is a logic for reasoning about actions. Special actions in our framework include belief revision and commitment actions, both modifying the mental state of an agent, the former with respect to its beliefs, the latter regarding its agenda. ----------------------------------------------------------------------------- -- Fri 23 Apr Edmund Furse, University of Glamorgan Programming by Imitation The nature of imitation learning in humans and animals is an active area of research in psychology, but with most of the focus on the question of which species are able to imitate. This research focuses on the nature of imitation learning from a Cognitive Science perspective. A model of imitation learning known as LAWE (Learning Algorithms from Worked Examples) has been developed in the area of paper and pencil algorithms. This limited domain makes it easier to develop a computational model, but nevertheless is rich enough for useful applications. LAWE can be considered an example of Programming by Demonstration (PBD) which enables naive end users to program by means of a simple demonstration of examples. Unlike other work, LAWE is inspired by a cognitive model of imitation learning, and needs no feedback from the user apart from the initial demonstration. According to the LAWE model, imitation is based upon four stages: 1. the segmentation of the events. 2. the explanation of the events using spatial relations 3. the recognition of repeat patterns 4. the merging of examples LAWE is believed to be capable of learning any terminating algorithm with at most one repeat, and current research is aimed at extending this to two repeats. Most human algorithms use a maximum of two repeats. LAWE can, in principle, learn algorithms as complex as long division and matrix inversion in a few minutes. ----------------------------------------------------------------------------- -- Thu 29 Apr Dr Peter Wallis, University of Bath: Decribing Something Complicated Most of the detailed technical work relating to software production involves using or manipulating descriptions written in more or less formal languages. Examples of such descriptions are programs, software specifications, technical manuals, project documentation and detailed descriptions of programming languages. Since these descriptions deal with extremely complicated artifacts, a universal problem with them is that they tend to be very hard to understand in their entirety. The usual response to such concerns is to "modularise" the description in some way to render it less opaque, but previous work on modularisation criteria relies largely on ad hoc techniques. My talk will introduce a long-standing personal research project that has as its eventual aim the study of modularisation issues in ways that are quite independent both of the particular artifact being described and of the structuring capabilities of the formal language used to describe it. The eventual aim is to find a way of formally studying existing ways of modularising formal descriptions and perhaps to suggest new ones. The origins, present status and long-term aims of the project will be described, with examples drawing on a very varied collection of descriptions in keeping with the generic approach being adopted. The two most technically detailed examples presented were developed in recent joint work with Steve Riddle. A small amount of relevant mathematics will be introduced: the only prerequisites will be very elementary predicate calculus and finite set theory. ----------------------------------------------------------------------------- -- Thu 6 May Prof. Tony Hey, Dept of Electronics and Computer Science, University of Southampton: Quantum Computing: An Introduction After some remarks on the fundamental physical nature of information, Bennett and Fredkin's ideas of reversible computation are introduced. This leads on to the suggestions of Benioff and Feynman as to the possibility of a new type of essentially 'quantum computers'. If we can build such devices, Deutsch showed that 'quantum parallelism' leads to new algorithms and new complexity classes. This is dramatically illustrated by Shor's quantum algorithm for factorization which is polynomial in time in contrast to algorithms for factorization on a classical Turing computer. This discovery has potentially important implications for the security of many modern cryptographic systems. The fundamentals of quantum computing are then introduced - reversible logic gates, qubits and quantum registers. The key quantum property of 'entanglement' is described, with due homage to Einstein and Bell. As an illustration of a quantum program, Grover's database search algorithm is described in some detail. After all this theory, the status of experimental attempts to build a quantum computer is reviewed: it will become evident that we have a long way to go before we can factorize even small numbers. Finally, we end with some thoughts about the process of 'quantum compilation' - translating a quantum algorithm into actual physical operations on a quantum system - and some comments on prospects for future progress. ----------------------------------------------------------------------------- -- Thu 13 May Dr Alex Yakovlev, University of Newcastle upon Tyne Petri nets and asynchronous hardware design Asynchronous circuits, which operate without use of a global clock, and as such offer a number of potential advantages that will be crucial for future microelectronic systems, such as robustness to technology variations, low power consumption to name but a few, are becoming a commercial reality. The first products with asynchronous ICs are being sold by Philips (see http://www-us.semiconductors.com/pip/PCA5007H). They have been designed with a Philips-owned design tool, called Tangram. Tangram's theoretical underpinning is a CSP-like specification notation, which makes the process of designing asynchronous circuits be somewhat analogous to concurrent programming. The VLSI circuit comes out of this process as a silicon ``image'' of a programme structure. Petri nets have their own tradition of being in a friendly and stable relationship with asynchronous circuit design. Can Petri nets be as successful as CSP and Tangram? Can they offer additional benefits? In the first half of the talk we overview the main areas of use of Petri nets in asynchronous hardware design, including various aspects of circuit modelling, verification and synthesis. In the second half we look at an example of a design of a control logic for a counterflow pipeline. A crucial part in this exercise is to synthesise a circuit-implementable Petri net specification from a transition system. We show the effective role of theory of regions in achieving the target. We discuss some `difficult' issues of semantic compatibility between asynchronous circuits and their Petri net models, including notions of arbitration and timing. ----------------------------------------------------------------------------- -- Thu 20 May Prof. Chris Hankin, Imperial College Principles of Program Analysis Program analysis is a collection of techniques for statically determining properties of programs. Such properties might be used for optimisation purposes, verification or debugging. Our particular approach is semantics-based; this enables us to verify the results of analyses and ensures that transformations based on the results are semantics-preserving. The first part of the seminar is a high-level tutorial of the field and presents a number of applications. The second part of the seminar will present some recent work based on Game Semantics (joint work with Pasquale Malacaria). ----------------------------------------------------------------------------- -- Thu 27 May Dr Manfred Kerber, University of Birmingham Beyond Incompleteness ABSTRACT: One of the key arguments for saying that the traditional AI approach cannot achieve the goal of explaining the human mind is based on Goedel's incompleteness theorem. This so-called Lucas-Penrose argument relies on the fact that any reasoning program which is powerful enough to deal with arithmetic is incomplete and cannot derive a sentence that can be paraphrased as "This sentence is not provable"; since humans would have the ability to directly see the truth of this sentence, humans and computers would have obviously different mental capacities. In this talk I try to refute this argument by firstly relating the incompleteness of logical calculi to the incompleteness of the rational numbers, secondly discussing completions in the one and the other case by admitting infinite objects, and thirdly obtaining finite representations of (some) infinite objects by compression. *Postponed till later date* Dr Jeremy Wyatt, University of Birmingham Skinner's ghost: robots that learn from rewards Over the past few years there has been a lot of interest in trying to automatically program robots using performance measures like reward functions. These methods while elegant and general typically require large amounts of experience, leading to slow learning. To speed convergence generalisation, directed exploration and teaching are often used. In this talk I will outline some of the particular issues that arise when employing these techniques on robot tasks. This describes work in progress. ----------------------------------------------------------------------------- -- Thu 3 Jun Dr Geoff Barnbrook, Department of English, University of Birmingham How we say what we mean: parsing Cobuild definitions In the process of defining their headwords, dictionary definitions provide a great deal of linguistic information about them. The Cobuild range in particular construct their definitions in the form of full sentences, which contain both explanations of the meanings of the headword and illustrations of some aspects of their typical usage. A parser has been developed which can extract the information contained in these definition sentences for use elsewhere. It uses the restrictions inherent in the purpose of the definition sentences and the format associated with it to enable a structural analysis to be performed, identifying the main elements of the definition. The prototype version of the Parser works on the Student's Dictionary, and its range is currently being extended to cover the Second Edition of the main Cobuild dictionary. This paper describes the main elements of its development and operation, together with its potential applications. ----------------------------------------------------------------------------- -- Wed 9 Jun *Note different day*, 4pm LR7 Dr Miklos Cserzo, School of Biochemistry, University of Birmingham Bioinformatics: when biology meets computer science A general introduction to biological databases, algorithms, tools and open problems of the field. -----------------------------------------------------------------------------