Laboratory for Foundations of Computer Science

Since its formation in 1986, LFCS has functioned as a research institute along lines much the same as those proposed for institutes in the new Division of Informatics. This description of LFCS is provided for the benefit of members of the Division who are considering setting up institutes of their own. There is some additional rather out-of-date information about LFCS on the web at http://www.dcs.ed.ac.uk/lfcsinfo/.

Scope

LFCS has the following aims (extracted from the original grant application):
The main purpose is to develop theories of computation, principally those which are likely to be a basis for methodologies; the criteria for this research will be lucidity, coherence and applicability. Examples are Along with these examples go the formalisms which embody them.

There are two important supporting purposes:

  1. Interaction between industry and universities through application studies and experiments. Under this heading fall tools for exercising the above formalisms.
  2. 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 through courses for industrialists.
Probably an algorithms/complexity-oriented example should be inserted into the above list of examples in recognition of the enlargement of the scope of LFCS in 1991 to include this area, but otherwise these aims remain valid. It is generally accepted as one of the leading centres in the world in Theoretical Computer Science and its application and 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 standards of research, and about approaches to solving problems. This shared culture is a very important component in its success. Other unifying factors are the widespread use of logic and category theory and of a common programming language (Standard ML).

Constitution and finance

LFCS is a research unit of the University, contained within DCS. It has its own accounts and has built up modest reserves (profits from running industrial courses and conferences, etc.) which are separate from those of the Computer Science department. It currently has an income of about £1M per annum from research grants, with most funding from EPSRC and ESPRIT.

Membership

There is no formal notion of LFCS membership. Anybody in DCS who subscribes to the aims of LFCS and is willing to contribute is welcome. The current numbers are as follows: 16 teaching staff; 18 postdoctoral research fellows; 5 support staff; 20 research students; 4 visitors. A few people from elsewhere in the University and further afield are Associate Members of LFCS.

Management

LFCS is managed on a day-to-day basis by its Director and Assistant Director in consultation with a number of Co-directors. 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 Lab Lunch is devoted to an informal discussion of relevance to the whole membership of LFCS.

Activities

LFCS's main activity is research. Most of this would 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. LFCS occasionally runs conferences and workshops, and in the past it has run short courses to transfer the results of LFCS research to colleagues working in industrial research labs and at other universities.

Organization of scientific activity

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 to support this research.

Research is organized into five broad themes:

There is considerable overlap between these. Many research projects and most LFCS members do not fit tidily into a single theme. Also, this list of themes needs to be revised to reflect more accurately current research in LFCS. Still, such a classification is useful in explaining LFCS's research profile. It also provides a structure for strategic discussion of future research directions via periodic theme reviews.

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.

Postgraduate teaching

A series of advanced courses for first-year Ph.D. students (some of them shared with the M.Sc. "Theoretical Computer Science" theme) has been offered by LFCS members for many years. The aim is to provide a common background in Theoretical Computer Science as a basis for independent research. This should continue under the Division of Informatics but could perhaps be integrated with similar courses in other parts of the Division into a broader programme.

Publications

LFCS publishes a celebrated report series with recent reports also available electronically. Software produced by LFCS is distributed freely. Members of LFCS also publish books and papers in journals and conferences, of course.

Infrastructure

The administration of LFCS is supported by the Assistant Director, a part-time Grant Administrator, and a secretary. The Assistant Director is responsible for most non-scientific aspects of the running of LFCS including liaison with industry. All three are supported by DCS and have duties outside LFCS in addition to their LFCS responsibilities.

The LFCS computing infrastructure was originally quite separate from the computing system in the rest of the Computer Science department and was supported by separate computing staff. Nowadays LFCS equipment is seamlessly integrated with the rest of the DCS network. Machines for teaching staff and research students are provided mainly by DCS while machines for researchers and central servers are provided from grants.

Research grant management

Considerable benefit is derived from a centralized approach to research grant management. Grantholders 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 grantholder can concentrate solely on writing the scientific case for support.

Interaction with other units in the University

A few members of LFCS are also members of the Computer Systems Group, and interaction is increasing. Alan Smaill is a DAI/DCS joint lecturer and contacts between LFCS and the Mathematical Reasoning group in DAI have always been strong. LFCS members currently hold or have recently held joint grants with members of CSG, DAI, Cognitive Science, HCRC, Sociology and the Management School, and have co-supervised Ph.D. students in most of these plus (at least) Chemical Engineering.

Industrial interaction

LFCS has strong links with a number of firms. Some are partners in collaborative grants while other contacts are less formal. Although members of LFCS undertake consultancy work and LFCS receives some direct industrial funding, the main purpose of these contacts for us is as a source of interesting research problems and realistic case studies rather than as a source of income.

Social activities

The atmosphere in LFCS is friendly and supportive. This is encouraged by a range of social activities: a Christmas party, a barbeque to celebrate the end of the annual first-year PG course take-home exam, the weekly Lab Lunch, and occasional excursions.
Don Sannella dts@dcs.ed.ac.uk.
Last modified: Fri Jun 26 10:16:27 BST 1998