Chair in Theoretical Computer Science

REF : 306712

Further Particulars


The University invites applications for a Chair in Theoretical Computer Science, to be held within the Division of Informatics.  We seek a candidate who will further develop the strengths of the Division and its Laboratory for Foundations of Computer Science (LFCS).  Example areas of interest are logic and proof, concurrency, programming languages and semantics, complexity and algorithms and formal development of programs and systems.  Applicants from other theoretical areas and applicants whose interests connect the theory of computation with other parts of informatics are also invited to apply.

In addition to outstanding strength in research and scholarship, the successful candidate should provide leadership and inspiration for fundamental research, encourage the integration of his/her own research with that of others and play an active role in teaching and administration.

The appointment is full­time, the salary will be within the normal professorial salary range and the person appointed will be required to retire at the end of the academic year in which he/she reaches the age of 65. The appointee will be, ex-officio, a member of Senatus and Faculty.

The Division of Informatics

Informatics is the study of information and computation whether in natural or in artificial systems. It comprises a vast range of scientific and engineering endeavour and has enormous economic and social impact.

In order to achieve a concerted and systematic approach to its advancement, the University of Edinburgh formed the Division of Informatics in August 1998. This brought together the former Departments of Artificial Intelligence, Cognitive Science and Computer Science (which included LFCS), together with the Artificial Intelligence Applications Institute. The Division possesses a combination of breadth and strength unparallelled elsewhere in the UK and competitive world­wide; as an intellectual endeavour it is strikingly original.

There is activity in informatics throughout the University, with the Division representing the central scientific and engineering activity in the subject. There is a rich variety of other effort within the Faculty of Science and Engineering; and other Faculties have their own interest, particularly Medicine, Arts and Social Sciences.

The Division (as previously constituted) achieved a 5 rating in the last RAE round; it had by far the largest number of research­active staff and the highest per capita research income in its unit of assessment. It currently has 66 faculty and 62 contract research staff (of whom 100 are Category A), as well as 70 support staff of various categories. Research and teaching are organised separately within the Division, with a strong centrally managed support organisation . It has an annual teaching income of (around) £2.4 million and research income of £5.6 million (of which £2.4 million is non­SHEFC). There are seven established Chairs; one is that presently advertised and the others are currently held by: Professors Bishop, Brebner, Fourman, Ibbett, Moore, and Steedman. Eight further Chairs are held by: Professors Bundy, Plotkin, Sannella, Stenning, Stirling, Tate, Webber, and Willshaw.

Research in Informatics

Informatics studies the representation, processing and communication of information in natural and artificial systems. The central notion is the transformation of information---whether by computation or communication, whether by organisms or artifacts. Understanding informational phenomena---such as computation, cognition, and communication---enables engineering and technological advances of major economic and social importance. In turn, technological progress and demands prompt
scientific enquiry.

In natural and artificial systems, information is carried at many levels, ranging, for example, from biological molecules and electronic devices through nervous systems and computers and on to societies and large-scale distributed systems. It is characteristic that information carried at higher levels is represented by informational processes at lower levels. Each of these levels is the proper object of study for some discipline of science or engineering. Informatics aims to develop and apply firm conceptual, theoretical and technological foundations for the study, analysis and design of a wide variety of computational

Informatics has many aspects and encompasses a number of existing academic disciplines - artificial intelligence, cognitive science and computer science. Each takes part of informatics as its natural domain: in broad terms, cognitive science concerns the study of natural systems; computer science concerns the analysis of computation, and design of computing systems; artificial intelligence plays a connecting role, designing and analysing systems which emulate those found in nature. Informatics also informs and is informed by other disciplines, such as Mathematics, Electronics, Biology, Linguistics and Psychology. Thus informatics provides a link between disciplines with their own methodologies and perspectives, bringing together a common scientific paradigm, common engineering methods and a pervasive stimulus from technological development and practical application.

Divisional Research is carried out within Institutes; as well as research they are responsible for training doctoral students.

There are seven institutes altogether:

AIAI, the Artificial Intelligence Applications Institute
IANC, the Institute for Adaptive and Neural Computation
ICCS, the Institute for Communicating and Collaborative Systems
ICSA, the Institute for Computing Systems Architecture
IPAB, the Institute of Perception, Action and Behaviour
IRR, the Institute for Representation and Reasoning
LFCS, the Laboratory for Foundations of Computer Science

AIAI promotes and expedites the application of research in artificial intelligence for the benefit of industry, commerce, government and academia. AIAI's applied research addresses planning and activity management, knowledge­based systems and knowledge management, and adaptive systems. IANC fosters the study of adaptive processes in both artificial and biological systems; two themes are the study of artificial learning systems and the analysis and modelling of brain processes. ICCS pursues basic research into the nature of communication among humans and between humans and machines, using text, speech and graphics, and the design of interactive dialogue systems, using computational and algorithmic approaches.

ICSA seeks development of a better understanding of systems components, both hardware and software, and their integration and interaction; this involves not only improving their raw performance and cost-effctiveness, but also making them more connectable and interoperable, more reliable, more usable and more applicable. The interests of IPAB are how to link, in theory and in practice, computational perception, representation, transformation and generation processes to external worlds---whether real or virtual. The intellectual focus of IRR is the study of representation and reasoning in natural and artificial computation systems, through formal theory, empirical studies, cognitive modelling and real­world applications. The mission of LFCS is to achieve a foundational understanding of problems and issues arising in computation and communication through the development of appropriate and applicable formal models and mathematical theories.

As well as Institutes there are a number of Programmes spanning Institutes; currently there are active Programmes in Bioinformatics, Software Engineering and System Level Integration. It is a characteristic of the Division that it can readily form new Programmes to deal with topics of current interest involving staff with a wide variety of appropriate skills from several
Institutes. It is anticipated that some programmes may evolve into independent institutes.

Bioinformatics includes research within Informatics, Biology and Biomedicine. It investigates a wide spectrum of problems concerning, for example, gene regulation and embryo development, or the development and functioning of specific neural structures. Software Engineering applies a wide range of methodologies and techniques: empirical studies; applications of AI techniques, computer science, mathematics and cognitive science.System Level Integration makes possible new forms of system, integrating transduction, computation and communication on a single chip; the design, analysis and correct
implementation of such SLI devices presents novel research challenges.

Finally, there are a number of Interdisciplinary Collaborations in which the Division has involvement. The Human Communication Research Centre (an ESRC­initiated Interdisciplinary Research Centre) links the Division, the Departments of Linguistics and Psychology, and the Universities of Durham and Glasgow. The Institute for System Level Integration links the Division, the Department of Electrical Engineering, and Glasgow, Heriot­Watt and Strathclyde Universities. Within the University, the Division has involvement in the Edinburgh Virtual Environment Centre, the Maxwell Institute, the Centre for Neuroscience, and the Centre for Speech Technology Research. The Division is taking part in two successful bids for EPSRC Interdisciplinary Research Centres: Advanced Knowledge Technologies and Dependability of Computer­Based Systems; the former also involve the Open University and the Universities of Aberdeen, Sheffeld and Southampton; the latter, City University and the Universities of Lancaster, Newcastle and York.

The Laboratory for Foundations of Computer Science

The primary aim of research in LFCS is foundational: to develop mathematical theories adequate for modelling and reasoning about computational systems and concepts of all kinds. At the same time, there is an experimental dimension to the work of LFCS: theories are embodied in formal notations, languages and software tools. In this way, the applicability and usefulness of the theories can be tested, and the ideas developed in foundational work can be disseminated to a wider community of

LFCS was founded in 1986 and itself builds on a long previous history of foundational research at Edinburgh. Its key strengths are: exceptional critical mass of leading international researchers in permanent positions, deep and long­lived intellectual traditions which give it stability and coherence, and a very strong international reputation, which continues to attract talented people at all levels, from Ph.D. students to post­docs, lecturing staff and visitors. LFCS currently has 18 lecturing staff (4 joint with other Institutes), 12 Contract Research Staff and 20 Ph.D. students; its annual grant income is a little over £1 million.

LFCS has a Director, there is also a Deputy Director. They receive the support of a small administrative team under the direction of a Service Manager. The Director is advised by a small group (the ``Director's Meeting'') consisting of two elected and two nominated members of LFCS lecturing staff, as well as the Deputy Director and Service Manager.

The main forum for discussion and scrutiny of LFCS affairs is its Research Committee, comprising all LFCS members of lecturing staff. This meets once a term. In addition, the weekly lab lunch is occasionally used by the Director to raise issues for general discussion within LFCS as a whole.

Research in LFCS

Research is organised into the following areas:

     Concurrency and Descriptive Complexity
     Stochastic Process Algebras and Performance Modelling
     Programming Languages
     Formal Specification and Program Development
     Software Engineering
     Algorithms and Complexity
     Computational Learning Theory
     Interactive Proof Assistants
     Semantics and Mathematical Foundations

The Software Engineering strand is an interdisciplinary research programme, also involving ICCS, ICSA, IRR and the Department of Sociology; the EPSRC Interdisciplinary Research Centre, Dependability of Computer­Based System, is a major activity of this Programme. LFCS is also involved in the System Level Integration Programme, and has a variety of other
research involvements across the Division.

LFCS provides a rich environment for Ph.D. students and post­docs. This is partly a function of its size and critical mass, and the availability of expertise across a wide range of topics; but an important role is also played by a number of organized activities. In particular, a major role in the training of Ph.D. students is played by the Theory Postgraduate Course, a series of taught post­graduate courses at a genuinely advanced level which are taken by Ph.D. students in their first two terms; some of these are taught by post­docs.

Here is a more detailed account of the various LFCS research areas and links and possible links with the rest of the Division.

Concurrency and Descriptive Complexity

(Stirling, Bradfield, Stevens, Jerrum). Work in this area involves both important theoretical advances (applications of tableaux methods to infinite­state model checking and to classical automata­theoretic problems such as DPDA equivalence; descriptive set theory and hierarchy and expressiveness results in modal mu­calculi; decision problems for bisimulation in process algebras; the study of locality and causality in concurrency); and the development of the Concurrency Workbench, a widely­used tool for the specification and analysis of concurrent systems.

Stochastic Process Algebras and Performance Modelling

(Hillston, Gilmore). The use of the stochastic process algebra PEPA as the basis for a compositional approach to performance modelling has been very influential. The work here includes both the underlying theory and the development of a tool, the PEPA Workbench. Recent theoretical work has focused on two areas: using the compositional structure as the basis for decomposed solution procedures, especially product form solutions; and development of a logic to specify performance measures over a given model.

Programming Languages

(Gilmore, Fourman, Stark, Sannella, Hofmann). Work in this area has mostly focussed on various extensions to or developments of Standard ML, a highly influential programming language originally developed within LFCS. Current developments include extending ML to provide a basis for distributed and "global" computation; Extended ML, which provides formal specification facilities on top of ML; and participation in the MLj project, to produce an advanced compiler from ML to Java bytecode and the development of "Thimble'', a library for concurrent programming.

There is also work on type systems for capturing resource bounds, leading e.g. to functional programs which can be certified by virtue of their typing as satisfying certain space or time bounds, and moreover can be compiled into efficient code in a type­directed way.

Formal Specification and Program Development

(Sannella, Anderson, Jackson). Work here is on algebraic and logical foundations of software specification and formal development, embodied in the CASL specification language and applied to specification and development of modular functional programs in the Extended ML framework. There is also work on specifying and verifying reactive systems using linear temporal logic; and on the development of safety­ and liveness­preserving refinement relations for reactive systems.

Software Engineering

(Sannella, Stevens, Anderson). The inter­disciplinary Software Engineering Programme draws on LFCS expertise to tackle problems such as: understanding software architectures; domain­specific languages, including semantics of diagrammatic languages; dependability of systems; and sound support for component­ based design.

Algorithms and Complexity

(Jerrum, Kalorkoti). Work here includes path­breaking research on randomised algorithms, rapidly­mixing Markov chains and connections with statistical physics; and work on algebraic complexity and related topics.

Computational Learning Theory

(Khardon). Work here covers both theoretical developments in computational learning theory and knowledge representation and reasoning, and also the development of efficient algorithms for these problems. There are links to model theory, descriptive complexity and inductive logic programming.

Interactive Proof Assistants

(Burstall, Fourman, Sannella, Jackson). There is a long tradition of work on interactive proof assistants at Edinburgh, starting with the pioneering LCF system and continuing with highly influential systems such as the Edinburgh Logical Framework, LEGO and LAMBDA. Current work includes Proof General, a generic interface for proof assistants; ProveEasy, a user­friendly logic tutoring systems; the use of PVS to verify garbage­collection algorithms using refinement relations; and combining model checking and mechanical theorem proving techniques to verify hardware. (Sannella, Stevens, Anderson)

Semantics and Mathematical Foundations

(Plotkin, Power, Hofmann, Sannella, Simpson, Stark, Longley). There is work on a wide range of topics using mathematical foundations from category theory, logic and type theory. Current topics include: the categorical and logical foundations of higher­order abstract syntax; general categorical frameworks for programming language semantics; axiomatic domain theory; variations on logical relations; realizability models of computation; modelling computational features such as mobility and state; game semantics; and linear logic. The work done at LFCS in this area has been highly influential.

Research Links with other Institutes

Institute boundaries are porous with shared membership and cross­fertilisation of ideas. This can result not only in ``binary links'' but more complex ones reflecting a common need in Informatics to bring a variety of methods to bear on a problem. The Software Engineering Programme (described above) and the EPSRC Interdisciplinary Research Centre, Dependability of Computer­Based Systems links LFCS with ICCS, ICSA, IRR and the Department of Sociology, and involves the LFCS members, Sannella, Stevens and Anderson. Other links with IRR are provided by the work of Alan Smaill on theorem proving in relation to programming, and that of Anderson, Fourman and Sannella under the EU Universal Information Ecosystems pro­active initiative project.

Connecting with ICSA, there is LFCS involvement with the System Level Integration Programme. Jackson works on formal hardware verification (also linking with IRR). Again, Stirling has contributed to the provision of suitable models of concurrency for SLI; his work on transaction protocols provides an­ other link with ICSA. Hillston's interest in Markovian process algebras and performance analysis provide another link between LFCS and ICSA. Fourman is currently working on applying model­checking to planning, providing links between LFCS, IRR and ICCS. Khardon's interests in computational learning theory, inductive logic programming and knowledgge representation and reasoning also LFCS with IRR, IANC and ICCS.

As well as developing such links further many more are possible. For example, LFCS and ICCS share a common interest in logic and semantics; LFCS, IANC and several other Institutes share a common interest in probabilistic methods and these could be developed much further, whether algorithmically, logically or semantically. Agents and their interaction are a common concern of workers in concurrency and AI, providing a potential link between LFCS and (at least) IRR and AIAI.


Undergraduate Teaching is organised into subject schools (Artificial Intelligence, Cognitive Science and Computer Science) and is supported by the Informatics Teaching Organisation. Graduate Teaching is the province of the Graduate School.

At undergraduate level the Division offers four­year Honours degrees in Artificial Intelligence, Computer Science and Software Engineering, together with a variety of joint Honours degrees. Artificial Intelligence can be taken jointly with Computer Science, Linguistics, Mathematics, Psychology or Software Engineering; Computer Science and Software Engineering can either be taken singly or else jointly with Artificial Intelligence, Electronics, Management Science, Mathematics or Physics. There are 112 final year honours students. Teaching within the Planning Unit was judged excellent in the 1994 SHEFC assessment exercise.

At postgraduate level the Division offers M.Sc., M.Phil and Ph.D. degrees; there is a flourishing postgraduate community of about 100 M.Sc, and 150 Ph.D. students in total. A single M.Sc. in Informatics is planned, encompassing a number of themes such as cognitive science, advanced computer systems and bioinformatics.

All postgraduate students belong to the Informatics Graduate School; Ph.D. students also belong to Institutes where they receive specialised training. It is planned that there will be advanced courses for 1st year students across all of Informatics to bring students up to the state of their art and give them a wider exposure within Informatics. LFCS currently organises a taught course taken by all first­year theory Ph.D. students.

Computing Facilities

The Division provides a professionally­managed computing environment tailored towards the needs of research and teaching. This includes a high­level of support for commodity computing on desktop and portable systems, as well as access to specialist facilities such as high­powered and parallel compute servers. The Division's system administration team is recognised for its original work in the field and is responsible for the management and development of an environment including over 800


Edinburgh is one of the most attractive cities in the UK. It combines the architectural grandeur and cultural advantages of a capital city with unrivalled access to unspoilt countryside.

The Division is located at four sites: the James Clerk Maxwell Building (JCMB) at the King's Buildings campus of Edinburgh University (about 2 miles from the centre of the city) and at three Central Area sites. Both LFCS and ICSA are housed in the JCMB; ICCS is housed in Buccleuch Place; IANC and IPAB are housed at Forrest Hill; and AIAI and IRR are housed at 80 South Bridge.

The University and the Faculty

The University of Edinburgh ( is a world­class university situated in the heart of Scotland's capital. It was established in 1583 and is now one of the largest in the UK, with an international reputation for excellence in a large array of subjects, including Science and Engineering.

Faculty Groups

For purposes of academic and financial management including planning and budgeting the eight Faculties (Arts, Divinity, Education, Law, Medicine, Music, Science & Engineering, Social Sciences, Veterinary Medicine) are grouped to form four Faculty Groups (Arts, Divinity and Music; Law and Social Sciences; Medicine and Veterinary Medicine; Science and Engineering). Overall managerial responsibility for each Faculty Group is exercised by the Provost, appointed by the University Court on the nomination of the Faculty Group concerned and with the approval of the Principal, as Designated Officer under the Financial Memorandum for the University.

Science and Engineering

The Faculty of Science and Engineering ( has developed a reputation for leadership and innovation in many different research areas. This excellence has been recognised by both industry and government through the award of research grants. The Science and Engineering SHEFC award is currently worth £28 million and the Faculty 1998/99 grant income was £31 million. In the 1996 UFC Research Assessment Exercise the following units of assessment were rated 5 or more:

     Biological Sciences
     Computer Science
     Earth Sciences
     Electrical Engineering
     Pure Mathematics

with over 90% of departments receiving a rating of 4 or more

This research excellence feeds back into undergraduate teaching in many different ways - students will learn of the very latest developments in their subject and any specialised equipment that they might require for an undergraduate project will be

Science at the University of Edinburgh began in 1583 at the same time as the foundation of the Tounis College of Edinburgh. From small beginnings within the Faculties of Arts and Medicine it flourished to the extent that degrees in science were instituted in 1864 and in 1893 a separate Faculty of Science was established. Today, the Faculty of Science and Engineering is outstanding in Scotland, within one of the leading research universities in the United Kingdom.

Distinguished former staff and students include: Chemist Joseph Black; James Hutton, father of modern Geology; the author Robert Louis Stevenson, who studied Engineering at Edinburgh; Charles Darwin; Max Born, who received the Nobel Prize for Physics; James Clerk Maxwell; Turing Award winner Robin Milner; and Peter Higgs, of Higgs Boson fame.

The Faculty now has over 5,000 under­graduates, over 1,000 post­graduates, almost 500 academic staff and over 500 contract research staff. In the Teaching Quality Assessment exercise conducted by the Scottish Higher Education Funding Council (SHEFC), the following subject areas in the Faculty of Science and Engineering have achieved excellent ratings:

     Cell and Molecular Biology
     Computer Studies
     Electrical and Electronic Engineering
     Mathematics & Statistics
     Organismal Biology

Terms of Appointment

The appointment is full­time, the salary will be within the normal professorial salary range and the person appointed will be required to retire at the end of the academic year in which he/she reaches the age of 65. The post­holder will be eligible to join the Universities' Superannuation Scheme (USS), to which the employee contribution is at the rate of 6.35% of annual salary with the University contributing a sum equal to 14%.

The University recognises that it may be advantageous that the successful candidate should be able to accept, within reasonable limits, consultancies or other paid employment outwith his/her University appointment. Permission to undertake such activities will not be withheld unnecessarily but it is a condition of the appointment that such employment may be undertaken only with the express approval of the Head of Department or, in the case of the Head of Department, of the Principal.

If relocation within the UK is required, the University will reimburse the successful candidate for vouched expenditure, within an overall upper limit of £8,000, as follows:

   1.Costs of removal of household contents and transport costs to Edinburgh for him/herself and immediate family up to a
     limit of £5,000.
   2.Transport costs (only) for him/herself and immediate family to and from Edinburgh for one preliminary visit before taking
     up appointment
   3.Two thirds of expenditure incurred in buying and selling the family home (in respect of estate agents fees (including
     advertising), legal fees and stamp duty).

If relocation from overseas is required a contribution will be made based on similar provisions. All decisions relating to relocation expenses for Chair appointments are at the discretion of the Principal.

Application Procedure

Please quote Ref: 306712

Please complete and return the Application Form plus your Curriculum Vitae (12 copies except for candidates from overseas who need submit only one copy) along with the original of the Equal Opportunities Monitoring Form, a statement describing the contribution the candidate would make to Theoretical Computer Science and the names and addresses of three referees- please include fax numbers and email addresses for referees if possible. Applications should be lodged with:

The Secretary to the University, University of Edinburgh, 9-16 Chambers Street, Edinburgh, EH1 1HT, Scotland, UK

Or fax (+44 (0)131 650 6509), or email (

Closing date: 13th October 2000

References will be treated as confidential to the Special Chair Selection Committee; the curriculum vitae and letters of application of candidates short­listed for interview will be circulated to senior members of the Division. The taking up of references is selective but does not imply a decision that the applicant will be placed on the final short­list for interview.

Applicants are advised that we plan to hold interviews on Friday 8th December 2000

Candidates who have been short­listed will be invited to make an informal visit to the University beforehand and deliver a lecture on their research.

Prospective applicants are invited to discuss these posts informally with the Head of Division, Professor Alan Bundy (by telephone: +44 (0)131 650 2716, or e­mail:, or with the Chair of the Search Committee, Professor Gordon Plotkin (by telephone: +44 (0)131 650 5158, or e­mail:

NOTE:­­These further particulars do not constitute a contract of employment and do not in any way override the terms of any contract of employment which may be issued subsequently to the successful candidate. The University reserves the right to make appointments from outwith those candidates who have submitted formal applications, or to make no appointment.

Asylum and Immigration Act 1996

Section 8 of the Asylum and Immigration Act 1996 makes it an offence to employ an individual who is subject to immigration control, and who does not have permission to reside in the UK and undertake the type of work for which (s)he would be employed. Therefore, should you be asked to attend for interview, you will be required to provide an appropriate document which will validate your employment, should you be appointed. An appropriate document may be one of the following:-

     A document stating your name and National Insurance Number (issued by a previous employer, the Inland Revenue, the
     Benefits Agency or the Employment Service).
     A passport describing you as a British Citizen or having the right to live in or be re-admitted to Britain, or a letter from
     the Home Office to this effect.
     A passport describing you as a British Dependent Territories Citizen, that status arising from your connection with
     A letter from the Home Office confirming naturalisation as a British Citizen.
     A birth certificate from the UK or the Republic of Ireland.
     A passport or a national identity card from a state which signed the European Economic Area Agreement (EEAA),
     confirming that you are a national of that state (or a UK residence permit granted to you as a national of such a state).
     A passport confirming that you are not subject to immigration control and have no restrictions to your entry to or
     residence in the UK, or a passport which confirms that you have the right to enter and remain in the UK and be
     employed in the field for which you are applying (or a letter from the Home Office to this effect).
     A passport which confirms that you have the right to abode in the UK as a family member of a named EEAA national
     who is resident in the UK.

The University is committed to treating all candidates equally. Should the University wish to appoint a person who is not able to produce a document as described above, an application for a work permit may be made on that person behalf. Subsequent appointment is subject to the success of that application.

Home : News : Vacancies 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail:
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh