The Laboratory for Foundations of Computer Science (LFCS) was formed in 1986 on the basis of a strong existing group in Theoretical Computer Science. It quickly built up a strong reputation and is now generally accepted as one of the leading centres in the world in Theoretical Computer Science and its application. Its present organization and structure is essentially that proposed for Institutes in the Division of Informatics.
LFCS wishes to continue in more or less its present form as an Institute within the Division of Informatics. It wishes to become an Institute now rather than waiting for the picture across all of Informatics to become clear.
An overview of the present organization of LFCS is available at http://www.dcs.ed.ac.uk/home/dts/lfcs.html. Much of what follows appears there in some form. The LFCS home page is at . The information there on research topics and grants is seriously out of date, but the remaining information (overview, teaching, publications, software, events) is fairly accurate.
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. In more detail:
The main purpose of LFCS is to develop theories that address issues arising in computing, principally those which are likely to be a basis for methodologies or understanding; the criteria for this research will be lucidity, coherence and applicability. An important component of such a theory is typically a formalism (e.g. a logical calculus) which embodies it; applicability may be demonstrated via a tool employing the formalism. There are two important supporting purposes:
- Interaction between industry and universities through application studies and experiments. The aim here is twofold: such interaction provides important feedback in evaluating theories; it also provides ``real-world'' understanding of which areas are currently in most need of the development of relevant theories.
- Enlargement, in the industrial and academic communities, of knowledge essential for grasping and applying soundly-based methodologies. This will be approached both through undergraduate and postgraduate courses and more widely through courses for the academic and industrial community.
Achieving a deep understanding of the nature of computation and computing systems is regarded as a worthy intellectual goal with strong potential for engineering application. Robin Milner's inaugural lecture for LFCS (see ECS-LFCS-86-1) spells out the rationale behind the main purpose of LFCS more eloquently than this application possibly can. The main idea, and the reason for the use of the word ``Laboratory'' -- which we wish to retain, concerns the mutually beneficial interplay between theory and practice via experimental application of the theory in building systems.
LFCS has an impressive track record of seminal research in this area. Its work has strongly influenced the development of Computation Theory particularly in the fields of semantics, specification, concurrency, complexity, machine assisted proof and implementations, both of languages and of proof systems.
There is a broad consensus within LFCS concerning the kind of problems that are interesting and important, about approaches to solving problems, and about standards of research. The approach to solving problems is generally mathematical, often employing methods originating from or inspired by mathematical logic, but also making whatever use of other mathematical tools -- algebraic, categorical, lattice-theoretic, combinatorial, analytic, etc. -- as appropriate. Another major unifying factor is the employment of a common programming language with advanced typing facilities, currently Standard ML. This shared culture is a very important part of the strength of LFCS.
Research in this area is beginning to make an impact on industry. Some examples are: use of formal methods in development of safety-critical systems; use of model-checking for hardware verification; relevance to the System Level Integration initiative. Much of LFCS's work could be characterized as basic research on theoretical foundations but there is a significant amount of applied research and much of this applied work has connections with groups in industry. Members of LFCS undertake consultancy work and LFCS receives some direct industrial funding; however, the main purpose of such contacts for us is as a source of interesting research problems and realistic case studies rather than as a source of income.
In their report, the IPU reviewers suggested that LFCS should split into separate institutes of Reasoning and of Computing Foundations. This suggestion was discussed extensively within LFCS but was rejected on the grounds that LFCS is intellectually coherent as it stands and that the suggested split would break many vital links between work on reasoning and the rest.
LFCS does not wish to broaden its scope to ``Foundations of Informatics'', although its expertise is clearly relevant to some topics outside Computer Science. There is great enthusiasm for collaboration with others in the Division and such a broadening might take place naturally over time, but it seems pretentious and currently insufficiently justified to assume this in advance. LFCS will be pro-active in seeking appropriate partners within the Division for collaboration. For example, we will organize workshops on topics of potential cross-Division collaboration.
Concerning current interaction with other units in the University: a few members of LFCS are also members of the Computer Systems Group, and interaction is increasing; before the formation of the Division Alan Smaill was a DAI/DCS joint lecturer and contacts between LFCS and the Mathematical Reasoning Group have always been strong; LFCS members currently hold or have recently held joint grants with members of CSG, the former DAI and Cognitive Science departments, HCRC, Sociology and the Management School, and have co-supervised Ph.D. students in most of these plus (at least) Chemical Engineering.
The current LFCS membership includes 16 members of teaching staff, 18 postdoctoral research fellows (including 2 members of teaching staff on fellowships), and 20 research students. All of the current members of teaching staff who belong to LFCS have agreed to be listed on this application as primary members of the proposed institute:
Most or all researchers who are currently employed to work on grants held by these people are also expected to become primary members. Here is a list of those who have so far agreed to this:
Samson Abramsky Stuart Anderson Julian Bradfield Rod Burstall Martin Escardo Mike Fourman Stephen Gilmore Jane Hillston Martin Hofmann
Mark Jerrum Kyriakos Kalorkoti Roni Khardon Gordon Plotkin Don Sannella Alex Simpson Alan Smaill Ian Stark Colin Stirling
David Aspinall Anna Bucalo Ewen Denney James Laird
John Longley John Power Daniele Turi Martin Wehr
The following have so far agreed to be listed as secondary members:
Alan Bundy Carsten Führmann Corin Gurr Paul Jackson
Thomas Kleymann Dave Robertson Mark Steedman Perdita Stevens
LFCS is managed on a day-to-day basis by its Director and Assistant Director in consultation with the Co-directors. Don Sannella is the current director of LFCS; his 3-year term expires in April 1999. One of the other Co-directors (currently Samson Abramsky, Rod Burstall, Mike Fourman, Gordon Plotkin and Colin Stirling) will succeed him and the directorship will rotate amongst the co-directors continuing previous practice.
The Research Committee, which is composed of all members of LFCS teaching staff, meets once per term. An Advisory Board composed of the Directors, representatives from the membership of LFCS, internal and external academics and industrialists, meets about once per year. Occasionally the weekly ``Lab Lunch'' meeting is devoted to an informal discussion of relevance to the whole membership of LFCS and there is a General Meeting of LFCS about once per year.
The direction of research done by individuals and groups in LFCS is of course the responsibility of the people involved, and similarly for the management of research grants, but LFCS provides a strong cultural environment and mutually supportive basis for this research.
Research is organized into five broad themes:
LFCS members are encouraged to ask each other to comment on draft grant proposals. There have been occasional attempts to take a strategic view of LFCS's research portfolio but coercion to fill holes that become apparent does not go beyond indicating the existence of opportunities and encouraging appropriate candidates to apply for lectureships.
Lab Lunch is a weekly informal meeting where visitors are introduced, news is announced, and 1-2 short talks or trip reports are given. This is supplemented by research clubs in specific areas, and a weekly Theory Seminar.
Following Divisional policy, LFCS has no line management function as regards teaching staff.
There is currently no mechanism for formal appraisal of research staff. Individual grant holders take responsibility for researchers employed by them. Cases for promotion are handled on an ad hoc basis by the Director in consultation with grant holders. However, LFCS supports the ideas contained in Stuart Anderson's paper on involvement of researchers in teaching (see http://www.dcs.ed.ac.uk/home/soa/teach-res.ps) and plans to institute a periodic planning and review procedure for researchers who opt into this scheme.
Plans for management of support staff in the Division seem quite unclear at present. Until now the Assistant Director has reported to the Director and other members of support staff have reported to the Assistant Director.
Considerable benefit is derived from a centralized approach to research grant management. Grant holders are ultimately responsible for their grants but all the clerical work and most decisions concerning details of expenditure are delegated to the LFCS central administration. Most equipment money is pooled and used to buy machines when they are required rather than when grants happen to start. Personnel can effectively be shifted between grants on related topics to optimize the use of funds. The grant application process is supported to the extent that the aspiring grant holder can concentrate solely on writing the scientific case for support.
In addition to grant funds, LFCS has accumulated some central funds including profits from running industrial courses and conferences. A scheme of small project grants to support initiatives that enhance the research portfolio or environment of LFCS is about to start, funded from this source.
LFCS has accumulated £40-45K of central funds from surpluses on past activities. Its income from research grants is about £1M per annum, with most funding from EPSRC and ESPRIT. Apart from the cash overheads that LFCS grants bring to the University and the Division, EPSRC grants bring in recharging funds of around £55K per annum (conservative estimate). This is currently used to fund a part-time Grant Administrator and a CO post in the Division. In the last RAE submission, 21 members of LFCS were counted as Category A staff. The income to the University from SHEFC which is attributable to the research activities of these people is around £779K per annum.
LFCS's track record with grant applications is excellent and our relations with EPSRC and ESPRIT personnel are good. Our input to the formulation of new initiatives has been sought by both bodies from time to time.
The prospects for future EPSRC funding are good. Current EPSRC policy is to encourage more speculative, curiosity-driven, high-risk grants, and this is exactly the sort of research that LFCS has pursued since its inception. Also encouraged are large and multidisciplinary grants, including those involving joint funding with other research councils. LFCS can use its influence to lever funding to other areas of the Division by forming partnerships and collaborations. We have significant relationships with a number of industrial partners, which fits well with EPSRC's intention to have half of all grants carrying some form of external contribution. The following proposed or existing programmes are relevant, among others: a managed programme in Systems Engineering and Systems Integration; a new or revamped programme on Critical Systems; a programme on Distributed Information Management; a focus on developing new activities around generic IT solutions across application domains.
Most EPSRC grants in LFCS are three-year ``responsive mode'' grants. There are some grants under managed programmes, some visitors from abroad are supported by EPSRC Visiting Fellowships, and LFCS members have received a fair number of EPSRC Advanced Fellowships and Senior Fellowships over the years.
The prospects for future European funding are mixed. ESPRIT is tending to cease funding theoretical research of a foundational nature in favour of participation by theoretical groups in projects having generally practical aims. LFCS is well-positioned to contribute to such projects but has not tended to seek such opportunities in the past. A specific opportunity in Framework 5 will be a pro-active initiative in ``Globally Aware Intelligent Information Systems'' to which LFCS could respond in partnership with others in Informatics.
All members of teaching staff in LFCS occupy established or temporary posts in the Division. A few are on EPSRC fellowships or similar, and then the fellowship pays for a replacement lecturer. EPSRC research grants do not pay for the time of the principal investigator and the few ESPRIT proposals where this has been attempted have failed. Each LFCS researcher is employed to work on a specific research grant. The post of LFCS Director is a major administrative task within the Division.
The administrative infrastructure of LFCS is provided by the Assistant Director (Gordon Duckett), a part-time Grant Administrator (Monika Lekuse), and a secretary (Kendal Reid). The Assistant Director is responsible for most non-scientific aspects of the running of LFCS. The Grant Administrator is supported by recharging funds from LFCS grants while the other two are supported by the Division. All three have duties outside LFCS in addition to their LFCS responsibilities. The support that these people provide for LFCS is an absolutely vital component in its success. It is essential that at least this level of support is maintained.
The LFCS computing infrastructure was originally quite separate from the computing system in the rest of DCS and was supported by separate computing staff. Nowadays LFCS equipment is seamlessly integrated with the rest of the network in Informatics South. Machines for teaching staff and research students are currently provided mainly by the Division, and at least this level of central provision must be maintained. Machines for researchers and shared servers are provided from grants.