UoA CS Structure and policy (RA5a analysis)

There are presently 9 Category A research-active staff selected, all of whom, but one, are qualified to PhD level. Fifteen additional staff (14.3 fte) are also research-active but have not been included in this submission since most are at the start of their academic career (7 currently registered for part-time PhD). Together they have generated a large number of public outputs over the review period, including 155 refereed papers (excluding authored/edited books or chapters in books). The high esteem of staff as researchers is signalled by their activity on international research funding committees, the chairing of major international conference sessions, invitations to plenary talks, or as invited speakers at important international meetings and research centres. The figures shown on RA4 are a reflection of monies spent during the period 1996-2000, however by the census date research was supported by £545,139 of external funding, including £290,903 from the EU, £209,090 from OST research councils and £30,900 from NHS and charitable trusts. On 1 December 2000 there were 21.85 fte research students enrolled in the subject area. The level of research student throughput and completion rate since 1996 is higher, in comparison with the 1996 exercise, with 7 students having been awarded doctorates or masters degrees (5 and 2, respectively) (RA3a refers).

Research takes place primarily on a group basis with members of staff and research students working together in well-defined sub-areas of research activity. These major groups are the Biomedical Computing Research Group (BIOCORE) and the Data and Knowledge Engineering Research Group (DKERG). DKERG is led by a senior researcher and Principal Lecturer and is in receipt of sizeable external research funding. BIOCORE is led by the research Professor and additionally attracts international recognition for the quality of its interdisciplinary research. Both groups consist mainly of newly-appointed members of staff some of whom, whilst still at the start of their research careers, are nevertheless eagerly enthusiastic in building their research reputation, seeking external funding and producing high-quality research output. The following represents a brief description of these two research groups and their constitution in terms of research-active staff.

During the period 1996-2000, academic staff attached to BIOCORE published in excess (including those currently in press) of 40 peer-reviewed journal papers and 50 refereed papers in major national and international conferences. This is in addition to a number of edited books, book chapters, official reports, internal reports and other presentations. Moreover, staff enjoy a diverse array of esteem indicators (RA6 refers). The group is particularly renowned for its activities in the field of intelligent computing in clinical oncology where major collaborative work focuses on the development of intelligent prognostic classification techniques, the identification of prominent markers and the provision of accurate clinical decision support and patient management strategies.

Specifically, this research involves the development of either stand-alone neural structures or hybrid neuro-fuzzy frameworks for the analysis and stratification of important pathological prognostic markers leading to the accurate prognosis and clinical management of cancer disease patients (Naguib outputs 1,3; Odetayo outputs 3,4). In particular, the study published in the British Journal of Cancer (Naguib output 3), which combines the analysis of both conventional and experimental prostate cancer prognostic markers, demonstrates the impact of this work on the clinical and oncological research communities. Further work on genetic algorithms (Odetayo output 1), Holland-based classifiers (Odetayo output 2), and fuzzy models and modelling of uncertainty (Petrovic outputs 1-4) are currently being applied to studies in breast, bladder, prostate and ovarian cancers.

Another aspect of prognostic analysis, also applied to cancer research, is that based on image cytometric and molecular analysis of tissue samples in relation to breast cancer aspirate cells (Naguib output 4), and on image processing algorithms for the quantitative measurement and feature extraction of cancerous colonic mucosa (Naguib output 2). Further work on image processing has centred on the development of robust parallel image processing paradigms based on systolic array and parallel virtual machine implementations (Amin outputs 1-3) and on cell segmentation and low level vision mechanisms (Todman outputs 1-4) which are currently being applied to studies in human form perception leading to the development of orientational coherence metrics for the histopathological identification and classification of colonic and pancreatic cancers.

Epidemiology related research follows two strands. The first relates to the analysis of the prevalent NHS breast screening procedures and on the performance of the invitation process over the first ten years of the screening programme. Novel approaches leading to the optimisation of currently used formulae for uptake and coverage have been suggested and are the subject of a substantial report to the National Cancer Intelligence Unit (not included in this return). The second strand investigates design considerations for the implementation of a dynamic relational database schema to hold dental epidemiological data (Amin output 4). This work aims at investigating dentition development in school children aged 4 to 16 by applying fuzzy SQL logic to the data sets, and is considered to be the first such investigation of its kind.

Successful work in the areas of artificial neural network applications in clinical oncological studies and on breast screening performance analysis have attracted wide national and significant international media coverage on numerous occasions (detailed in RA6).

While data and knowledge modelling is central to the work of DKERG, the scope of the group also incorporates two additional sub-areas which relate to its core work. The first sub-area concerns the implementation of information systems and technology in enterprise. This deals with the development of a framework for knowledge management and representation in business, and the development of methods for improving information systems deployment in underdeveloped nations. The second sub-area concerns the development of internet-based learning environments. Here, research includes the development of training frameworks for SMEs and the application of software development life cycle to the development of on-line learning materials. The example publications returned in this review relate to the core work of DKERG rather than these latter two sub-areas.

The level of research activity in the Computer Science subject area, in general, has increased significantly beyond the levels documented in the 1996 RAE. The principal changes include an:

The research culture, both within the university and within the Computer Science Unit, has significantly developed during the course of this assessment period. At university level, measures to improve the research culture have included the appointment of a Pro Vice Chancellor for research, the creation of a Graduate School in a new building with a support infrastructure for research students, the establishment of an investment fund for research (supporting sabbaticals, studentships etc.), and support for training events for staff (e.g. on European research bidding processes) and for research students. Within the Computer Science Unit, we deliberately took the decision to build strength in one main area (i.e. digital imaging) by recruiting new staff, with appropriate research expertise. As a result of this process, the majority of staff returned as research active in this submission have joined the university in the period of this assessment, and most of these have taken up their first academic staff appointments.

Besides developing a strong group of research active academic staff in one area, we have also developed an appropriate critical mass of full time research students to work with them. The information in form RA3a demonstrates a significant upward step change in the number of full time research students, which took place in 1999. This step change occurred as a result of a notable increase in our external funding, which has enabled us to offer more full time studentships. A significant part of the additional funding, which we have used to support these studentships, has arisen through industrial sponsorships and training collaborations (with major UK and international companies such as Ericsson, Fujitsu, and ABN AMRO Bank who have awarded funding of over £150k in total). Much of this additional non-core funding does not count as research income in the RAE definition, but it has been particularly helpful in increasing our level of studentships and research equipment and infrastructure. Some of the industrial collaborations, which have generated this additional funding, have been established by non-research active staff, who have thereby helped to support the research efforts of the Unit. During the period of assessment we have also taken steps to improve the training given to the PhD students and contract researchers with central university support (e.g. courses on research methodology, thesis preparation, research career planning).

The creation of a Research Centre with eight contributing academic staff and (currently) eight full time PhD students has led to a significant growth in the research culture within the Unit. Regular research seminars are held with both internal and external speakers. The researchers working in the different application sub themes have been able to share knowledge and techniques and thereby make advances that would otherwise not have occurred. For example, interaction between staff and research students working in the visual surveillance area and those working in the remote sensing area have led to some useful developments in structural analysis of satellite imagery in urban environment monitoring. The fruits of this interaction are demonstrated by the fact that some of the publications by staff working in the visual surveillance sub theme have been in journals concerned with environmental monitoring (e.g. JONES, output 1). The benefits of this interaction between the different application themes is also evident in the context of a 249kEuro European Commission funded project "MAVIRIC" which the Unit coordinated. This activity was concerned with the exploitation of machine vision techniques in remote sensing. The aim of MAVIRIC was to bring together workers from two quite different areas of imaging research to tackle the problems associated with the structural interpretation of imagery from the new generation of very high resolution imaging remote sensing satellites, such as IKONOS-2. As part of this activity, the Unit organized an international workshop at Kingston in 1998, which brought together 38 machine vision experts and remote sensing experts from around the world.

BARMAN has applied image analysis techniques to conditions such as cataract and posterior capsule opacification in an attempt to provide clinicians with a quantitative measurement of visual performance (BARMAN, outputs 3 and 4). Together with a PhD student, BARMAN is also developing a telemedicine system for remote diagnosis of retinopathy of prematurity – a condition affecting pre-term infants. BARMAN has excellent external collaborations with Kings College London, Imperial College (with whom she is preparing a proposal for a major clinical trial), Moorfields Eye Hospital, and the University of Torun, Poland. Her work received a citation in a British Medical Journal review of significant developments in ophthalmology in 2000.

Our priority during this reporting period has been to invest resources in creating a group of high quality researchers in one focused area of Computer Science research. To this end we have pursued a vigorous recruitment policy targeting comparatively young staff whose research can contribute to digital imaging. This has resulted in the creation of a research centre with a significant and growing international reputation, in which the majority of research active staff have joined Kingston since 1996.

This policy has enabled us to form an integrated, energetic and innovative team of researchers in which group interaction as well as individual effort promotes high quality research. The Digital Imaging Research Centre has adopted practices designed to integrate new staff into a strongly supportive environment. All developing research staff are attached to senior researchers who act as mentors, advising on research plans, helping in the drafting of publications, identifying funding sources, and advising on IPR and exploitation issues.

Since the last Research Assessment Exercise, we have concentrated on developing excellence in one area, which has enabled us to create a Research Centre with its own distinctive identity. We believe that the quality of the outputs, the research culture and the reputation of the Centre have developed to a very pleasing level. Almost 70% of our publications put forward for assessment on this occasion are in peer-reviewed academic journals (most of them journals of international standing in their respective areas). The remainder were presented at major international peer reviewed conferences (the vast majority IEEE or ACM sponsored). Besides the 32 publications returned, a further 156 papers have been published by the eight research active staff in our submission making a total of 188, during the period of this assessment.

Staff submitted have achieved peer recognition both nationally and internationally, as indicated by invitations to participate in organizing committees of conferences, international technical committees and advisory boards, to referee papers for international journals, to participate in editorial boards of international journals and to contribute by invitation to special issues of journals. Recognition at a very high international level has also been evident from invitations to assist overseas governments and the European Commission on evaluation and planning of R&D activities, from the award of a paper prize from a German academic body, and through funding of research by an Australian company. Further details of these are given in RA6.

The number of full time PhD students significantly increased during the period of this assessment. We also adopted relatively recently a broad policy of progressively reducing the number of part time PhD students, and giving priority to the recruitment of full time research students using both grant awards and industrial support. We believe this policy will further enhance our future research performance. The trend in full time and part time research student numbers arising from this policy is evident in RA3a.

Applied Artificial Intelligence The group covers research in Planning, Scheduling, Transport Logistics and Constraint Based Reasoning, and Neural Networks as applied to Manufacture, Control and Medical Applications. The work of the group centres on the application of AI based technologies to industrially and commercially relevant problems and in particular manufacturing. There are 5 academic staff working in this area (3 professors, 2 lecturer posts, 4 Ras, and 9 RS).
The AAI Group has been strengthened by the appointment of Prof. Lisboa and the integration of Prof. Williams (Engineering) whose interests in Neural Networks and industrial computing complements the rest of the group. In addition, Dr Akomode, joined the group as a new academic in replacement of Dr P Smeaton who has retired. Again, our policy of recruiting young staff sees the addition of Mr. El-Rhallibi, who we expect to submit as a research active member of staff in the future.
The scheduling and planning subgroup (Kelleher, Akomode, and El-Rhallibi) work on planning logistics and scheduling in manufacture has grown out of the earlier work on fundamental properties of RMS and constraint based reasoning. The work has been published in well known and respected journal and conferences (Akomode 97, 98, Kelleher 96, 00). The work has received significant grant funding including a large 4^th Framework grant on rescheduling in conjunction with Pirelli (Milan) and Iberia Airlines (Spain). Further funding from the EU, in Cooperation with a large shipping Company (VoPak (NL)), addresses flexible logistics management.
The research grouping on in neural networks (Prof Lisboa and Prof Williams) investigate Neural techniques and applications in Control (Lisboa, 98, 00, Williams, 96, 99) and is at the forefront of two specialist areas of clinical decision support, namely the characterisation of high-dimensional noisy spectral sources and the derivation of prognostic indices for censored data. This research is carried out with leading international research groups in the field, namely the Universitat Autonoma de Barcelona for clinical grading of brain tumours with Magnetic Resonance Spectra acquired in vivo, and Christie Hospital, in Manchester, for breast cancer post-surgery survival analysis, with support from the Istituto Nazionale per lo Studio e la Cura dei Tumori in Milan, who developed some of the early theoretical work.
A new strand of research has been introduced by extending neural network and graphical methods from medical research onto the important business area of data visualisation of information for the segmentation of the electronic commerce market. This research is already transferred to Unilever Research Laboratories as part of a long-standing industrial collaboration further cementing the group’s position in developing new methodology targeted to direct practical value. The standing of the research group has resulted in consultancy work both from industry and from national organisations such as the Health and Safety Executive leading to membership of the executive committee of the Royal Academy of Engineering’s UK Focus for Biomedical Engineering.
The change in personnel of the group has been well managed. In the period of assessment the group has received the following grants:

Research at MMU, returned under UoA25 (Computer Science), involves two major research groups in the broad area of artificial intelligence:

o CARD (Centre for Agents Research & Development); and
o Intelligent Systems Group.

The UoA is vibrant, highly focused and has delivered:

o 104 major international journal and conference papers;
o 8 PhD awards
o 6 RSs
o Total Research Council grants £0.75M;
o 8 OST grants;

The groups pursue research of international and national importance as evidenced by the award and continued growth in the numbers of Research Council and high profile industrial grants and contracts and the substantial number of publications at the most prestigious international conferences in the field, a substantial proportion of which are by invitation. The UoA is characterised by relatively young dynamic staff with complementary interests and a vision for building upon the international profile of the unit. There is a strong on-going commitment to collaboration with external expert scientists and research groups (e.g. Moscow State; Trento; Padua; Naples; Amsterdam; Utrecht; Saarbrucken; Murdoch, Perth; New South Wales; Vilnius, Lithuania; Ukraine; Warsaw; Malaga; Universidad Nacional del Sur Bahia Blanca, Argentina; King’s; Edinburgh; Leeds; Manchester; UMIST) that enables the groups to maintain an effective and influential international and national role within the research community. Members of this international network of collaborators have been attracted to take up research posts within the groups at MMU or have held visiting appointments funded by the EPSRC during the review period (e.g. Pliuskevicius; Arranz).

The University has a positive philosophy concerning the encouragement and development of research activity, the need to maximise research experience, and the provision of an environment conducive to research. This support, both at the managerial level and financially, has played a key role in the development and expansion of research throughout Computer Science over the last five years. The University has identified Computer Science as a key long-term research area and has initiated a £9M building project to enhance the infrastructure support for Computing and IT. Since 1996, the University has invested a further £1M in its centres of excellence in Computer Science through the appointment of senior research fellows, research fellows and research students together with their attendant support costs.

The overall strategy has been, and continues to be, to develop and sustain high quality research at the international level. It was originally envisaged that the research groups declared in the 1996 RAE submission would be developed further in this one. However, the success of the UoA has led to a high turnover in staff (also contributed to by the high staff mobility in this discipline) with many of the 1996 staff taking up promoted posts at other universities. Nonetheless, the combination of an active research enhancement policy within a positive research culture has enabled the UoA to continue to flourish with, for example, the Intelligent Systems Group securing its standing at the international and national levels. By continuing support for research active staff, we have successfully developed a large proportion of staff new to the UoA .

2 Research Management:

The UoA Management Committee oversees strategic planning and progress monitoring. Committee membership comprises senior research staff, Head of Department, Dean of Faculty and the University Director of Research Development. Day to day running is managed by Research Group Leaders (RGL) and the UoA Coordinator. The role of Research Group Leaders includes: driving the production of innovative research outputs of international standing; providing support to staff and students by setting up and managing external collaborations with research groups of international standing; organising training and development programmes; promoting the acquisition of relevant research skills.

The Faculty Research Degrees Committee (FRDC) and Faculty Graduate School are jointly responsible for QA monitoring and deliver appropriate supporting programmes for the training of supervisory staff and postgraduates. Young staff supervising PhD students are mentored by experienced staff. Mentoring also assists postdoctoral research staff to make the transition from supporting to independent researcher status.

During their PhD programme, students are encouraged to publish chapters of their theses as research papers, or to present data to international and national conferences (e.g. 4^th International Workshop on Temporal Representation and Reasoning (IEEE); European Conference on Artificial Intelligence (ECAI); 9^th IEEE International Conference on Fuzzy Systems) gaining experience of the peer review process and to network with key figures in the field. The University, FRDC and Department also ensure that postgraduate students have appropriate equipment, technology, technical support and skills to conduct their work. All registered research students and academic staff at MMU have access and full borrowing rights to the enormous resource base of the libraries of all four universities in Greater Manchester via the Consortium of Academic Libraries in Manchester scheme (CALIM).

Research seminars involving internal and external international and national speakers are held at research group, departmental and UoA level. Regular Research Colloquia are held at which oral and poster papers are contributed by post graduate, post doctoral and research staff. These scientific exchanges bring additional dynamism and vitality to the research culture. The UoA will continue to contribute to the setting of the international research agenda by continuing to co-ordinate international workshops and meetings at MMU and externally through the membership of individual members of the UoA on the international scientific advisory committees of the most prominent conferences in the discipline {eg International Conference on Artificial Intelligence: Methodology, Systems, Applications}.

3.1.1 Background Since the last RAE, the work of the Logic and Computation Group has evolved and expanded, and MMU has become identified as an international centre of excellence for research in logic and agents, particularly automated-reasoning, executable logics and formal methods for agent-based systems. In recognition of these developments, and with a view to future growth and exploitation, the Centre for Agent Research and Development (CARD) was formed. The purpose of this expansion was to broaden the range of research activities that could be supported, to encourage further collaboration, and to exploit the novel research being carried out. Since April 1996, CARD has attracted significant EPSRC funding, having already completed EPSRC projects valued at over £250k and currently holding grants worth over £300K, in addition to industrial funding from, for example, HP Laboratories (Bristol) and EU funding as part of, for example, the European Network of Excellence on Agent-Based Systems (AgentLink). The research activities of CARD cover a broad range from theoretical and logical aspects of agents and reasoning through to more practical applications and development of agent-based systems. The key achievements and deliverables for which CARD is internationally recognised are outlined in 3.1.3. and 3.1.4 below.

3.1.2 Objective
To undertake and apply high quality research into all aspects of agent-based systems, including analysis, foundations, development and programming languages, and to promote collaborative research between CARD and other groups internationally, nationally and within MMU.

Human–Computer Interaction: Main achievements
The HCI research group has particular strengths in 3 main areas: Formalisms for Interaction, Personal Technologies and Digital Libraries. The work of the group has been influenced by various government initiatives – for example, the 1993 Follett report on digital libraries and the 1995 Foresight report, which includes usability and personal technologies in 3 of the top 6 topics. Two recent successful grant applications have been in response to particular initiatives: the Multimedia and Networking Applications and Distributed Information Management programmes of EPSRC.
The main focus of the Formalisms for Interaction group is the use of formal and semi-formal modelling in interaction design – investigating how soft aspects of design can be described in ways that are precise and rigorous enough to support design practice. This involves the integration of methods from psychology and formal methods to reason about interaction design. Blandford [2] has investigated a trade-off between rigour of formalisation and scope of techniques. Conversely, Blandford [3] demonstrated an approach to integrating insights from different modelling techniques by passing results from one technique to another, to build up a rich understanding of a design problem that represents multiple perspectives. Fields [3] built on this work, using Modal Action Logic to compare design options proposed by Blandford [3]; this work illustrates a role for formal notations in analysing usability features. Butterworth [3] presented a formal framework that supports reasoning about the use of a system, in such a way that an analyst could assess whether modifications to an interface specification were likely to yield required improvements in use. A Resource Model (RM) that supports reasoning about function allocation and distributed cognition has been developed by Fields [1,2,4] with colleagues at York. RM makes ideas from distributed cognition more directly applicable to HCI, and therefore offers an applicable framework for considering how people and technology work together. The RM consists of a typology of information resources and strategies that users employ in deciding how to act. It has been used successfully for: generating design ideas; understanding differences between different designs; and reasoning about team working with multiple resources.
Programmable User Modelling (PUM) also represents soft aspects rigorously. PUM was originally developed to support cognitive modelling for evaluating interactive systems. Blandford [1,4], Butterworth [1,2,4] and team extended the PUM scheme to support formal reasoning and proofs about interaction and to facilitate rapid uptake of modelling in real-life development. A formal model of rational interactive behaviour was presented, and used to support reasoning about users’ knowledge needs for interactive systems. Both formal proof and simulation approaches have been tested. Building on results of the PUMA project and Curzon's previous work on formal verification, a prototype verification methodology has been developed that provides formal verification support to eliminate a variety of classes of user errors from interactive systems (Curzon & Blandford, in press). The methodology, based on a generic user model in higher-order logic, has been shown to detect post-completion errors, communication goal based errors and some delay errors. Curzon's previous work, listed under HCI to reflect his current affiliation rather than history, demonstrated how interactive proof could be used in the verification of ATM communication chips, identifying the strengths and weaknesses of the approach as compared with automated tools [Curzon 2,3]. With his PhD student, Xiong, he demonstrated how the linkage of interactive (e.g. HOL) and automatic (e.g. MDG) verification systems could be formally justified [Curzon 1,4].
The Digital Library group addresses computer science, HCI and cultural issues in the design and use of digital library systems and tools. This builds on earlier work on hypermedia authoring.
Authoring tools have been developed to support the production, maintenance and evaluation of hypermedia. For example, Gentler [Thimbleby 3] particularly addresses issues of maintaining consistency raised by collaborative authoring. The work involved a close relationship with the Royal Society of Arts, who used products from the project to develop their Web site; the quality of this work led to consultancy with EPSRC and the Arts and Humanities Research Board. The group also designed and implemented the Royal Academy’s web site using its tools, and ran the site until 1999. Theng [1] analysed the nature of tasks people engage in while navigating hypertexts, and used that analysis to inform the design of HyperAT, a hypertext authoring tool to help authors manage the structure of hypertext documents and automate aspects of usability evaluation [Theng 3].
Configuration tools have been developed for digital libraries, particularly for distributed collection management across multiple platforms; these have been adopted by Waikato. Group members have been investigating the design of digital libraries for and by children. A questionnaire study with adult users established users’ views on desirable features of the digital library [Duncker 2]; when extended to elicit views from children, the work resulted in a set of design guidelines for digital libraries for children [Theng 4]. Cultural aspects of digital library design have been investigated [Duncker 3], including the use of metaphors and choice of colours in interface design.
The Personal Technologies group is concerned with the use of computer technologies in mobile systems and personal contexts. Studies have addressed both social and technical aspects.
From a social perspective, Thomas [2] and Blandford (in press) have studied the use of electronic and paper personal information management tools. This work has identified many of the issues that account for low take-up of electronic tools, including mismatches between user tasks and those supported by the current generation of electronic tools.
From a technical perspective, Jones [1,2,4], Thimbleby and others have developed tools to enable materials created for conventional displays to be used effectively on much smaller screens such as handhelds; following a tutorial at Web9, this has been taken up by Terry Winograd’s group at Stanford. Algorithms such as hashing have been used to improve user interface effectiveness [Jones 3]. After review by EPSRC and the Ergonomics Society, this work was selected for exhibition at the London Science Museum. Thimbleby, Cairns and Jones (in press) have developed quantitative models to predict user costs – principally the time to achieve goals for given user knowledge. The value of these models has been demonstrated by applying them to various interface designs for pervasive technologies like video recorders and mobile telephones. Thimbleby [4], starting from the premise that design is (or should be) an ethical activity, has proposed a set of design probes that support thinking about design requirements for hand-held devices. He has also presented mathematical analyses of various classes of devices, whereby particular usability features can be measured; for example, Thimbleby [2] analyses a particular pocket calculator, and demonstrates how this style of analysis can expose unreliable and inscrutable design features that undermine usability. One area of concern for mobile systems is the proliferation of malicious code. Cairns [2] and Thimbleby have developed a formal model for viruses and Trojan horses that gives clarity to our understanding of the way defences can be mounted against them. Further work is ongoing.

Artificial Intelligence: Main Achievements
This group, formed about 18 months ago, has achieved notable results applying both symbolic and sub-symbolic AI techniques to address important practical problems. The group’s two main themes are neural networks and natural language understanding.
In neural networks, one focus has been on modelling and prediction. The main application areas have been medical informatics and semi-conductor manufacture. Wu [4] applied the growing cell structures (GCS) neural network to the prediction of coronary heart disease based on short-term electrocardiogram measurements. Binary encoding of Poincare plot encoded data was found to produce good results when applied to a trial group. Bavan [1] applied a content associative memory model to recognise protein sequences based on protein fragments; this model permits multiple associations and outputs (unlike traditional neural nets), and was shown to have a higher saturation point and be more efficient than existing techniques. Meng [1,2,3,4] has applied neural networks to modelling and prediction of semiconductor manufacturing processes. She developed a static neural model of a reactive etching system. This model was shown to predict the behaviour of the actual system more accurately than statistical models. A dynamic model formed the basis of a hybrid neural network regulator, combining a neural emulator with a neural controller. This has been shown to provide accurate control of the reactive ion etching process under various operating conditions.
Neural networks have also been applied to natural language understanding. At the lowest level, Mitchell [1,4] and Bavan have developed a neural network for sequence recognition which has been applied to multiple word retrieval problems. Mitchell [2] found that retraining was faster than other systems when incrementing the training set . The ability of the system to retrieve multiple target sequences from a single input sequence resulted in a solution to the variable binding problem.
At a higher level of natural language understanding, Wu [1,2,3] developed a novel Symbolic / Connectionist System to assist in word sense disambiguation. It integrated a knowledge-based system with standard neural network algorithms. On trial, it correctly disambiguated 95% of test sentences. Huyck [3,4] has developed a parsing system, Plink, that is capable of parsing non-grammatical sentences (unlike related systems) and performs well on the Penn Tree Bank's parsing metric. Huyck also developed a biologically plausible neural system, CANT, that simulates Hebb's cell assemblies (CAs) – that is, reverberating circuits of neurons. CANT has captured many of the physical properties that CAs must have [Huyck 1,2].
Mitchell [3] has applied genetic algorithms to solve travelling salesman problems; he developed a temporal chromosome that could incorporate parallel message passing. This representation avoids the repair procedures that plague other evolutionary approaches to this problem. Such a representation creates a wider gap between phenotype and genotype, improving the scope for gene crossover, mutation and reproduction. This also leads to a generic chromosome representation that can be used to solve many graph problems; developments are ongoing.

Information Systems Engineering: Main achievements
The Information Systems Engineering group combines interests in both information systems and software engineering, and focuses on two main areas of work. The first addresses the interlocking domains of processes, methods and technologies used in the development, acquisition, operation and support of software-based systems. The second area addresses products, specifically models and software artefacts for use in applications such as business and medicine.
Work on processes, methods and technologies studies systems and practice within the social, organisational and technical context. It investigates what influences the performance of practitioner groups, and how their performance influences that of the enterprise. Woodman's work [1,2] on software process improvement and quality assurance has produced novel analyses of how social and cultural facets of organisations impact software development. In addition, it has described how software engineering communities are formed from constituencies across the profession, in organisations and within projects, and has demonstrated how established social sciences may be used in exact research into technical processes. Duncker [4] has used similar methods to develop a principled account of how the participation of end-users, or lack of it, affects software development. Work by Galal [1,2] adapted the grounded theory method from the social sciences into the GSEM (Grounded Systems Engineering Methodology), to support requirements engineering and systems design, situated in a rich human context. Requirements elicited using GSEM are fully traceable within the application domain, and hence verifiable by end-users. End-user computing (EUC) is another aspect of the ISE group's work. Lawrence [1,2,3] has developed a practical, survey-based instrument which enables organisations to profile business users in terms of their potential for effective end-user-led IS development and to model EUC effectiveness factors. A series of surveys confirmed that the levels of role power and freedom and of tool suitability are highly significant indicators of effective end-user IS development. Jenkins [1,3,4] has continued earlier work on resource estimation in software project management by refining these models, to the extent that they are the basis of commercial project management tools developed by Volmac. In object technology, Woodman [3,4] has shown how objects packaged as components can be used in building customisable environments, and has also contributed to the prediction of the performance of object-oriented databases. The programming environment and tools his team produced have been used by about 20,000 students worldwide. Also in the area of database technology, research by Revell [1,3,4] and others has considered the design of temporal object databases, resulting in the development of a temporal querying algebra. The FIBEX data extractor [Revell 2] generates index files from semi-structured document files, such as those typically used in digital libraries. Abeysinghe [2] has worked on improving the accessibility of formal notations, especially CSP.
The second area of work relates to IS products, through which computing contributes to other domains. Abeysinghe [1,3,4] has applied her approach to enable business professionals, especially in the construction industry, to model processes. Hanson [1,2,3,4] has applied a range of software development methods to deliver products that support the work of companies in novel chemical synthesis, e-publishing, banking, printing, packaging and pensions organisations. The work of Evans is also oriented to products that contribute to other domains, in his case medicine. In collaboration with Winter (Institute of Child Health), he has addressed problems relating to the delivery of clinical and genetic information from databases over the Internet. Evans' team have developed two major software systems relating to dysmorphology using Internet technologies. Two journal papers describe the theories behind the development of these systems [1,2]. The systems produced [3,4] are being used by clinicians. Information is now accessible globally and presented in a form that is tailored to the needs of specialist users in dysmorphology and genetics. Information on cases and syndromes is keeping pace with the literature and consequently supporting diagnoses more efficiently than is possible with standalone databases. Successful diagnosis can aid the counselling given to parents, such as the risk of recurrence and the prognosis for an affected infant.

Information Systems Engineering: current work and future strategy
As the ISE group further establishes itself and newly-arrived members become integrated, some reorientation of work is taking place. For example, the recently started OOSPICE project, funded through EU Framework 5, is investigating the impact of object-oriented and component-based development (CBD) on the SPICE approach to software process improvement and capability assessment. The project aims to produce a metamodel of CBD and a revised reference model for the emerging ISO SPICE standard. Through OOSPICE, Jenkins and Woodman are now concentrating their work on processes and object/component technology, and new members of the ISE group are using it for investigating process improvement in failure-prone development and rapid production of e-business systems. The theme of e-business is also evident in other developments spearheaded by the group. Woodman is working with several companies to establish an e-business centre to focus research and to accelerate technology transfer and support businesses in North London. This work is being extended to an international project for on-line and mobile support for enterprise development.
Group members are also establishing a centre for studying systems failures; preliminary funding of £10,000 has just been obtained from industry to support this work. A core resource will be an established repository on failures. Within this context, new members of the group are extending their work on software quality and the impact of organisational practices.
Abeysinghe is continuing to develop her work combining semi-formal and formal models for use in business. With a recently won EPSRC grant (GR/N02368), she is collaborating with Huyck of the AI group to introduce Natural Language Processing to allow her models to be used by end-users. Lawrence is carrying out further evaluation of his instrument to model EUC success factors in a large UK organisation (finance sector) within a study of EUC management and support. Future work will identify detailed features needed for effective EUC support, and will lead to the development of prototype EUC tool software.
Research into tools and technologies is to be further directed towards the areas of database technology applications. Hanson is extending his work on knowledge management to support corporate activities [Hanson 4], through a follow-up TCS project. Evans is extending the systems reported above, and conducting rigorous testing on them. He is collaborating on a new MRC Co-operative Group Grant on bioinformatics as the partnership’s computer scientist.

The School of Informatics and Multimedia Technology has gone through an important period of change leading to the development of a research culture based on three main research groups. In 1998 the name of the School was changed from School of Computing to the School of Informatics and Multimedia Technology (SIMT). This signalled a strategic repositioning of the School to align itself with significant developments in the subject base and stimulated the recruitment of staff in the newer areas of multimedia technology. As the School has continued to expand this development has been paralleled by the recruitment of strong research staff from traditional areas of Computing and Software Engineering.

The Department has chosen to submit as research-active only those academics who can demonstrate both international recognition and a minimum of four journal publications in the assessment period. This has led to a reduction in the number of staff nominated as research-active, instead of the planned increase. Nevertheless, the Department is proud to have achieved its aim of broadening its research culture and increasing its research output across the whole Department (see RA6c). The record number of 29 PhD successes in the last five years illustrates the mature research culture that permeates the Department.

Research activity in the Department has continued to progress in three complementary and mutually-supportive research groups, as described in RAE’96:
• Intelligent Simulation and Modelling – previously referred to as Real-Time Telemetry Systems;
• Intelligent Recognition and Interactive Systems (IRIS) – this group has evolved from the Handwriting Recognition Group to include our rapidly-growing research into interactive systems;
• Real-Time Machine Control (RTMC).

Prof. Hopgood joined as Head of Department on 1/1/2001. His interests in intelligent systems and their practical applications complement all three research groups. In the first instance, he plans to develop his research within the IRIS Group, while promoting Intelligent Systems as the integrative theme of the Department (RA5c).

Strategic planning and monitoring of research in the Computing Department is managed through the Departmental Research Committee, whose main objectives are to sustain and develop the quality and profile of departmental research, provide cross-fertilisation of ideas, promote team strength, implement research supervision standards and facilitate research development of individual staff, e.g. through mentoring and sabbaticals. The committee promotes dissemination of research results (see http://www.doc.ntu.ac.uk/research.htm), publication of working papers and the presentation of research seminars. Our seminars are open to all, thereby maximising awareness of the Department’s research. All these activities serve to open our research to peers’ scrutiny and promote a research ethos. They are part of our continued commitment to encouraging all staff to be research-active and providing the best environment for the development of research excellence.

The selection of the application areas for the Unit’s research was influenced by the Government priorities for addressing urban sustainability (urban transport – GR/K16593, GR/G32468), environment (water distribution systems – GR/N16369), wealth creation (spin-off companies: Pacer Systems Ltd., Axiomatic Technology Ltd., IC-Routing Ltd.) and quality of life issues (Virtual Reality Systems for the disabled; EC – 982111UK8).

As well as its own network of computers dedicated to research, the Department has access to a £1.2m Faculty Research Institute that provides additional computing facilities and a suitable environment for both individual and group work. A new virtual reality simulation facility has been established with the help of EC funding (EC-982111UK8). Our strong industrial links offer the opportunity of access to external resources such as on-line access to real-time traffic control computers at the Nottingham Traffic Control Centre, equipment and instrumentation through our spin-off companies, and test data sets provided by NSK-RHP and Rolls-Royce.

Intelligent Simulation and Modelling Group
The work of the Intelligent Simulation and Modelling group is focused on processing uncertain and multi-resolution data and the development of parallel and distributed processing algorithms. This focus matches the current national and international definitions of the Simulation and Modelling field, which indeed were shaped through active contributions from our staff. The group has a strong base of nine academic staff, of whom Dr Al-Dabass, Prof. Bargiela, Dr Claramunt and Prof. Evans are named in RA2. The work has been supported by EPSRC (GR/K16593, GR/N16396, GR/N10813, GR/R10707, GR/R32468) and industry.

An efficient analogue neural network for processing uncertain data has been developed in collaboration with the Artificial Brain Systems Laboratory, Japan [see AB-1 in RA2]. A generalised neural classification and clustering technique, that builds on our neural confidence limits analysis methodology (work reported in three journal papers), has been developed and validated as an abstraction-forming and decision-support tool [AB-2]. A fault-tolerant framework for the implementation of a decision-support system has been developed [AB-3]. An important theoretical result of global convergence criterion for fine-grained genetic optimisation has been achieved [AB-4]. The objective of developing a Bulk Synchronous Parallel (BSP) fault-tolerant system has not been pursued because of the changing emphasis in the computing and telecommunications industry. Instead, research into fault-tolerant mobile simulation environments has been carried out in collaboration with British Telecom (STRF00/31) and Psion Industrial (GD/EG97-10), leading to four research publications.

A novel hierarchical approach to fuzzy possibilistic reasoning was developed and shown to have excellent properties in recognising 2-D patterns [DA-1, DA-2]. A self-organising/self-adaptive architecture for artificial neural nets was devised and shown through simulation to be effective in classifying multi-dimensional patterns [DA-3]. Examination of levels of parallelism in processing neural net algorithms [DA-4] led to the conceptual design and simulation of an efficient parallel-processing architecture.

Basic research on the representation of spatio-temporal processes within GISs has been accomplished. Current extensions of this research include the development of the approach for the representation of composite processes, the database modelling of spatio-temporal processes, and the application of the framework to socio-economical studies and traffic systems [CC-4, CC-2]. Significant research contributions include the integration of graphs within spatial databases [CC-3] and the modelling and simulation of urban structures within GISs [CC-1].

The design of VLSI processor arrays for neural network applications for pattern classification [DJE-1] and the solution of large sets of finite element equations by parallel and genetic algorithms [DJE-2] have been applied to non-invasive neuroscience applications on human brain modelling by magnetic resonance imaging. This work has been funded by the EPSRC (GR/N10813). The design of parallel asynchronous algorithms for a Beowulf PC cluster, supported by the Association of Commonwealth Universities, is given in [DJE-3 and DJE-4].

Intelligent Recognition and Interactive Systems (IRIS) Group
This group comprises eight academic staff, of whom Prof. Hopgood and Dr Brown are named in this submission. The group’s research falls into two distinct but closely related areas, i.e. intelligent recognition and interactive systems. Our intelligent recognition research is focused on handwritten, naturalistic, gesture and natural language interactions with computers. Despite the departure of three active researchers (Prof. Whitrow, Dr Palmer-Brown and Dr Rose), Dr Sherkat took over leadership of this research and has published two papers in refereed journals and 21 at conferences during this period. His work is has been supported externally, notably cursive handwriting in facsimile images funded by GCHQ Cheltenham (F11C1/74650/C).

In contrast, our research in interactive systems has seen dramatic expansion. Dr Brown joined the University in 1998 and rapidly created a thriving area of research into interactive multimedia systems for socially-excluded people. Multimedia-based training tutors are being designed to develop skills related to work, travel, numeracy and literacy in users having learning or physical disabilities. This initiative, known as Greenhat Interactive, has attracted funding from the EU Adapt Fund (982111UK8), European Social Fund (001075WM3), ESRC (R000223018), New Opportunities Fund (E/CLL/2000/ 36), National Lotteries Charitable Board (MC022476), and DETR Invest to Save (RE245).

Methodologies for the evaluation of virtual learning environments have been developed [DJB-1, DJB-2] and an assessment of whether constructivist developmental theories provide a suitable conceptual design framework for virtual training environments has been made [DJB-3]. An important result of the ESRC-funded work was the new strategy for embedding intelligent virtual tutors within the scripting of virtual learning environments [DJB-4].

Work in the area of instrumentation has led to the development of the patented incremental motion encoder (IME) [PDT-2] which has received industrial support from Heidenhain GmbH and Hewlett Packard. The multinational bearing manufacturer NSK-RHP is currently applying the techniques at the Ruddington Research Laboratories. Recent work on 3D shape description has led to improved techniques for triangulation of point cloud surfaces and segmentation of the surfaces based on curvature estimates. This work is supported through collaboration with the Forschungszentrum in Karlsruhe. It builds on our track record in scanning and image processing [PDT-1], the mathematics of shape description, particularly the fairing of non-uniformly parameterised curves [PDT-3], and engineering drawing interpretation [PDT-4].

Staffing Policy
The Department is committed to the development of high quality teaching and research. Undergraduate student numbers have been deliberately reduced by over 30% during this RAE period by raised admission requirements. This has had the dual benefits of an enhanced academic ethos and creating more time for staff to devote to research. All academic staff are now guaranteed two days per week free from teaching commitments, to encourage research.

The University provides training to help staff develop their research potential, such as workshops on research supervision and writing grant applications. Within the Department, senior researchers encourage and mentor less-experienced staff. All staff are encouraged to participate in research seminars, which are conducted in a constructive and supportive atmosphere. The University appraisal system provides for performance review and agreement of objectives, together with the identification of any staff development needs. Internally-funded research studentships (10 in the current period – see RA3b) are used to encourage younger members of staff to become involved in research supervision. Where appropriate, members of staff are encouraged to register for research degrees – two staff members are registered externally; Dr Peytchev and Dr Stout completed their PhDs while in post during the current period. Such systems have successfully created a research culture, demonstrated by the substantial increase in research activity shown in the table on page 1 of RA5a.

The increasing development of research-based modules in courses at undergraduate and postgraduate level has benefited both staff and students. Most final year modules on our fully-accredited BSc programme have emerged from departmental research — recent examples include Multimedia Systems, CAL, Graphics for VR and Natural Language Processing. Similarly, our research in simulation, modelling and visualisation is also central to a combined maths/computer science degree currently under development. Many student projects on taught courses are based on current research, notably our industrially-sponsored MSc Real-Time Computing Applications.

The University has recently appointed Prof. Hopgood as Head of Department with the principal remit of developing research. There have also been seven permanent lecturer/senior lecturer appointments during the last five years, all of which took into account the potential contribution of the candidates to the departmental research profile. The Department was successful in attracting high quality staff in the early stages of their academic careers. Prof. Hopgood and two of the other new appointees (Dr Brown and Dr Claramunt) are explicitly included in this RAE submission. The others are developing rapidly and their research outputs are expected to reach the standards that we have set ourselves for submission in the next round.

Research Organisation and Infrastructure

The University's Strategic Plan gives very high priority to the enhancement of research activity and has appointed a Pro Vice-Chancellor to promote policies that encourage the pursuit of research excellence. Research is managed through the University's Research and Consultancy Committee and the Research Degrees Committee. Both committees are supported by the University Research Centre that also offers a comprehensive series of domain-independent training seminars for research students and new supervisors. Domain specific training is provided within the School. Professor Pidcock (returned in UoA 23) represents the School in the University research committees; and chairs the School Research and Consultancy Committee and the School Research Degrees Committee. A Postgraduate Research Tutor is responsible for the welfare and administration of research students and for the monitoring of their progress. Since research students form a major part of the School's research effort, fostering a strong research culture amongst the students is a priority. Each student is supported by a team of at least two supervisors (which may include staff from both parts of the School) and students are asked to give papers to the School's Research Colloquium on a regular basis. Career development assistance is also offered in the form of a wide range of teaching opportunities.

Distributed Systems Research Group (Head Professor Duce)

Network performance engineering: Dr Ball

Contributions: This work, which is grounded in analytical queuing theory and simulation, has made a number of significant contributions to the subject of resource control in multiservice networks. The group's work has placed great importance on the support of continuous media and has not treated this as a simple delay sensitive version of "normal" computer data. One of the major outputs of this work has been a comparative evaluation of Sorted Priority Algorithms and Class Based Queuing (CBQ) [Ball 1,4]. The results have provided the answers to a number of very important questions regarding the effectiveness of each in meeting the needs of various types of traffic.
Another major contribution has been the development of a Measurement Base Flow Acceptance Control Mechanism for use with CBQ in packet switched networks [Ball 1]. This mechanism is primarily intended for providing guaranteed services to continuous media traffic and can work with either individual or aggregated flows.
A solution to the problem of mapping IPv6 flows onto ATM cell streams has been developed. Although based on the QoS requirements of continuous media traffic, it could be used for data traffic with minor modification. Finally, the research into reactive congestion control for adaptive continuous media has identified the requirements for this type of media, and has clearly shown that existing methods used for computer data are generally unsuitable for this purpose.

Formal methods: Dr Reed, Professor Duce, Dr Simpson, Professor Cooper (Visiting Professor)

Contributions: Reed's work on formal methods for the design and analysis of networks naturally divides into deterministic parallel computing and non-deterministic parallel computing. In the field of deterministic parallel computing, a ground-breaking paper illustrated that a formally developed model of bulk synchronous computing could produce scalable parallel programs for diverse parallel architectures [Reed 1]. The strength of this work is that it demonstrated that an abstract elegant model could accurately predict behaviour of a single source code across different parallel platforms.
The objective of the work in non-deterministic concurrent systems is to scale up formal methods for application to industrial-sized applications. A significant contribution was the development of induction techniques for the finite-state model checker CSP/FDR which allows modelling and analysis of certain arbitrary-sized network protocols. Such techniques can be used to reveal undesirable behaviour such as potential deadlock for network protocols [Reed 2,4].
This work suggests another approach for making formal methods more effective for large applications: a mixed paradigm which plays to the strengths and overcomes limitations of individual tools and techniques. An in-depth study identifying advantages and disadvantages of certain existing formal methods for routing protocols [Reed 3] has revealed advantages and disadvantages for large-scale use not previously recognised in existing formal techniques.
Duce is developing an approach to describing and reasoning about the conjoint behaviour of user and system models, called Syndetic Modelling, in collaboration with Dr Duke (Bath), and two psychologists, Dr Barnard (MRC Cognition and Brain Sciences Unit, Cambridge) and Dr May (Sheffield) [Duce 2,4]. The work started by applying formal mathematical modelling techniques of the kind found to be effective for modelling the computer side of interactive systems to describing Barnard's Interacting Cognitive Subsystems model of human cognition. The work so far has resulted in an approach to reasoning about the deployment of cognitive resources during an interactive task.
Duce also contributes to standardization activities, including PREMO (ISO/IEC), where his work concerns the use of formal techniques to support the development of standards [Duce 3].
Simpson in [1], together with colleagues from the University of Oxford, described how the formal description technique Communicating Sequential Processes (CSP), together with the refinement checker Failures Divergences Refinement (FDR), can been applied to the analysis of safety invariants for geographic databases associated with Solid State Interlocking railway signalling systems. A technique for modelling such databases, and their safety invariants, in terms of sequences of events, and a refinement-based method for reducing the complexity of the verification of geographic data were developed. It was established that a task normally carried out manually at enormous cost, in time and manpower, could be reduced to a series of automated checks.
In [Simpson 2] it was shown that the concept of non-interference, which is normally associated with theories of security, may also be used to reason about safety properties. A technique for modelling safety properties in terms of communicating processes and a practical theory for reasoning about the protection of systems from failures were presented.
In [Simpson 3], it was shown how a combination of Z and CSP may be used to aid in the development of appropriate policies for the secure integration of untrusted code in an otherwise trusted environment. The Z notation was used to describe how desirable security requirements may be expressed and combined, and CSP was used to analyse the possible behaviour of combinations of such requirements. In addition, it was shown how the notions of determinism and refinement may be used to verify that combinations of security requirements behave as desired.
In [Simpson 4], the language of CSP was applied to the analysis of a transport layer protocol used in the implementation of the Bulk Synchronous Parallel model (BSP). The protocol was modelled using CSP and verified using the refinement checker FDR2, establishing not only that the protocol is free from the potential for both deadlock and livelock, but also that it is fault-tolerant.

Distributed cooperative visualisation: Professor Duce, Professor Cooper (Visiting Professor)

Intelligent Systems Research Group (Head Mr Nealon)

Intelligent agent technology: Ms Greenwood, Mr Nealon, Dr Zhu

Contributions: The focus is the investigation of frameworks that support agent-oriented computing particularly in distributed environments. There are already available frameworks for mobile agents that support sending a segment of code to remote machines to execute, however these frameworks do not provide support for co-operation between mobile agents and services in remote machines. An architecture, VISITOR, to support mobile agent computing has been developed which supports flexible communication and co-operation between mobile agents and local agents, where the latter provide services through an agent broker [Greenwood 2,3]. A later development (carried out in collaboration with BT at Martlesham Laboratories, who partly funded the project) was the use of this architecture to support a system delivering a virtual call centre on the Web.
Work has been undertaken on the novel application of mobile agents to the area of software testing [Greenwood 4]. More recently Zhu and Greenwood have been developing approaches to agent–oriented quality management of distributed hypermedia and cooperative information systems. Work has continued in the medical informatics area investigating the use of an intelligent multi-agent approach to building an interface to medical databases. This research is carried out in conjunction with Nealon and his work on the diabetes treatment advisor [Greenwood 1].

Intelligent medical informatics: Mr Nealon, Ms Greenwood

Contributions: The work in intelligent medical informatics (undertaken in close collaboration with Professor R Holman of the Diabetes Research Laboratories (DRL) and Head of the Diabetes Trials Unit (DTU) at the Nuffield Department of Medicine, Oxford University) has made a major contribution to the treatment of insulin dependent (Type 1) diabetes. Initially the researchers at Oxford Brookes developed prototype software for an early handheld computer, operated through a touch sensitive screen, which was used to validate in a small clinical trial a new approach to the optimisation of insulin treatment, proposed by the collaborating physicians. This approach is much simpler for the diabetic user and more robust than that employed by the only previous insulin dosage advice computer system, developed in the United States, which required detailed information in absolute and quantitative terms, without the possibility of missed data entries, at each insulin dosage event. The new approach, in addition to blood glucose levels, required only relative qualitative data on health and food intake, and could continue to operate with sparse data, while providing excellent advice and data visualisation to the patient. The successful validation of this approach enabled the researchers to develop an intelligent patient advice system and a clinic-based data collection and patient system configuration program. These systems underwent a very successful full hospital clinical trial, directed by the DTU at the Radcliffe Infirmary in Oxford [Nealon 2]. Later, the software was ported to newly available handheld hardware. Despite the success of the clinical trial this approach remained one of several approaches. A later study (published in the Lancet and British Medical Journal) unambiguously placed this approach to insulin treatment optimisation at the forefront of diabetes treatment worldwide.

Neurocomputing: Dr Crook

Contributions: Work on neurocomputing began with an investigation of biologically plausible neural networks (with CH Dobbyn, now at the Open University and the collaboration continues). A dynamic neural network architecture called DENN was developed which was capable of perception switching in a visual field. Another area of investigation involves the development of tools for explaining the output of trained neural networks. The knowledge stored in neural networks is distributed across the network weights, which makes it difficult to explain or justify network output. Several methods of extracting rules from trained networks were developed, including the use of input parameter influences [Crook 3].
In 1997 Crook began research on the utility of chaos in neural networks as a means of storing and retrieving memories [Crook 4]. The presence of chaos offers enormous advantages to the developer over other non-chaotic dynamics: chaotic systems are considerably easier to control than other linear or non-linear systems, requiring only small appropriately timed signals to stabilise the Unstable Periodic Orbits (UPOs) which are embedded in the chaotic attractor, and chaotic attractors have an infinite number of UPOs embedded within them. If each UPO was used to represent a unique dynamic memory state, then there is a theoretically infinite capacity for memory storage. UPOs are trajectories in state space and some trajectory classification methods have been investigated [Crook 2]. A novel architecture has been developed for a chaotic neural network which incorporates a neural implementation of the delayed feedback method for controlling chaos. New methods for learning and adaptation have been developed and applied to this architecture.

Speech: Mrs Zajicek

Contributions: The focus of the speech group has been on techniques that enable blind and visually impaired users to scan Web pages and sites in an equivalent way to sighted people when searching for information. The group has developed a Web browser, called BrookesTalk, which can be used as a speech only browser or with a combination of speech and visual output. BrookesTalk was awarded a medal for innovation in the British Computer Society IT awards in 1998. The work was carried out in collaboration with the Royal National Institute for the Blind. BrookesTalk uses synthesized speech output and features include document summaries and page abstracts [Zajicek 1,2,3].
Funding has been obtained from the Spanish Association for the Blind to work with linguists at the University of Barcelona to build a Spanish version of BrookesTalk and from the Microsoft Active Accessibility awards initiative to integrate BrookesTalk with Internet Explorer.
Zajicek collaborates with the School of Health Care to explore how to support older people (where loss of short term memory, sight and hearing are all factors) in using the Web [Zajicek 4]. A first prototype, BrookesExplained, supporting Universal Access principles, has been built and tested.

Uncertain reasoning: Dr Wilson

Contributions: Wilson has developed a detailed analysis of the problem of computing Dempster-Shafer belief and related problems, looking at both exact and Monte-Carlo algorithms, applied both to product sets and the standard case of a listed frame of discernment. With S Moral (University of Granada, Spain), he developed Monte-Carlo algorithms for computing, up to (any) given accuracy, Dempster-Shafer belief in the standard case which are almost linear in the size of the frame of discernment (whereas the exact problem is known to be #P complete) [Wilson 1]. He contributed a chapter on Algorithms for Dempster-Shafer Theory to the Handbook of Defeasible Reasoning and Uncertainty Management Systems which incorporates a significant body of original work [Wilson 4].
Wilson has developed a simple theory of infinitesimals, leading to a nice system of infinitesimal probability [Wilson 2]. This can be used in the semantics of a number of theories of belief revision, default and non-monotonic reasoning, and also as an extension of Bayesian networks. A logic of probability has been constructed that allows ordinary statements of probability to be mixed with statements of infinitesimal probability, which allow default-type reasoning. This expressive logic has a very simple proof theory that is complete for finite sets of statements [Wilson 3].
He has also shown (with Mengin, Université Paul Sabatier, Toulouse) how the general computational scheme known sometimes as "Local Computation" (which was developed in the sphere of uncertain reasoning) can be applied to theorem proving in many classical and non-classical logics used in Artificial Intelligence.

Requirements engineering and software testing: Dr Zhu

Staff Movements and Staffing Policy

The DTI recognises CAS as a "Centre of Excellence" in the application of intelligent computing and adaptive systems to industrial problems. Raj Rao, a world expert in condition monitoring is a Visiting Professor to the Centre, and the COMADEM conference was held in Sunderland in 1999.

SUGAL (Sunderland Genetic Algorithm system) has been developed by Andrew Hunter and has more than 2000 users around the world. Andrew Hunter also collaborates with Lee Kennedy (a joint appointment as Professor at the University and Consultant Physician at the City Hospitals) in the health area, for instance on the automated diagnosis of diabetic retinopathy.

Staff in Computer Science at Sunderland plan and monitor their research in a systematic manner. The institution has provided significant financial backing for these plans and in turn this has made it possible to provide sabbaticals (an average of two per year since 1997), teaching relief and travel funds to support both research active staff and to allow research inactive staff to start new lines of research. A system of administrative and technical support has also been developed.

Non-research-active staff can be given timetable relief to initiate new, specified research activities. Where appropriate they are encouraged to register for part-time PhDs. Alternatively they may be encouraged to contribute to research projects led by other members of staff or to contribute to research student supervision and monitoring in areas related to their technical expertise.

A small number of posts (two research professors and two research lecturers) with particular responsibility for developing research, rather than teaching, have been created. The filling of these posts (especially the professorships) has allowed the research culture in Sunderland to blossom in ways which would not have been otherwise attainable. The two Professors (Gilbert Cockton and Stefan Wermter) have brought to Sunderland a real understanding of quality at the highest level and how to achieve it. Their expertise has helped a number of longer established staff to significantly improve their publication and funding records.

Improvement in the quantity and quality of research among all staff have been supported by: targeted timetable relief with clear objectives; clear targets through the appraisal process; paper writing and research proposal development workshops; and the mentoring of less-experienced researchers by those who have greater experience in publishing.

The CSRC already enjoys a vibrant research culture. Since 1996 our aim has been to greatly strengthen our national and international reputation for applied computing research so as to become a leading centre for inter-disciplinary research in the UK. New research areas have been developed in data compression, computer modelling and the application of meta-heuristic algorithms to radio frequency assignment and automated software testing. The CSRC’s research is divided into four sub-areas: Information Systems, Digital Imaging, Applications of Adaptive Algorithms and Computer Modelling. Substantial numbers of papers have been published in each sub-area in international journals and conferences and they have been cited widely.

The quality of our research has been recognised both nationally and internationally by the award of prizes, the number of collaborations with prestigious international universities and Research Institutes and the appointments of researchers to Journal Editorships and Editorial Panels.

The Development of Inter-disciplinary Research since 1996
We have enhanced both the quantity and quality of our research and the current submission covers the work of more than twice as many researchers as in 1996. Research output quality has been further improved, and is now concentrated in peer reviewed journals at the international and national level. There has been a fivefold increase in the number of higher degrees awarded; about 60% of our Doctoral graduates have taken up lectureships and post-Doctoral fellowships in Universities and the remainder have joined industry and research institutes across Europe. The six-fold increase in external income achieved the goal set in 1996. We were awarded two British Computer Society Medals in successive years (1996 and 1997) – a unique achievement for a British University.

Research in Glamorgan is organised by means of Research Units which are specialist groupings of researchers and which form the main thrust for advancing the University’s research culture. CSRC comprises Research Units from a wide range of disciplines reflecting its longstanding track-record in inter-disciplinary research with mathematics, medicine and sociology; important and exciting innovations since 1996 have been the development of inter-disciplinary links with electrical engineering and chemical physics. Our research has contributed, for example, to advances in radio frequency propagation and to our knowledge of the molecular structure of organic molecules as well as to Computer Science.

In 1996, our aims included the retention of new PhDs as post-Doctoral Assistants alongside new blood appointments. The successful implementation of that policy has contributed to the strength of this submission.

There has been a significant uptake of our research by industry and commerce. The Kane-Thompson Centre (KTC) for studies in information systems and information technology was established, as planned, with funding from the ERDF (£115k). One of the key aims of the KTC has been to build more effective links between IS academics and IS practitioners. The KTC has promoted this by providing IS/IT forums and seminars, briefing papers and work on research projects for its members. This activity is planned to continue in the future as the Glamorgan Information Systems Centre. An outstanding success for the University is that we have the largest number of Teaching Company Schemes of any University, demonstrating our commitment to technology transfer. Our research has been commercialised in spin-out companies and licensing agreements. The radio-frequency assignment work has expanded substantially with the production of software tools and fundamental models of radiowave propagation. This research is being exploited by the Swedish company, ComOpt, and by BAE SYSTEMS. Active participation in the National Radio Propagation Programme (NRPP) has ensured that the results of the research are widely disseminated to both users and service providers of mobile, internet and radio-communication services. As a result more efficient utilisation of the radio spectrum has been achieved. The MAPLEX automated cartography software was marketed by the spin-out company, HollyBush Software, which was sold to Environmental System Research Institute, California (ESRI), one of the 50 largest software companies in the world. A spin-out company to market a miniature version of the MAVIS wound measurement instrument is being developed with Scientific Generics (Cambridge). MAVIS is in use in several UK, Scandinavian, American and German hospitals and research institutes. We have developed and currently maintain the GNU Modula-2 compiler. Our Centre for Electronic Product Engineering is recognised as a Centre of Expertise by the WDA and has played a key role in transferring electronic and computing technology to Welsh industry. It was involved in projects totalling £2.2M in value over the RAE period; funding was provided mainly by the DTI and Europe and is in addition to the income quoted in RA4.

The research of each sub-area will now be described.

1. Information Systems (IS)
The bulk of the IS research is in Geographical Information Systems (GIS). The GIS group was established some 20 years ago and has developed highly successful lines of research as well as introducing new areas of activity and new collaborations. Notable progress was made in the areas of terrain modelling for visualisation (National Windpower £18k: Kidner), radio wave propagation and compression techniques for spatial data. We have pioneered the application of triangulated spatial data models for multi-scale databases and map generalisation and provided the first examples of dynamic graphical conflict resolution using various optimisation techniques. Our work on qualitative spatial reasoning has led to a general formalism for data integration and the handling of imprecise knowledge, and the development of a model for spatio-temporal reasoning to support enquiries on pattern and causality. The research was supported by two NERC grants (£130k: C.B.Jones). The Maplex software project was awarded a BCS Medal in 1997. Two new professorial appointments (Higgs and Taylor) have already resulted in additional active project collaborators within the UK (Leeds and Newcastle Universities), Europe and the USA (Nevada University).

In a wider context, the discipline of Information Systems (IS) has focussed on the study of the application of information technology in organisations and society. Beynon-Davies and Blyth’s research covers the areas of strategic data planning, data management for healthcare, IS failure, the application of ethnography within IS development, IS security, responsibility modelling, and IS Evaluation.

In 1995 the ESRC awarded a grant (£62k: Beynon-Davies, Tudhope with the Open University) for an ethnographic study of prototyping practice in information systems development which has resulted in a significant number of publications for this RAE period. Blyth has been funded on a BT fellowship (£6k) and obtained £100k from DERA for four information security projects.

The Hypermedia group was awarded EPSRC funding (£121k in 2000: Tudhope and Cunliffe) to investigate the use of semantic structure and similarity measures for navigation and making queries in hypermedia systems. The project is in collaboration with the National Science Museum, the Museum Documentation Association (MDA), JP Getty Trust and the Canadian Heritage Information Network. This research has also contributed to the cultural heritage application domain through numerous publications including guidelines for MDA thesaurus construction projects. The group’s collaborative work with GIS inspired a workshop at the British Museum on GIS for museums, a session on geographic access to cultural heritage at ICHIM'97 and a research visit to FORTH in Heraklion. The unit has collaborated with related applied projects, such as the JISC DNER project on networked educational use of video (£328k for a consortium led by Glamorgan’s Library) which shares an emphasis on metadata for multimedia resource discovery and the EC funded Graduate Teleworking Initiative to enable multimedia graduates to set up their own businesses. Recent staff appointments have opened up other research areas, such as educational hypermedia authoring tools.

In 1997, the New Review of Hypermedia and Multimedia moved to Glamorgan (Tudhope editor and Cunliffe associate editor). Founded in 1989, its editorial board spans the leading international centres for hypermedia research. Glamorgan editorial strategy has implemented quality reviews of key research strands, including multimedia evaluation, adaptive hypermedia and open hypermedia systems.

2. Digital Imaging
Research in Digital Imaging has expanded since 1996 to include the analysis of medical infrared images (B.F.Jones and Plassmann) and the compression of both video (Jiang, Feng and Reddy) and terrain elevation data (Smith and Kidner).

Plassmann has developed a software package BTHERM which captures and analyses infrared images of the skin. B.F.Jones, Plassmann and Ring have presented a series of papers at the IEEE Engineering in Medicine and Biology Conferences. They are members of an international network of specialists in infrared imaging in medicine and collaborate with researchers in the USA (Falls Church, New York, Washington, DC), Poland (Lodz), Austria (Vienna) as well as the UK. The National Technology Transfer Center, Washington, DC, funded the production of an archive of the pioneering work in thermal imaging in medicine and the Glamorgan web site is the international resource for this information.

3. Applications of adaptive algorithms.
Research has thrived in applying Adaptive Algorithms (mainly genetic algorithms, simulated annealing and artificial neural networks) to an increasing range of domains.

Since 1996, Radio Frequency Assignment has been a major research area. It encompasses the development of both meta-heuristic algorithms for frequency assignment and techniques for evaluating the algorithms and the assignments obtained using them. The Universities of Glamorgan (Smith) and Cardiff (S. Hurley) collaborate in this work, with three externally funded research fellows based at Glamorgan and Cardiff. Two other research fellows have worked at Glamorgan between 1996 and 2000 and a research student has joined the group at Glamorgan.

As a result of this increased level of activity, the group has developed a reputation internationally and nationally as the leading group working in algorithms in this area. Of particular note is the recognition of the package FASoft of meta-heuristic algorithms (developed by Glamorgan and Cardiff) as the leading software package for frequency assignment. FASoft has been used by the group to solve the standard benchmark problems for mobile telephone networks, which had remained unsolved for nearly 25 years.

The group has received funding (with Cardiff) for four projects from the UK Radiocommunications Agency. As a result of this work Glamorgan was selected by BAE SYSTEMS and DERA Malvern to research frequency assignment algorithms suitable for a new communication system under development for the British Army. DERA at Defford have agreed to fund a research student to extend the work to satellite systems.

Additionally, Glamorgan was selected by ComOpt AB, a Swedish company supplying software to some 20 international mobile telephone companies, to research improved techniques for frequency assignment. The group also received research grant funding from EPSRC for a research fellow for two years. This joint project was administered by Glamorgan and provided funding for a research fellow for Glamorgan/ Cardiff and a research fellow for Royal Holloway, University of London. The final report on this project for the Glamorgan/Cardiff contribution was rated as alpha 4 and assessed as having made a "very significant contribution to the field", with management and use of resources classed as "excellent". An EPSRC ROPA project on frequency hopping has started recently.

Eyres and B.F.Jones have pioneered the use of meta-heuristic algorithms for the automation of software test data generation (evolutionary testing). Genetic algorithms have been used to derive tests automatically to cover the functionality and structure of software, to seek specific faults and to determine extreme execution times. The techniques for the last were developed through funding from the Correct Systems group of Daimler Chrysler who use these techniques routinely in their Berlin Laboratories to test real-time control systems. B.F.Jones is a member of the steering group of an EPSRC funded network (SEMINAL) of university and industrial research groups to develop and promote the use of meta-heuristic algorithms in software engineering.

Morris has applied neural networks to the identification and classification of the biological specimens. The biological domain poses particular problems for automated identification and classification in that in addition to the natural variation between samples, samples may also be damaged leading to missing or erroneous parameters. Radial Basis Function neural networks have been used to identify marine phytoplankton from flow cytometry data. Solutions have been developed for dealing with missing data, rejection of unknown species and estimation of populations from mixed samples. This work has been funded by the EU and NERC and has resulted in a system that is undergoing field trials. The work in this area has been supported by collaboration with University of Cardiff, Plymouth Marine Laboratories, University of Exeter and also European partners.

Wilcox has developed neural networks for use in instrumentation and control systems for wastewater treatment and combustion processes. Recently completed projects include one study funded by the European Union and one by a UK charity. One of these projects has resulted in the development of a control system for wastewater treatment using a sensor previously developed in the University. The research in this area has attracted international recognition. Other areas of applied research into neural networks include the reduction of gaseous pollution - work that has attracted considerable external funding from the European Union and British industries as well as the prediction of cutting tool wear in collaboration with Heriot-Watt University.

J.A.Ware has enhanced existing neural network techniques to problems in industry, the health sector, and commerce. Since 1997, he has collaborated with the University of Wales Hospital, Heraklion University, Crete, and researchers in Romania to enhance magnetic resonance imaging systems. The purpose of this research was to interpret medical images for earlier diagnosis and treatment. Another project involved the comparative study of residential valuation techniques and the development of a house price modelling system. The work was in collaboration with the Halifax Building Society and partially funded by an ESRC ROPA award. A third project was the optimisation of work roll profiles in hot strip steel mills. The results obtained from this work gave significant commercial benefits and consequently Metrology Systems Wales have agreed to fund a further PhD studentship. This new studentship will enable the prototype already developed to be progressed to the stage where it will be integrated into the actual environment of a hot roll mill.

4. Computer Modelling
There has been a substantial increase in our research into the use of numerical methods to model the performance of a variety of systems.

Ryley, Perkins and Smith analysed the susceptibility to error of magnetic and optical storage devices when operating in hostile environments. Data compression techniques that are robust in the presence of uncorrected errors have been developed and have generated international interest.

Rees and Evans have developed a GUI-based tool that allows system testing, analysis and modelling to be conducted within a single integrated environment and have evolved computer algorithms that enable the design of multisine test signals for testing both linear and Volterra non-linear systems. The group collaborates with Rolls Royce plc, the University of Sheffield and the University of Birmingham. Significant progress has been achieved in devising efficient methods for the estimation of parametric and non-parametric models, enabling accurate computer models to cover the turbine operating range. The conclusions from this joint programme recommended that the frequency-domain estimation techniques demonstrated by the University of Glamorgan should replace the existing ‘wobble test’ techniques used by Rolls Royce.

George and B.F.Jones have collaborated since 1996 on the computation of molecular structures that have helped in the interpretation of experimental infrared spectra. A successful application was made for EPSRC support via a consortium, including George, leading to an award of £563,165 from Nov 1996 to Nov 2002 to use High Performance Computing facilities at the Rutherford Appleton Laboratory for these computations. The Glamorgan contribution centred on "Ab Initio Studies of Hydrogen Bonding". The strategic importance of this work is the improvement in the analysis and control of many industrial and biological processes including those associated with genetics and reproduction when understood at the molecular level. A paper describing the work has been accepted and is scheduled for publication in the Philosophical Transactions of the Royal Society in December, 2001.

Staffing policy
Several new blood appointments have been made including three Professors of international standing. Jiang was appointed as Professor of Data Compression; he has published more than 70 refereed research papers since 1996 in international conferences and journals. The appointments of Higgs and Taylor to Chairs in GIS have broadened and strengthened the work in that area. Feng has joined Jiang’s group from Hong Kong Baptist University.

Knowledge representation and reasoning research develops models of physical [Ara3] and medical [Ara1] systems, and business environments [Com3]. Arana's knowledge analysis methodology concentrates on the capture and normalisation of re-design knowledge thus enabling the efficient re-use of past experience [Ara2]. Her reasoning system uses constraint satisfaction techniques in order to support the redesign of manufacturing articles [Ara3]. Compatangelo's work focuses on the conceptual design of computer-based systems, information systems and enterprise models. A description logics representation captures the conceptual schema, an associated methodology assists the building of a knowledge base, and a knowledge management tool realises the approach [Com1,Com2]. His approach will be further developed in a new EPSRC-funded project.

Craw and Boswell's knowledge refinement research applies machine learning in automated knowledge engineering tools that assist the development and maintenance of KBS. The approach of their EPSRC project is distinctive in providing a generic framework from which to assemble refinement tools for specific KBSs [Cra1,Cra2,Bos4]. In addition to the standard use of refinement tools for debugging, Craw and Boswell were first to recognise the importance of refinement for the task of KBS maintenance [Bos1], now recognised to be substantial. More recently, Craw's attention is turning to automated knowledge engineering for case-based reasoning (CBR) systems. This EPSRC project focuses on acquiring and refining the retrieval and adaptation knowledge used by CBR [Cra3], rather than simply relying on acquiring new case knowledge. Papers on adaptation are accepted for IJCAI 2001 and ICCBR 2001.

The KBS research is well-supported by EPSRC funding and links with industry. We seek further research funding to build novel tools that ease the development of complex knowledge-based software. Existing tools are ready to be deployed by knowledge engineers developing applications [Ara4], and software houses specialising in knowledge management [Bos2].

The Computational Intelligence subgroup tackles real-life complex optimisation problems not amenable to traditional analytical techniques.

McCall's Oncology Workbench (described later under Medical Informatics) optimises cancer chemotherapy treatments [McC2, McC3] where the Genetic Algorithm (GA) fitness comes from mathematical models of tumours developed by one of our mathematicians. The TAIGA project spans the divide between GA theory and applications, blending McCall's background in mathematics and experience of GA applications with Brown's expertise in formal methods and functional programming. It provides a generic library that is used for the rapid development of GAs, and as a tool to support a better understanding of GA theory. This library has been used to develop a GA for analysing well-log data [Bro2], and to gain a better understanding of GA implementations [Bro1]. Other GA projects include Elder's work on multi-objective land-use planning [Eld1].

Harper's emphasis is on IR systems that provide powerful and effective user interaction. Fireworks is an architecture for implementing extensible information-seeking environments [Har2], from which SketchTrieve, a highly innovative search environment for end-users, was developed [Har1]; SketchTrieve features as an exemplar in Hearst's chapter of a recent major IR textbook. The EPIC image retrieval system implements a novel spatial indexing and retrieval model [Har3].

The spiralling usage of the Web has focussed attention on personalised, intelligent, adaptive information retrieval systems. The large scale challenge of Web-based retrieval is tackled by Harper's new "mediated access" approach for structuring and searching the Web. This research was funded by Ubilab IT Research Laboratory, Union Bank of Switzerland (as was Fireworks), and the resulting WebCluster system has been integrated within Ubilab's Informia.

Goker's Context Learner for Okapi [Gok2] highlighted the need for user-adaptive IR systems, a popular topic of recent specialised workshops [Gok4]. Her newly started EPSRC project is analysing real-life Web user queries to detect relevant patterns for exploitation by incremental learning algorithms [Gok1]. Access to Reuters' intranet user data under a collaborative agreement enhances this research.

Teahan applies text compression in a novel form of text mining where compression rates inform the matching between text sources. His models achieve state-of-the-art performance in language and dialect identification [Tea3], Chinese word segmentation [Tea1], and produce an estimate of the entropy of English that is closest to Shannon's (1951) famous human-based estimate [Tea4]. Recent joint work with Harper applies text mining to choose the best compression model for a document, and has appeared in Proc. IEEE Data Compression 2001.

Richardson's research is concerned with the effective delivery of Web-based material and communications via digital networks. Novel algorithms have improved the quality of coded video under poor network transmission conditions [Ric1,Ric2]. Work on resource-efficient software video coding [Ric3] led to the development of a successful commercial CODEC and Richardson's position as director of a video communications software company.

The IR subgroup has been supported largely by industrial funding, and recently by EPSRC. We seek EPSRC and EU grants to extend our research in web-based searching using collaborative, intelligent agents, and to apply language modelling to various IR processes.

The Medical Informatics subgroup provides novel means of interaction with medical information.

Practising oncologists have found McCall's Oncology Workbench easy to use as a decision support system for designing, evaluating and optimising novel chemotherapeutic treatments [McC1]. The industrial relevance of the Oncology Workbench is demonstrated by funding from EPSRC JREI, SGI and the cancer charity Tenovus Scotland, and venture capital for commercial exploitation is now being sought. The role of the Oncology Workbench for computer assisted learning (CAL) is being exploited in a SHEFC funded project to develop a Web-based CAL Authoring Mini-Engine collaboratively with Glasgow College of Art and Aberdeen University's MediCAL. Richardson's work in optimising video compression has been applied to telemedicine and the delivery of CAL systems [Ric4]; this also led to SHEFC-funded work with Aberdeen University's MediCAL and CLUES units.

All research-active staff benefit from a research allowance that offers a partial buy-out from teaching and administration. The regular research allowance is 10%; an enhanced allowance of 20% is awarded to new staff and very active researchers. Activity is reviewed each year and the allowance adjusted. Additional allowances of 10% are given for PhD supervision and the management of projects. Annual staff appraisals explore the personal plans and aspirations of all staff, together with infrastructure needs and staff development requests.

We are particularly supportive of new staff. The enhanced research allowance is awarded without penalty for the first 2 years. Departmental pump-priming funding is earmarked for research projects for new staff; these are awarded on a competitive basis. Within the first 2 years of appointment we aim to give each new research-active staff member a PhD student or RA/RF. We provide appropriate assistance with supervision and all new staff are assigned a mentor.

We target university and departmental research funding at individuals. Our researchers were very successful in the last two competitive rounds for the University's Research Development Grant: pump-priming funding for 3 projects (£96K) and partial buyouts for 5 research-active staff (£42K). We devote approximately £60K p.a. of departmental RAE research funding as pump-priming for RA/RF projects with new staff, and to finance sabbaticals for research leaders. This is in addition to a quota of internally funded PhD studentships.

We value our contract researchers and research students, providing them with the same research environment and support as research-active staff. All conference costs are automatically covered when actively contributing to a conference. Offices are organised according to themes to provide a self-supporting environment and infrastructure for research staff and students. A weekly social event encourages informal discussions between research groups.

The University has encouraged the formation of research groups which has resulted in the researchers in UoA 25 forming one large unit: the Applied Computational Intelligence Research Unit. The work included under this heading covers intelligent and interactive systems, artificial neural networks, artificial life, evolutionary computation and complexity, and statistical signal processing. Current work corresponding to the two other topics from the 1996 submission (Organisational Information Systems, and Environments for Collaborative Work) is submitted in UoA 61. The UoA 25 section of the School includes 8 academic staff including two new staff.

The University’s Research Board organises seminars and training intended to help new researchers. New staff undertake an induction programme and are given a mentor and a reduced loading of non-research duties to encourage their research.

The Head of School coordinates research activity in the School, with the assistance of a research committee comprising all active researchers in the School. Matters such as the above policy and the prioritisation of bids for School and University funding are discussed and decided by this committee. The School encourages all staff to participate in research, and provides funding for attendance at conferences to present academic papers. For academic posts, it is regarded as essential to have research expertise, some University-level teaching experience, and a good fit with the School’s subject areas. All recent appointees have a significant record of accomplishment in research and thus contribute to the School’s current research foci. For internal promotion, the candidate’s research accomplishment represents one of the main criteria, and it is rare for promotions to take place without it. Studentships are funded at University and School level as an addition to the studentships supported by EPSRC and other external sources.

The School currently has 14 full-time research students in this UoA, including five self-funding international students attracted by the School’s research in this UoA. (A sixth such student has just completed.) It is noteworthy that 5 PhD awards were made in 2000.

Research seminars related to UoA 25 work have been held in semester time, on a fortnightly basis since 1996, weekly since 1999. In addition to encouraging participation in appropriate conferences, the School supports students’ attendance at summer schools. In 1998, 4 research students attended a summer school on Bayesian methods in Cambridge, and in 1999, 3 research students attended a summer school on an Introduction to Neural Methods at the Gatsby Institute, University of London.

The University and School actively encourage collaboration with other research institutions and participation in project consortia, through provision of travel expenses and relief from other duties. The School currently has two visiting professors (from Hong Kong University and from Université de Caen) each of whom have visited for several weeks to date to give seminars and meet individually with research staff and students. The School has a strategy in place for increasing the number of externally funded projects, by using applications for such funding as a criterion for University funding.

The School hosted an international conference in 2000: the Second International Computer Science Conventions Symposium on Engineering of Intelligent Systems (EIS2000), chaired by Fyfe. Paisley staff are often invited to join the programme and scientific committees of international conferences and journals (see RA6). Invitations were accepted to send visiting professors or researcher fellows to several national and international researcher centres including

Girolami completed his PhD in 2 years and 4 months, in 1997. In 1998 he published frequently cited papers that provided a generalisation of the ICA algorithm of A. J. Bell and T. Sejnowski (1995), and published further papers jointly with them and T.W. Lee in 1999 and 2000. These results have wide application but their first use was to remove interference from ocular and muscular signals in electroencephalographs so successfully that he became a visiting researcher at the Salk Institute, and he and Fyfe both became visiting researchers at the Riken Institute. Co-authors S. I. Amari and A. Cichocki are directors of research at Riken, and a student of Girolami (Rosipal) was one of only 2 UK PhD students selected in 2000 for Riken’s BSI summer intern programme to work in Amari’s laboratory. An extension of this work to nonlinear component analysis, by Rosipal and Girolami has now (2001) been published in Neural Computation (MIT Press).

A second modification to the PCA networks in Fyfe’s thesis is to apply a rectification to the weights in the ANN. Fyfe showed analytically that under certain assumptions about the source distributions, this led to extraction of independent sources. Charles (again supervised by Fyfe at the University of Paisley and funded by the University) developed this idea and linked the resulting networks to the statistical technique of Factor Analysis. Charles now supervises two research students, both funded by the University, who are again extending this work using wavelet bases on video data.

A new area of research was developed in Pei-Ling Lai’s PhD which investigated Canonical Correlation Neural Networks which extract the joint correlations (sometimes even mutual information) between pairs of data streams. Lai was a self-funded student supervised by Fyfe. Her PhD was completed in 2 years 8 months, and Zhenkun Gou, another self-funding student supervised by Fyfe, is currently extending the work.

Fyfe also developed research into modifying Hebbian learning itself by considering the noise distribution of the data set. MacDonald is currently completing the writing up of his PhD dissertation in which he has applied this concept to EPP networks. MacDonald has been much in demand at ANN conferences that have sessions on remote sensing and we anticipate that he will complete his PhD by the summer. It is worth noting that McGlinchey, McKay and MacDonald were all undergraduate students of Fyfe and all enjoyed final year Honours projects with him. McGlinchey’s PhD was funded by EPSRC, while the other two students had their PhD projects funded either by the University or the School.

A final area of research has been in the use of ANN’s for prediction: Shang-Jen Chuang, a self-funded student from Taiwan, is currently waiting to make his oral defence of his dissertation and Ying Han, a self-funded student from China, has begun to extend this work; she already has 4 papers published, one of which is taken directly from her Master’s dissertation at the University of Paisley.

Another area of research has been based on Evolutionary Computation: Livingstone is currently completing a PhD thesis on "The evolution of communication". His paper on modelling language was one of 20 selected from over 70 submitted for inclusion in the volume. Outputs 3 and 4 have led respectively to invitations to join the language evolution group at the University of Edinburgh, and an invited contribution to a book in press. Mr Wang, a self-funded student from Taiwan, is currently writing a PhD dissertation on "The evolution of cooperation“. Fyfe and collaborators with financial backgrounds have written several well-received papers on Genetic Programming for financial prediction.

The research direction that Girolami has been developing for the last 18 months is based on the theoretical foundation of probabilistic modelling and inference. This has grown from his PhD research where the blind separation of sources can be viewed as an inference problem in the case of missing data. This work, represented in Technical Reports 4 and 6 referred to above, has informed the submission of a joint EPSRC bid with F. Crestani (Strathclyde University) and opened a number of areas of new research investigation in the areas of Machine Learning and Information Retrieval. One software company is investing in the further development of various modeling approaches by Girolami for visualisation of dynamic data streams. Girolami has also been invited to contribute a chapter to book edited by Stephen Roberts (Oxford University) and Richard Everson (Exeter University), published by Cambridge University Press.

Campbell uses adaptive sub-band processing techniques to tackle the problems of noise reduction in speech enhancement schemes, which has benefited from substantive collaboration with the MRC Institutes of Hearing Research at the Royal Infirmary (Glasgow) and at Nottingham University. All four of his submitted papers arose from invitations to expand contributions to refereed conferences. Shields, co-author of one of them now works for Epson.

In the last 4 years Charles has produced 24 refereed publications and he completed his PhD at the University of Paisley in 2.5 years. Of these 4 papers have appeared in refereed international journals, 5 are book chapters, and 7 papers are in the top two European conferences (ICANN and ESANN). He has initiated and convenes the Vision Research Group and his major field is the application of Factor Analysis neural networks to this area.

Introduction

In 1996 Napier University undertook a major strategic investment in computing research, appointing three professors of international standing (Benyon, Fogarty, Kerridge). A strong research culture has been established throughout the School: research income has shown a steady growth and now averages some £600,000 p.a.; the research student population has been built up to 25.5 FTE; there are eight research assistants/fellows; there are four EU-funded and four research council funded projects; and five TCS programmes.

Institutional support for the School of Computing has been excellent. When Prof. Fogarty left early in 2000, we were able to replace him with Prof. Peter Ross from Edinburgh University. Also in 2000 the Information Management group (led by Prof. Davenport) joined the School of Computing from the Business School in order to build upon synergies in the areas of information communities and social informatics and Kennedy was promoted from Reader to Professor. With five professors the School is now well placed to maintain and develop the research culture and research outputs over the next four years.

The Work of the School

This submission concentrates on the activities of the three core ‘Computer Science’ research groups; Evolutionary Computation, Database and Object Systems and Human-Computer Interaction. Work in the areas of social informatics and information communities as well as the work of the International Teledemocracy Centre (a new interdisciplinary research centre based in the School) is returned under Unit of Assessment 61. Of course members of these two communities work closely with each other on areas such as ethnographic approaches to analysis and design (e.g. [AC4] — references in square brackets refer to publications listed in RA2). Several PhD students are supervised jointly and work on research contracts may cross the rather arbitrary boundary imposed by the RAE’s units of assessment. Such collaborations contribute significantly to the overall vitality of the research culture in the School as a whole. When appropriate, reference is made to individuals or projects in Unit of Assessment 61 as ‘(UoA61)’.

The Evolutionary Computation research group has established itself as a key European centre in the area, partly supported by key appointments such as Hart and Ross. The Database and Object Systems group continues to excel, particularly in transport informatics and in bioinformatics where the BBSRC/EPSRC joint panel is supporting Prof. Kennedy’s work for a second three-year period. The Human-Computer Interaction group contributes original work of impact to issues of HCI theory, design practice and assistive technologies.

Evolutionary Computation

The Evolutionary Computing group is very well known for its work on evolutionary timetabling and scheduling. Ross and Paechter were founders of the PATAT series of international conferences (Edinburgh, Toronto, Konstanz) on the theory and practice of timetabling, with proceedings all published by Springer-Verlag; Ross co-chaired the first of these. [BP2,BP3] describe a genetic algorithm that is used to timetable all of Napier University's classes, and which has led the way to the development of many related systems abroad. Ross has developed large-scale evolutionary exam timetabling systems [PR2], and one of the products of this has been the GATT system which has been widely used internationally by universities, notably by Harvard University for their MBA exams.

Work on evolutionary scheduling has produced a whole series of "current best" results on benchmark problems through a range of novel techniques, from operator targeting to the idea of using genetic algorithms to combine choices of the heuristics to use at different stages in constructing high-quality solutions. This latter idea, now termed `hyper-heuristics', has been used very successfully for a large real-world scheduling problem [EH2], for large exam timetabling [PR2] and dynamic scheduling problems [EH4] and has generated a great deal of interest. It is now being explored further in a major EPSRC grant (GR/N36660), together with colleagues at the University of Nottingham (GR/N36837).

However, the group's research ranges much more widely than timetabling and scheduling. It has, for example, explored and developed adaptive techniques in evolutionary computing such as self-adapting weights [BP4] and mutation strategies [PR1, BP3], and adaptive data selection ideas in genetic programming; discovered unusual phase-transition phenomena in families of graph-colouring problems, that apply to a much wider class of search methods than evolutionary ones; developed novel forms of artificial immune systems for fast scheduling [EH1,EH3]; developed novel ideas in the evolution of hardware configuration; and developed novel GA visualisation tools and techniques. Paechter leads the EC-funded DREAM project, involving seven European partners, that is developing systems to support highly-distributed and scaleable models of large-scale evolutionary computation. The group is a very active member of the EC-funded Metaheuristics project, also involving five other European partners, that is conducting a range of comparative studies of meta-heuristic techniques including genetic algorithms. The group has also been very successful in using classifer systems to model the trading behaviour of groups of stock market traders; as yet, this is still one of only very few practical applications of classifer systems.

The group is committed to working with others and to exploring evolutionary concepts. It co-ordinated the EC-funded Network of Excellence in Evolutionary Computing (EvoNet), it hosted a range of European workshops on evolutionary computing topics and it remains the administrative hub of EvoNet II. The immediate plans for the group are to build upon their current successes, exploring new forms of evolutionary algorithms and applying these to real-world problems. The group is also at the negotiating stage of a further EC research project that will use evolutionary techniques to explore some novel ideas in the `Neuroinformatics for Living Artefacts' FET area.

Database and Object Systems

The Database and Object Systems Group is involved in the development and application of novel database technology, object databases and modelling. Much of the research in this area is of a multi-disciplinary nature; particularly in transport informatics and bioinformatics. Napier, Glasgow and Manchester universities collaborated on an EPSRC funded project (GR/L02778) to investigate systematic generic support for user interfaces to databases. This work led Prof. Kennedy to a subsequent collaboration with taxonomists at the Royal Botanic Garden Edinburgh. This work has been addressing problems in botanical taxonomy, where multiple overlapping classification hierarchies for organisms create unique database problems [JBK4]. These problems occur at both the storage and at the user interface levels and are generalisable to any classification scheme that has to deal with multiple overlapping hierarchies. The work is having a major impact in database areas where issues such as ontologies and classification are critical. A relational structure cannot support the required performance, so a new, extended, object-oriented model is proposed. The ‘Prometheus’ model [JBK3], [JBK4] was developed through a BBSRC/EPSRC grant (1995-9 [95/BIF10516]). The novel database model and query language that have been built are illustrated in [JBK4]. The research continues to receive support from the BBSRC/EPSRC Bioinformatics initiative through a follow-on grant (2001-4 [00/BIF14353]) and has resulted in Prof. Kennedy being invited to the Media Lab Bioinformatics meeting in Heidelberg.

The taxonomic work has also resulted in highly original work on visualisations of multiple hierarchies. The example used in [JBK3] was so well received at AVI 2000 that the keynote speaker, George Robertson, asked to use the example. The work has thrown up some very interesting, previously ignored issues in visualisation concerning whether to base the representation on the underlying (graph-based) data model or on the (set-based) user’s model of the data. Working with Prof. Benyon in the HCI group, this work has been generalised to a novel methodology described in [JBK2] and has been further supported with a studentship from the bioinformatics panel.

The research degrees programme has benefited greatly from the collaborative nature of the EU funded research projects. The School has had visiting students from the Swedish Institute of Computer Science, the University of Aarhus and Bang & Olufsen and Napier students have been able to undertake reciprocal visits for periods up to three months. Such exchanges contribute significantly to the experiences of research students.

The School has in place an effective and transparent method of research resource allocation. The staffing resource model is very clear about the allocations for research degree supervision, work on externally funded projects and other scholarly activities. A ‘contract’ for individuals to pursue research is reviewed annually as part of the staff development process. Individuals are classified as one of (a) those undertaking active research and mentoring of more junior researchers, (b) research active staff who are still developing a track record and (c) researchers embarking on a research career. An appropriate resource allowance is allocated based on this classification and an agreement based on agreed outputs is established in line with the overall research policy. All new staff are expected to be research active and staff are encouraged to obtain a PhD if they do not have one. A mentoring scheme is in place to support new staff and those at the early stages of their research career; a scheme which has already resulted in one ‘fast track’ EPSRC grant.

Research in the School contributes significantly to Government foresight priorities (in such areas as e-commerce, ageing population and information and communication media) and to European priorities for improving the quality of life. The mixture of research council and EU funding for research balances the need for pure and applied research. The School demonstrates its committment to effective dissemination and transfer of the research into the economy through TCS and LINK programmes, and to the development of understanding through the research degrees programme.

The Future

The School of Computing has made significant progress over the assessment period. The promised investment in PhD bursaries took place and has been maintained and plans to attract research income and research degree students that were set in 1996 have been exceeded. Members of the School regularly publish in international journals and conferences and each of the research groups can demonstrate significant impact on the international scene through conference organisation, participation and other measures of external recognition (see RA6). The School is now well established in its chosen key areas of computing and has clear plans for future development. A vigorous and vital research culture has been established which is feeding the other activities of academics such as teaching and technology transfer. Fourteen members of the School have been submitted to the RAE through Unit of Assessment 25 or 61.

Whilst planning is vital to success, so is the willingness to re-align when necessary. Prof. Beddie took up a position with the Scottish parliament in 1998 and Prof. Kerridge took over as Head of School. Prof. Kennedy’s work has focused more keenly on the specifics of database models structures and interfaces to support her bioinformatics work where it is having a major impact on the discipline. The research in general database and object systems envisaged in 1996 has taken place and the key member of staff involved has, within the last six months, moved to apply this research in an industrial context. With Prof. Benyon’s arrival there was a shift in emphasis towards a contextual approach to usability, and this rendered the usability laboratory unnecessary and Prof. Kerridge’s focus on modelling for transport has superceded his research on parallel and distributed systems.

The main growth area in research has been more on the requirements and design side of computing, social informatics and information communities that has led to the submission of six people to UoA61. Although some of this was due to the interests of new appointments, to a large extent this was due to Prof. Benyon’s and Prof. Davenport’s (UoA61) international collaborations with partners across Europe through the ‘connected communities’ theme of the EU’s 4^th Framework Long Term Research programme.

Our aim for 2001 – 2005 is to build on the well established groups that have developed since the last assessment. In particular, an active research degrees programme will continue to be supported, financed from recovered overheads, TCS money and a certain amount of the RAE income. The activity of a healthy research degrees programme has succeeded in spreading the research culture widely through the School and it has been excellent at encouraging interdisciplinary research and nascent research areas. In addition to the research degrees programme, a key strategic aim is to invest in more staff time for research and more administrative and technical infrastructure. This will be achieved by continuing to attract external funding. The School is poised to move to new office and laboratory accommodation, refurbished at a cost of £5.3 million, with some £750,000 specifically earmarked for research staff and research students.

In terms of impact on the discipline, and of research within the School, the expectation is that both the engineering and design sides of computing will develop. On the engineering side, developments in wireless technologies and the increasingly embedded nature of computing will lead to the ‘disappearing internet’. One approach to dealing with the issues that arise from this is to develop mobile agents that can be sent out to undertake specific tasks. The agent-based approach promises to have a resonance elsewhere where Prof. Benyon has long been interested in interface agents (and, indeed, was chair of the ACM’s conference on Intelligent User Interfaces, in 2000). Prof. Kerridge has been applying the approach to pedestrian modelling (and has recently been appointed to the US Transport Research Board’s Artificial Intelligence Committee). Prof. Kennedy will continue her bioinformatics work which in turn will encourage further developments in visualisation and in object databases. On the requirements and design side we expect to see development in social informatics and information communities. A new degree in Information Systems is planned which will enable and encourage growth in the Social Informatics group. The existence of the International Teledemocracy Centre (ITC) in the School is expected to provide many benefits. The ITC provides an excellent focus for much of the School’s research work; people interacting with technologies, issues of enfranchisement and the social impact of technologies, database, knowledge management and data mining issues.

The overall strategy for the School of Computing is to grow steadily from the position of strength that it has established during the assessment period. Specific targets and performance indicators have been set that include: measured growth in external research funding to an average of £1,000,000 p.a.; a research student population of some thirty FTE with ten completions per year; six TCS or LINK programmes active at any one time and 50% of staff active in research at a national or international level.

The University has a research policy that encourages research in all areas and excellence in some. Its investment in five professors in the School of Computing, and in new estate, demonstrates its commitment in this area. The published outputs described in RA2 include considerable material of international standing. The research income, research degrees activity and overall research culture in the School demonstrate real vitality. RA6 provides significant evidence of international esteem. The School can demonstrate a significant impact on the discipline in areas such as evolutionary algorithms and their application to scheduling, novel database structures, visualisations and human-computer interaction. Our intention is to continue this quality of research, spreading it wider throughout the School and discipline.

The School’s strategy is to conduct research which stays focused on important, long-term, fundamental challenges of CS and its applications. The (M), (P) and (D) groupings are geared towards provision of principled, sound and exact accounts of computation, languages and systems and the clean design of languages and systems. The (A) grouping works on some of the fundamental problems which need to be overcome to make AI usable in realistic contexts, not just in idealised environments. Novel computing methodologies developed in (E) avoid human preconceptions about problem solving and system design. Grouping (I) works at the interface between Computing and the Sciences, effecting cross-fertilisation of ideas and realisation of methodologies.

In the sequel, Part 1 details key research achievements and future plans of the groupings. General research culture, management and strategy are discussed in Part 2. Citations to RA2 papers are shown thus: [Jung 2] or Jung [2], for paper 2 of Jung. Other papers are also alluded to, by conference or journal name and year. RF/RA/RS stand for research fellow/associate/student (in RAE terminology RA = Research Assitant without PhD, RF = Postdoctoral Research Assistant).

RA5a Part 1: Research Achievements of Groupings during Assessment Period
(M) Mathematical Foundations of Computer Science
There is strong collaboration with groupings (P) and (D), as well as other national and international centres of excellence in this area, with support from UK and EU grants.

Domain Theory. A denotational semantics maps programming constructs into a mathematical universe of semantic spaces. Members of the group have contributed substantially to the understanding and the structural analysis of such universes: Jung, Kegelmann (RS) and Moshier (USA) have developed a sequent calculus which provides a purely logical analysis (via cut-elimination) of domain-theoretic constructions [Jung 3]. This, and Escardo’s localic investigations, have led to the affirmation of stably compact spaces and closed relations as central to denotational models. Huth (was RF), Jung and Keimel (Darmstadt) have exhibited a natural instance of the linear type discipline in Domain Theory which does not refer to the lift-monad [Jung 2]. Jung and Tix (Darmstadt) have written a comprehensive account of the order-theoretic properties of the probabilistic powerdomain [Jung 1]. Schalk’s work with Hyland (Cambridge) has led to a more structural understanding of game models [Schalk 1]. Future work will exploit the novel relational universe to address issues in denotational semantics, especially of exact numerical computation.

Exact numerical computation. This research is based on a rigorous mathematical model of the real numbers which avoids the round-off errors inherent in the traditional floating-point representation. Escardo [1,2] extended PCF with real numbers. The work has laid foundations for further work in many places (Imperial, St Andrews, Paris). Escardo [1] established the fundamental properties of adequacy and universality for higher-order exact real number computation. Integration, as an important example of a higher-order operation is studied in [Escardo 2]. With Hofmann (Edinburgh) and Streicher (Darmstadt) he discovered the inherent parallelism of basic functions in this approach. Konecny (RS) with Jung characterised precisely those real-valued functions which are computable by a resource restricted device. Future work will concentrate on the impact of representation on the efficiency of real-number algorithms. The collaboration with St Andrews on the integration of exact numerical computation into computer algebra systems will continue.

Computational Logic. Apart from domain logics mentioned above, the emphasis has been on linear logic and linear lambda calculi. De Paiva, Ritter and Ghani (RF) designed the first explicit substitution calculus for linear logic and proved important meta-theoretic properties [Ritter 1], using categorical semantics to clarify subtle interactions between explicit substitutions and linearity. De Paiva, Ritter, Maietti (RF) and Maneggia (RS) gave a systematic account of the relationships between various linear lambda-calculi and their models. De Paiva, Ritter and Ghani applied techniques from linear logic to modal logic and obtained a novel characterisation of computation in stages (ICALP’98). Ritter solved the long-standing termination problem for calculi with explicit substitution [Ritter 3]. Ritter and Pym (Queen Mary) showed how intuitionistic proof search can be seen as a special case of their counterparts in classical logic [Ritter 2, 4]. Future work will concentrate on the semantic characterisation of proof search, automatic program optimisation of staged computation, and modal logic for knowledge representation. A new collaboration with Bono (Turin) will study languages combining functional and object-oriented features.

(P) Programming Languages
This work grew out of the recent appointment of Reddy, Thielecke and Fuhrmann (RF). Its focus is on the semantics and formal methods for state-manipulation, dynamic data structures, memory usage in implementations, control operations and other computational effects found in programming languages. Reddy produced a novel semantic model for Algol-like Languages [Reddy 1], solving the long-standing problem of modelling locality of local variable declarations and providing the first known successful modelling of irreversibility of state change posed by Strachey in 1973. His model for an interference-controlled fragment of Algol (SCI) and for full Idealized Algol [Reddy 2], was proved fully abstract up to second order and led to further development of the game semantics of Abramsky and McCusker. The model for SCI in [Reddy 1] inspired O'Hearn et al. (QMW) to revisit an earlier model which was discovered to be doubly closed [MFPS 95] leading to further development of the Logic of Bunched Implications. Reddy also applied his theory to the semantics and formal methods for object-oriented programming [Reddy 4], and is establishing relationships with techniques of program refinement [FOSSACS 00].

Thielecke analysed control operations, i.e. first-class continuations, from an abstract, categorical perspective on their essential structure [MFPS 97]. Much of this structure was generalized to call-by-value languages with effects (such as Standard ML) [TACS 97; Thielecke 4], and studied in depth by Fuhrmann (RF) [MFPS 99]. The categorical structure thus unearthed was applied to the study of expressiveness of control operations [HOSC 98; Thielecke 1,2,3], showing that exceptions and the call-with-current-continuation operation are of incomparable expressive power, a surprising fact refuting several informal claims made in the previous literature.

Within the EPSRC-project XSLAM, Ritter applied the calculus of linear explicit substitutions [Ritter 2, see also (M) above] to the implementation of functional languages. He developed a calculus which models memory usage for functional languages incorporating all higher-order functions.

Probabilistic model checking. This aims to provide theoretical foundations, algorithms and software tools for automatic verification of probabilistic systems. Such tools can enhance the design process through early error detection, prediction of failure and performance, and provision of diagnostic information. Jointly with Ryan, RFs (Norman and Huth, now at KSU), RSs (Norman, Parker), an EPSRC Visiting Fellow (Segala from Bologna) and collaborators (some in Bonn, CMU, UC Berkeley), Kwiatkowska has contributed to all areas of the field (EPSRC grant GR/M04617 and British Council/DAAD grant). Definitive compositional metric-space and domain-theoretic semantic models for probabilistic process algebra CCS [Kwiatkowska 3] and CSP were formulated. Probabilistic logics were developed alongside algorithms for automatic verification of probabilistic systems against specifications expressed in such logics [LICS'97], including a symbolic model checking algorithm [Ryan 4] and another under the assumption of fairness [Kwiatkowska 1]. PRISM (www.cs.bham.ac.uk/~dxp/prism/), the first fully-fledged probabilistic symbolic model checking tool implementing these algorithms, is nearing release [TACAS’00, CAV’01]. It can efficiently build and analyse three types of probabilistic models (DTMCs, CTMCs and MDPs) of substantial size against specifications such as "the chance of X occurring is at least 98%“ or "the chance of Y occurring is at most 1%“. Future work includes optimisation e.g. using parallelisation (building on Theodoropoulos' work), using data abstraction for very large or infinite state systems, and deployment in industry.

Verification of Quality of Service. This pioneering work, begun in 1999, is concerned with algorithms and tools for automated verification of dependability and quality of service properties of distributed systems, for example, soft deadlines ("the chance of a packet being delivered within 15ms is at least 82%“). With support from EPSRC (GR/N22960), Kwiatkowska with Norman (RF), Sproston (RS/RF) and Segala (Visiting Fellow) proposed the modelling formalism of probabilistic timed automata, and the first region-based and symbolic algorithms for their automatic verification [Theor.Comp.Sci, in press]. They then solved an open problem by formulating a method for automatic verification of continuous probabilistic timed automata [Kwiatkowska 4]. Future work will improve the efficiency of the methods, integrate them with verification tools, and develop case studies.

Distributed simulation: Simulation is an alternative to exhaustive analysis, and enables partial analysis of systems for which model checking is impractical. Theodoropoulos with Logan (now in Nottingham) developed a novel generic distributed simulation framework which enables the efficient dynamic partition of system state and dynamic load balancing [Theorodopoulos 4; Proc. IEEE, to appear]. In collaboration with colleagues from Manchester he advanced the field of modelling and distributed discrete-event simulation of asynchronous hardware [Theorodopoulos 3, J. Parall. & Distr. Comp. and Concurr.-Practice& Experience, to appear], overcoming problems with using relatively abstract tools such as Occam and CSP, developing novel synchronisation protocols and proposing a generic modelling and simulation framework. His work on the instruction and trace-driven simulation of large MIMD machines and multithreaded microprocessors led to the development of novel simulation techniques and synchronisation protocols [Theodoropoulos 1,2]. Future work will concentrate on further development of the proposed simulation frameworks addressing challenging optimisation, causality, and load management problems.

(A) Artificial Intelligence and Cognitive Science
Proof planning. This is a technique for guiding the search for proofs in automated reasoning, and for explaining their structure. It emulates human reasoning by first outlining an abstract plan. Kerber with Jamnik & Benzmuller (RFs) have extended proof planning systems to include practical, automated learning of new proof methods (re-usable strategies) from a few examples [Kerber 3,4]. They also approach concurrent and distributed agent-based proof search in a novel way, employing cooperating heterogeneous reasoners. Jamnik and Kerber have mechanized informal human mathematical reasoning, making major advances in the automation of the use of diagrams [J.Logic,Language&Infor, '99; book in press, CSLI Press Stanford]. Future work topics include: the relationship between analogy and the formation of new methods; learning of the primitive vocabulary for the formation of complex methods (open problem); and application of the techniques in an educational environment.

Logic and reasoning. The thrust here is to provide correct and efficient logical accounts of various aspects of human reasoning. Counterfactual reasoning and the logic of belief update were considered to be only informally connected. Ryan & Schobbens (Namur) showed a precise relationship between these topics [Ryan 1], leading to an automatic cross-migration of results. Ryan, Andreka (Budapest) & Schobbens also definitively answered the question of how logic formulae expressing default information can be combined with and without priorities, and provided a thorough exploration of the properties of the combination [Ryan in J. Logic & Computation, in press]. Through applying the ideas of model checking to reasoning about knowledge in multi-agent systems, Ryan & Lomuscio (RS) showed how informational interactions among the agents can be captured as computations involving finite automata [Ryan 2,3]. Current work develops the idea that role-fulfilment in agent systems can be formalised using abstraction. Future work will use this idea to make model checking multi-agent systems more efficient.

Reasoning about beliefs and mental states. Reasoning about people’s mental states is crucial for the long-term applicability of AI, e.g. in natural language processing and legal reasoning, but the field has made little headway with handling various sub-problems, notably the role of uncertainty. Barnden implemented ATT-Meta, a system that reasons about other agents’ beliefs and, uniquely, handles (qualitative) uncertainty and resolution of reasoning conflicts within and across all levels of belief nesting (Barnden [1,3] and in AI & Law, in press; www.cs.bham.ac.uk/~jab/ATT-Meta). The work addresses various neglected but important issues such as a potential combinatorial explosion of reasoning goals. Peterson [2,3] established by theory and psychological experiment a link between counterfactual reasoning and simulative reasoning about beliefs, and related experiments [Peterson 4] threw light on the nature of autism. Future work will include further refinement of ATT-Meta’s conflict-resolution techniques; heuristic streamlining of its handling of nesting; extension to non-belief mental states; and application studies.

Computational linguistics / natural language understanding. Handling figurative language effectively and flexibly is important for the long-term future of automated natural-language processing. ATT-Meta (above) performs reasoning needed in metaphor understanding (Barnden [1-3]; EPSRC: GR/M64208). Key achievements include: understanding rich, creative extensions of familiar metaphorical modes of expression (this fills a major gap in the field); casting metaphorical reasoning as a type of simulative belief reasoning; greatly transcending reasoning limitations of other computational approaches to metaphor; embedding metaphor understanding in a general, implemented uncertain-reasoning framework; and handling metaphorical language about mental states, almost entirely ignored in other AI work on mental states. This research stresses discourse coherence as a guide to understanding. Smith & Hancox [Hancox 2; and in AI Review, in press] showed in computational detail how coherence considerations can influence understanding. This and other language-pragmatics research [Lee 1-3] has been complemented by work on syntax, speech, and gesture (Hancox [3,4], Edmondson [2,3], [Edmondson ICSLP'96 Workshop on Integration of Gesture in Language & Speech; Gestures: Meaning & Use'00]). Bullinaria [1] achieved new successes in accurate connectionist modelling of human reading, spelling and past-tense acquisition. Future research will include: setting ATT-Meta’s metaphor approach in a broader pragmatic-processing framework; expanding the handling of time and causation (central to much metaphor); and continued research on handling metaphor combinations [Lee & Barnden in Metaphor and Symbol’01).

(E) Evolutionary Computation
The School has one of the strongest groupings of permanent staff focused on this area in the world.

Evolutionary Artificial Neural Networks. (This is also an aspect of (A).) Yao developed EPNet, a system for evolving compact generalising neural networks, using novel mutation operators and behavioural evolution [Yao 2]. An ensemble approach to evolving NNs has been proposed [Yao 1]. Poli introduced an efficient dual representation for evolving NNs [Poli 2] and discovered novel NN learning rules using Genetic Programming (GP). Bullinaria identified mechanisms by which evolution shapes neural structures in the brain [Neural Network World’00] and clarified what is required of a NN model to be biologically plausible [Bullinaria 2]. Rowe produced a novel method for evolving recurrent NNs [Artificial Life’96]. Future work includes further development of efficient techniques for NN training and NN-ensemble evolution.

Theory of Evolutionary Computation. Rowe (with Vose, Colorado) helped develop the stochastic dynamical systems theory of evolutionary algorithms (EAs) [Rowe 1]. He generalised this work to arbitrary search spaces, relating the action of genetic operators to the search space structure. This work accounted for finite population effects that are often counter-intuitive [Rowe 2]. Yao with He (RF) proved for the first time conditions under which an EA does or does not take at least exponential time to reach a global optimum. Poli gave GP a sound theoretical basis (see below). Future work includes analysis of average time complexity of EAs on various problems, generalised schema theorems and dynamical system models for finite populations.

Co-evolution. Sloman [4] presented a new way of looking at interacting trajectories of different co-evolving entities in design space and niche space, in the evolution of human-like architectures. Yao and Darwen (Australia) produced a novel approach to automatic modularisation of a learning system through co-evolution [IEEE Trans EC, ‘97; ‘00]. Future work includes development of new distance metrics for co-evolutionary systems and automatic design of modular systems.

Evolvable Hardware (EHW). EAs can serve as knowledge discovery engines. Miller demonstrated a saving of up to 23% on the number of gates in common circuits such as digital multipliers, and showed how new design principles could be extracted [Miller 1,2]. He also identified key features of EHW fitness landscapes [Miller 3] and produced novel ideas in logic synthesis [Miller 4]. Yao & Schnier (RF) developed new EAs for discovery of novel designs, leading to a patent application with Marconi. Future work includes co-evolving designs and specifications, and evolution of fault-tolerant systems.

Genetic Programming (GP). GP is for evolving tree-like structures such as computer programs. Poli provided solid theoretical foundations for GP, including several new exact schema theorems [Poli 1-4]. These results generalise and refine existing GA theory and explain the mechanics of evolution acting on variable size and shape structures. Poli also made technological advances such as sub-machine-code GP, parallel distributed GP, and sub-symbolic representations for GP. Miller developed a new form of GP, Cartesian GP, that has representational redundancy and neutrality which is important for evolving efficient designs.

Other Evolutionary Computation Techniques. (See also (I).) Yao with students invented a Cauchy mutation operator which outperforms existing mutations on many problems [Yao 4]. They also invented the stochastic ranking method for effectively handling constraints [IEEE Trans EC’00]. Rowe constructed prognostic models for cancer patients using EAs, improving on doctors' current best practice [AI in Medicine’98]. Miller effectively minimised Reed-Muller canonical expansions using EAs [Int. J. Electronics'96].

In its future work in general, the (E) grouping will continue to study fundamental theory while maintaining relevance to real-world applications.

(I) Image Understanding and Computer Vision
Image interpretation based on the physics of image formation. Going beyond traditional interpretation techniques that analyse the image itself, Claridge and Cotton (RS) developed a new, generic, approach, which draws on fundamental understanding of image formation, and successfully applied it to the analysis of skin lesions. Theoretical papers [Claridge 2,4] received prizes. Impressive clinical results in melanoma diagnosis (EPSRC GR/M53035) brought invitations to collaborate from leading dermatologists in Europe and Australia. A commercial clinical device based on this work (www.SIAscope.com) is rapidly being taken up in Europe and beyond. Claridge and Preece (RF) have recently shown that the method can be extended to other tissues and begun work with ophthalmoscopic images. An exciting prospect for future work is to deduce, in real time, the structure of certain materials and tissues from their images. A recently awarded Leverhulme grant (F/00094/M) will support cross-disciplinary theoretical work and development of practical methodologies, including evolutionary methods. Commercial exploitation will be sought.

Vision modelling. Drawing on psychophysical models of visual perception, Claridge developed a family of new image analysis algorithms yielding results consistent with perception. An algorithm based on the "irradiance effect“ predicts well the perceived edge location in translucent objects (e.g. lesions in x-ray images), where derivative-based methods fail [Claridge 3]. Studies of the neuropsychological basis of closure, a perceptual phenomenon associated with surface emergence, led to a novel method for segmentation of poorly defined cellular structures in biological and industrial images [Inf Sci’00]. Claridge’s and Billups’ (RS) principled solution to an often neglected problem of parametrisation of computational models of vision [Claridge 1] contributed to an international interdisciplinary study with Humphreys (Birmingham), Stiehl (Hamburg), Mingolla (Boston) & Peterhans (Zurich) [Image & Vision Computing’96]. Future work will continue to study and exploit perceptual models in a similar way, in collaboration with colleagues in Psychology and Medicine and drawing on evolutionary techniques.

Architectural requirements for visual systems. Sloman has been exploring requirements for a variety of aspects of human and animal vision within the CogAff architecture framework (see also A). His theory depicts a visual system as three architectural layers which evolved at different times and perform different sorts of tasks with different perceptual requirements. By viewing the components of the visual system and the components of the central layers as a sort of "ecosystem“ in which the parts co-evolved he has obtained new insights, including generalising Gibson’s notion of "affordance“ and also explaining and generalising ideas in neuropsychology on alternative visual pathways [Sloman 3]. Architectural requirements for visual systems will continue to be developed and implemented.

Evolutionary Image and Signal Processing. Poli has been exploring alternative ways of designing image and signal analysis algorithms through the use of evolutionary techniques. He became one of the first researchers ever to successfully evolve image analysis algorithms using genetic programming (GP) [Image & Vision Computing’99]. The strength of GP techniques will be exploited to evolve new image analysis operators and their sequences; to evolve image-exploring feature-seeking agents; and to develop new classes of image filters whose design is not constrained by tradition and preconceptions. Access to the new technology, as an everyday software tool for image analysis system designers, will be ensured by making it efficient and reliable.

RA5a Part 2: Growth, Staffing Policy, Research Culture and Research Strategy
In 1996-2000 the School earned 10 major EPSRC research grants (including a £100K JREI grant with Biosciences and Medicine) and one ESRC grant jointly with Psychology, totalling £1.37M, and another 16 major research grants from other agencies, totalling £1.55M. This more than trebled the level of funding during the previous RAE period (£909K). The School has joint projects with BT, Marconi, Rover, Sharp and Sony etc., and has effected technology transfer notably in skin imaging. Among the major awards is a £601K EU ERDF grant for a Centre in Advanced Telematics to support technology transfer to regional SMEs (1999). In 2001 the School won a related HEFCE grant for a 3-year HEROBaC fellow. Since 1996, 20 RFs and 14 RAs have worked in the School, and there are 3 RF vacancies.

The School is active in research interchange, internally, nationally and internationally. The weekly Departmental Seminar covers all parts of CS and neighbouring disciplines, and regularly attracts audiences from across the campus. The School also currently runs two focused, weekly research seminars: in Theory, and in Evolutionary Computation and Neural Networks. These and other, more informal, seminars bring in School members outside their own specialised remits. The School has attracted distinguished speakers (many from abroad) (see RA6 for some) through these mechanisms, together with the Guest scheme (below) and funding-council visitor schemes. School members have organized major conferences etc. in Birmingham (AISB’00, ESSLLI’00, APPSEM’96, PSSL’98, MathFIT’97) and elsewhere (see RA6). RAs, RFs and RSs are fully involved in such activities.

RSs report every 6-months to their thesis groups (3+ staff each, from different areas), which are fora for intensive research discussions, and their progress is reviewed by the Research Standards Monitoring Group (chair: Hancox). This has led to a steady improvement in completion rates: 91% over the last 4 years. Theory students benefit from a 3-term training by the Midlands Graduate School in the Foundations of CS (founder: Jung with Nottingham and Leicester). RSs are funded to present their work at conferences. The School awards 6+ new research studentships per year, to the most promising applicants, irrespective of area or supervisor. The School was accepting 7/year around 1996 and has more recently been accepting 15/year; 36 were awarded PhDs in 1996-2000.

Research support in the School is organized by a central committee (chair: Claridge) that includes RS and RF representation. On the basis of individual merit and independently of applicant status or rank, it supports research travel, pump-priming of research (which helped create laboratories for Robotics and Medical Image Analysis), up to six Guest Fellowships or Professorships per year, and School-organized workshops and conferences.

The School’s research culture and themes are eminently well-suited to interdisciplinarity, as is evident above, especially in the case of groupings (A), (E) and (I). Specific interdisciplinary collaborations have included: Barnden under ESRC grant with E. Robinson (Psychology, Birmingham), on mental-state reasoning; Claridge variously, as noted under (I) above and in RA6; Peterson with D.Bowler (Psychology, City U.) on autism, and with Education (Birmingham) under funding by the Shirley Foundation; Edmondson with M. Tatham (Essex) on syllable phonetics; Poli with T. Bao (Biosciences, Alberta) & J. Nelson (Biology, Duke U.) on modularity within the genome; Poli with K. Harris & R. Royston (Chemistry, Birmingham) on determination of crystal structure. However, much of the School’s other research is intrinsically interdisciplinary in scope as well.

Performance Modelling and Engineering Group (PME) [leader: Prof. D.D. Kouvatsos, with Prof. Woodward, Prof. Graves-Morris, Drs Al-Begain, Awan, Csenki + Rodriguez, Sheriff, Shepherd]
This group has continued research towards the creation of novel analytical, numerical and simulation techniques and related algorithms for the modelling and performance/reliability evaluation and prediction of computer systems and high-speed telecommunication networks. It has pioneered cost-effective methodologies for the exact and approximate analysis of general Queueing Network Models (QNMs), based on the information theoretic principles of maximum entropy and minimum relative entropy, queueing theoretic concepts, Markov and semi-Markov processes, advanced numerical methods and batch-renewal traffic processes. New and more powerful exact and approximate quantitative results have been derived for various types of arbitrary QNMs with finite capacity and, thus, blocking schemes, general service times, multiple job classes and mixed (priority/non-priority) scheduling disciplines. These solutions have been implemented via station-by-station system decomposition and multilevel hierarchical aggregation algorithms which employ closed-form probability distributions for the queue length and response time for single or multiple queueing stations within tandem, split and merged configurations. Batch renewal processes were used for the modelling, characterisation, call admission control and management of traffic at the edges and the interior of the network. Extensions have also been made to analyse QNMs under various buffer management schemes leading to new congestion control mechanisms with space priorities. The new methodologies offer simple and practical means for performance evaluation and prediction of computer communication systems including multiservice integrated terrestrial and mobile networks based on Internet Protocols (IP) and Asynchronous Transfer Mode (ATM) networks. The group is an internationally recognised research centre of systems performance modelling and evaluation, hosting the largest IFIP working conferences in the world on ATM & IP Networks (1996-1998, 2000), attracting in total over 500 international experts from industry and academia as well as research students worldwide (organised by the group and chaired by Prof. Kouvatsos).
The work of the group (1996-99) on the Performance Modelling and Evaluation of Broadband Integrated Services Digital Networks (B-ISDNs) attracted - jointly with Imperial College - substantial EPSRC funding (£284K) with Prof. Kouvatsos as principal investigator. The final report was graded Alpha 4 (May 2000) - very significant contribution to the field. Earlier EPSRC funded work of the group on ATM Networks Performance was awarded Alpha 5 (Jan 1996). Another EPSRC funded project (£140K) on the performance evaluation of mobile video systems is currently ongoing (1998-2001) with Prof. Woodward the principal investigator. Current work of the group focuses on fundamental research into Internet traffic characterisation, call admission control and performance modelling and prediction. The work includes an investigation into the analysis of complex continuous and discrete time QNMs (Prof. Kouvatsos, Prof. Woodward, Dr. Awan) and its innovative applications into traffic control and its effects on the Quality-of-Service (QoS) as well as call admission control, handover and capacity management of second and third generation mobile systems and wireless ATM networks (Dr Al-Begain).
Two other members of the group (Prof. P. Graves-Morris and Dr. A. Csenki) are mathematics specialists, carrying, out research into high speed computation and probabilistic modelling and giving support to the many numerical and stochastic aspects of work in the systems performance/reliability analysis field. Strategic appointments associated with the group have recently included two professors (one pending), one senior lecturer and a first-appointment lecturer (Dr Awan).

Distributed Virtual Environments Group (DVE) [leader: Prof. R.A. Earnshaw, with Drs Palmer, Wan, Zharkova + Prof. Excell]
This group has grown out of the Imaging group submitted to UoA 29 at RAE 96, also subsuming the RAE96 UoA 25 groups in graphics, image processing, and music technology.
At the last RAE there were three sub-groups: i). visualisation and 3D imaging over ATM networks; ii). multimedia assets in industrial design; iii). photonics and image processing. The first two aspects have been continued and combined into one area of distributed virtual environments and computer graphics, and this has been expanded to include computer animation and modelling. This has enabled us to attract substantial funding from HEFCE/JREI, EPSRC, EC, industry, and the DTI.
Prof. Earnshaw leads the sub-groups on distributed virtual environments and computer graphics, and computer animation and modelling. These include research in visualisation, virtual studios, multimedia, and distributed virtual environments. Prof. Cavazza was, and Drs Palmer and Wan are, the most active co-workers. Prof. Green led the sub-group on photonics and image processing, the photonics work being considered part of the TS research group: Prof. Excell has taken over the telecommunications aspects, but his work in bioelectromagnetics also involves 3D imaging and graphics.
The research in digital media and content generation is underpinned by the close working relationship with the National Museum of Photography, Film and Television (a division of the National Science Museum), located close to the campus. This relationship operates through the Electronic Imaging & Media Communications Department, an innovation unique to Bradford, which works to bridge the ‘two cultures’ between digital technology and artistic aspects of content. This department has strong computer-science leadership in Prof. Earnshaw (also Dean of the School of Informatics). Staff in the Museum collaborate with the DVE Group in European research projects. The work of the DVE Group with national and international collaborators is combined under the heading of the ‘Institute for Digital Media’.
The group received acknowledgement of its expertise by its inclusion in the Virtual Centre of Excellence (VCE) in Digital Broadcasting and Multimedia Technology, with the Universities of Bristol, Cambridge, Essex, Surrey, Imperial College, and University College London. The group was successful in its JREI bid for £350K for a Silicon Graphics Onyx supercomputer in 1996 for research in computer animation. This provided international-class power for compute-intensive tasks underpinning several large projects.
The group was successful in the following bids: i). Digital VCE for a joint research project with UCL on Virtual Theatre Rehearsal (£440K); ii). EU for collaborative project VPARK - Virtual Entertainment Park (994KEuro: 25% to Bradford; other partners: Swiss Federal Institute of Technology; University of Geneva; Integrated Information Systems; UK National Museum of Photography, Film & Television); iii). DTI/EPSRC LINK Broadcast Technology initiative for project VIP - Virtual Interactive Presenter (£752K total - £539K to Univ. and local SME partner).
The image processing specialists have been investigating compression of multiple image data sets, particularly related to the areas of multimedia, network communications and the Internet. An astronomical imaging thread exists within this group and the key member is Dr Zharkova, who has a major international reputation in solar image processing.

Intelligent Information Systems Group (IIS) [leader: Prof. I.S. Torsun (deceased 11/00); acting leader: Dr D. Rigas, with Drs Muyeba, Ridley, Wang + Shepherd]
This group is concerned with executional models for intelligent systems, including computational models and algorithms. The scope includes: deductive databases, modal and temporal logic, neural networks, non-monotonic reasoning, and reasoning with uncertainty. The term ‘Intelligent Information Systems’ has been adopted in its wider sense because it incorporates Information Sciences with Artificial Intelligence (Dr Wang), User Interfaces and Multi-Modal communication (Dr Rigas), Formal Methods, Databases and Data mining (Dr Ridley). For instance, some of the group’s detailed objectives include investigation of Artificial Intelligence techniques and paradigms, multimedia information processing for information systems, data mining techniques to support data repository needs of information systems, investigation of the effective use of formal methods and techniques in the design of information systems. Until his recent death, the leader was Professor I.S. Torsun, whose sub-group’s recent research has been in neural networks, for the development of a spatial-temporal network which can dynamically analyse data patterns using time series. Recruitment of a new leader at professorial level is in progress; in the interregnum, a new Senior Lecturer, Dr. D. Rigas, has been appointed to be the acting leader.
There are plans to build upon the existing research by applying intelligent control systems and multimedia interfaces to solve industrial problems. The areas cover scheduling, planning, simulation, and control of production systems, intelligent control systems, discrete event systems, neural networks and fuzzy logic. It is also planned to build upon the multimedia and interfaces expertise for the support and operation of these systems. Current work involves stochastic process algebra to analyse functional and performance characteristics. The integration of object-oriented methods and standards with formal notations is also being investigated, and a framework for the analysis of OOP languages has been developed (Dr Muyeba). Research has also been undertaken in software development of general user interfaces, auditory interfaces and multimedia systems. Audio-visual communication metaphors have been employed to assist in the development of software for visually impaired users: this is also of benefit to industrial software developers and designers (Dr Rigas).

Environment. The Laboratory is currently sited centrally, in increasingly over-crowded accommodation spread over three adjacent buildings. Technical and administrative support is supplied by 7 computer officers, 1 technician, and 7 assistant staff. During the last couple of years lack of space for new research staff has made it difficult to fully realize the potential for expansion of research activity that undoubtedly exists within the Laboratory. However, in the Autumn of 2001 the Laboratory will move into purpose-built accommodation of 10,000sqm gross on the west side of the city. The new building is funded by a donation from the Bill and Melinda Gates Foundation (£12.9M), by HEFCE Project Capital Allocation (£4.5M) and the University (£3M). This will allow expansion of staff numbers by some 60% over the next 10 to 15 years. Our strategy for the next five years is as follows.

Research Strategy. The Computer Laboratory aims to carry out world-class research across a broad spectrum of computer science. Although the subject is rapidly evolving, a number of core themes recur: systems, communications and security engineering; mathematical foundations; and the interplay between humans and computers. We will strive to preserve a mix of these themes in our research activities. We believe it is very important to do so, to ensure that the themes are not divorced and condemned to lead separate, incomplete lives. For example, there is continual evidence that the most relevant mathematical theories of computation arise in response to engineering experiment.
Systems, communications and security engineering. The advent of global computing and the junction between computing and communication presents many opportunities that we plan to exploit during the next five years. The existing strengths of the Systems Research Group in this area will be augmented during 2001 by the appointment of a Marconi Professor of Communications Systems. This Chair is funded from a £28M donation by Marconi to Cambridge University that will also provide significant research income for the Computer Laboratory over the next six years. Marconi have also set up a research laboratory in Cambridge, whose first director, McAuley, has close ties with the Computer Laboratory, having been a Lecturer here in the 90s. This will eventually move to a new building next to the new Computer Laboratory building. It is likely that some space in both new buildings will be occupied by researchers from the Department of Engineering's Division of Information Engineering, enhancing and extending existing research collaborations with our Systems and our Natural Language research groups and with CCSR. Our research groups also plan to make use of the forthcoming Cambridge Open Mobile System, a pair of test networks for research into next-generation mobile services being provided by Vodafone and covering the city of Cambridge. Our RAE’96 plans to expand research on Security were hampered by the departure of Needham to become the first Managing Director of Microsoft's Cambridge Research Laboratory (whose new building is also sited next to the Computer Laboratory’s new building). We have just appointed a new Lecturer (Kuhn) in security and will seek to strengthen the Security Research Group during the coming phase of expansion. (Needham's departure also had a positive aspect for us: Security is one of several areas where we are building strong research collaborations with the Microsoft Research Laboratory.)
Mathematical foundations. The Theory, Semantics and Programming Group has grown during the last six years to become the second largest in the Laboratory after Systems. The recent appointment of Winskel to a Chair makes it well placed to contribute to theoretical aspects of global computing, mobility and security. We also plan to exploit Winskel's connections to build up a collaboration with the Basic Research in Computer Science (BRICS) Institute in Aarhus (Winskel was its first Director), based around the exchange of graduate students.
Human-Computer Interplay. New developments in computing and communications present both new ways of engaging with technology and new social phenomena mediated by technology. There is a strategic role for humanities, arts and social science perspectives within technology research. Crucible is a nascent research institute within the University of Cambridge whose purpose is to encourage such interdisciplinary research. It is co-directed by Blackwell (who was appointed to a Lectureship in the Computer Laboratory in October 2000) and Good in the Faculty of Social and Political Sciences; Good is also a director of the newly formed Cambridge-MIT Institute (CMI). The Laboratory's Graphics and Human/Computer Interaction Group will expoit the opportunities provided by CMI and by Crucible to expand its activites in interdisciplinary research into human-computer interaction.

Research groups. For each of our research groups, we describe research-related achievements during the assessment period, current activities and future plans. Much of the work reflects EPSRC priorities (which also take into account Foresight recommendations) for IT and Computer Science. Thus "novel technologies and new ideas" occur throughout; there is a "holistic approach to architectures of large scale systems" in much of the work of the Systems Research Group; and "computing-communications convergence" is particularly evident in that group's work and in the work of the Theory, Semantics and Programming Group towards formal models. (In what follows, a reference like [Anon-n] refers to Anon's nth publication listed in RA2.)

A. Automated Reasoning Group. (Gordon, Paulson, Norrish, Slind, 5 research assistants, 5 research students.) This group pioneered the application of Higher Order Logic (HOL) to the verification of computer hardware; as a result, Higher Order Logic is now a standard formalism for verifying digital designs. The group has traditionally built its own tools: Gordon's HOL System is primarily used for hardware verification, while Paulson's generic Isabelle System supports a variety of logics. These proof assistants are two of the most used worldwide. Major releases of these tools (Hol98 and Isabelle99) were produced during the assessment period. Work with the HOL tool has concentrated on linking the theorem prover to other design tools, including industrial CAD and CASE tools. This has included work combining theorem proving and proof planning [Gordon-2, Slind-2], and contributions to the core proof engine of the toolkit produced by the Prosper ESPRIT project [Gordon-3, Gordon-4]. Other notable achievements are a mechanised semantics of the C language [Norrish-1], the exploration of functional programming in a theorem prover [Slind-1, Slind-3, Slind-4] and the work by Gordon's PhD student John Harrison on floating point verification, for which he won a BCS Distinguished Dissertation prize. Paulson's Isabelle System has been used for both theoretical and practical investigations. Theoretical work includes mechanising parts of set theory [Paulson-1], abstract algebra [Paulson-2], and the use by Paulson's PhD student Jacques Fleuriot of non-standard analysis for mechanising analysis, for which he too won a BCS Distinguished Dissertation prize. Practical work with Isabelle has concentrated on the verification of cryptographic protocols: several industrial-grade protocols, including Kerberos, have been analysed to a level of detail unmatched by other methods, often uncovering design defects [Paulson-3]. Isabelle has also been used to develop a verification environment for concurrent programs, using the UNITY calculus [Paulson-4].
Current projects include work on the theory and implementation of a platform for combining deductive theorem proving and model checking; and on automating compositional proofs about parallel programs. The group is investigating automatic creation of multiple views of logic specifications for execution, interactive deduction, and automatic formal verification. It also plans to study mechanically verifying real world e-commerce cryptographic protocols in collaboration with the Security Group. A long-term aim is to provide a flexible core proof engine that can be embedded in other CAD/CASE systems to provide a programmable platform for formal verification.

Computer architectures. Work on this topic is carried out in collaboration with the Graphics and Human/Computer Interaction Group. Moore and Robinson have investigated self-timed circuit design. They produced the design of a new architecture based on rotary pipelines for super-scalar processors that lends itself to asynchronous implementation [Moore-2], a new storage element (the reset-enable-data or RED flip-flop) to improve data path performance in asynchronous circuits, a design methodology for the control circuits in an asynchronous system and an approach to rapid prototyping of self-timed circuits [Moore-3]. The group continues to investigate self-timed microcontrollers as a vehicle for improving and benchmarking self-timed design techniques, sponsored by EPSRC, Cambridge Consultants Ltd and AT&T Laboratories. These microcontrollers will have data-driven power consumption and will consequently be particularly efficient at low duty cycles [Moore-4]. Using their foundation in self-timed processor design, the group will explore other low-power computer design issues. Other current projects are: FPGA design (Altera), third generation smartcards (EU), and multi-threaded processors (EPSRC) [Moore-1]. Future plans include work on globally asynchronous, locally synchronous system design.
Operating systems. Work on the Nemesis operating system [Leslie-1, Hand-1], a vertically structured operating system designed to support predictable and configurable quality of service for applications, has continued through a large ESPRIT LTR project. This has led to a publicly available distribution of the operating system [Hand-2]. Many of the Nemesis ideas are being carried forward in other projects. We are investigating server-less storage systems in which clients have direct access to a shared pool of network-attached disks. A key tenet of this work is that clients receive predictable application performance through provision of quality of service guarantees. Ideas from Nemesis are also being exploited in the XenoServer project [Pratt-1] which aims to build a viable platform to support public-access wide-area computing by enabling applications to execute components closer to the data and services with which they need to interact, avoiding long interaction latencies, bandwidth bottlenecks or high network link charges. XenoServers may be deployed at strategic network locations in order to host untrusted application code, in return for the application's "sponsor“ paying for all resources used or reserved [Pratt-3]. Such a system would enable network users such as content providers to distribute components of their applications in a manner that is both efficient and economical. A further development from this work has been the design and implementation of an extensible virtual machine supporting application-specific control of the programming language's runtime environment [Harris-3].
Networking technologies. Source modelling is now of limited value with the rapid turnover and evolution of new network applications; by the time one has developed a model of an application, the application has changed. Leslie and Crosby investigated techniques based on on-line traffic measurement. These take results from large deviation theory, but rather than extracting a large deviation bound from a model, they extract it directly from measurement. Work on resource management in networks is now focussed on automated dynamic negotiation and pricing of service level agreements between carriers. We believe this could result in more efficient use of existing bandwidth, and enable ISPs to make quality of service versus price tradeoffs as to how traffic is routed to and from them. Gibbens, in joint work with Kelly in the Statistical Laboratory, has shown how mathematical and economic approaches to congestion control can be applied to existing and proposed developments in packet networks such as IP networks [Gibbens-2]. He has also helped to produced a teletraffic analysis of the consequences of the IETF DiffServ proposals [Gibbens-3] that forms the basis for further work in the areas of resource pricing for distributed control in packet networks and for the teletraffic analysis of enterprise IP networks. Leslie leads a team investigating network programmability, specifically looking at the provision of dynamic virtual networks that have dedicated resource assigned to them and that can have different network control systems, despite running on the same physical network [Leslie-2]. By allowing differentiated control on a single infrastructure, one encourages innovation in network control systems and services [Pratt-4]. This work has led to patent applications and is being pursued by a start-up company. Work on Internet topics includes semantic analysis of network traffic in which non-intrusive monitors perform application-level analysis of network traffic in real time in order to gain detailed high level information without vast storage requirements. This will provide an accurate understanding of an application's behaviour and performance. Other work includes the investigation of carrying IP over a global circuit switched core based on DWDM. The circuit switched core is to be reconfigured dynamically according to network traffic patterns, with the aim of approaching the bandwidth efficiency and user-convenience of datagram networks, while avoiding the need for packet switching in the network core. In the area of home networking, the Warren project [Greaves-2], explored the use of low cost ATM hardware for domestic networks. Work in this area has continued with the development of the "HAN“ local area network. This a system that aims to achieve high bandwidths over existing phone line wiring using a novel technique whereby network nodes dynamically reconfigure their receivers depending on with which other nodes they are communicating. Another extension of this work, Auto HAN, is examining higher-level issues such as application organisation and security, and is investigating ease of "programmability of the home“ through the use of intuitive Lego™ style tangible interfaces.
Middleware and multimedia support. Large scale distributed applications must be built above middleware platforms that support heterogeneous hardware and software environments, with the possibility of mobile, wireless applications and disconnected working. Their ubiquitous nature makes new demands on privacy and security, since one application may span many administrative domains which wish to restrict mutual trust, such as in a nationwide electronic health record service. Bacon and Moody pioneered event-driven middleware through the Cambridge Event Architecture (CEA). Their "publish, register, notify“ event paradigm employs source-side (scalable) filtering of parametrised events and includes event mediators and composite event detection servers [Bacon-2,3, Moody-4]. Events are a means by which disparate components may be composed to form new systems; a component may offer to carry out an action if another component supplies a trigger. An aspiration is to achieve "global computing“ by federating event systems, requiring that the event services span administrative domains. Closely integrated with CEA is Oasis, an open architecture for secure, interworking services. Oasis implements role-based access control as encryption-protected certificates [Bacon-1,3,4, Moody-1,4]. It uses event channels to span services which have issued role membership certificates and this spanning structure functions as a dynamic proof tree that the certificates remain valid. Violation of role entry conditions are signalled as events which leads to selective and immediate revocation of certificates. Current work is on engineering large-scale systems [Bacon 4].
The group is currently beginning to explore how to automate the process from policy expression (law) via mathematical logic to implementation (in large scale distributed systems) with initial reference to access control policy. This will involve collaboration with the Natural Language Group in order to capture access control logic from policy expressed in pseudo-natural language. Another current interest is information retrieval systems; after over thirty years of research into such systems, recently techniques have been developed to allow access to multimedia documents, including text, graphics, audio and video. However, many of the systems which handle media other than text are bespoke designs. Research led by Bacon and Moody is investigating methods of constructing information retrieval (IR) applications which can exploit multimedia data in a uniform manner; just as databases are implemented within a DBMS, so it is hoped that IR applications may be designed under Cobra [Moody-2,3], which extends the ODMG Object Model to support generalised keywords.

H. Centre for Communications Systems Research (CCSR). (Lee, 2 research assistants.) After a two-year start-up period, our RAE’96 plans for a multidisciplinary centre for communications systems research were realised in June 1997, under the Direction of Stewart Lee, a University Research Professor, formerly a Professor at the University of Toronto. The founding departments all have active research interests in communications systems; they are the Department of Applied Economics, the Computer Laboratory, the Department of Engineering and the Statistical Laboratory. The Centre is supported entirely by industry; its current industrial sponsors are Alcatel Bell, the BBC, Bristol-Myers Squibb, HP, Hitachi, ITT, Marconi, Micromuse, Microsoft, Nortel, and Sun. Almost all of these support co-operative research programs, and the others supply equipment or philanthropy. The total support arranged to date is over £1.75M and at present some nine postdoctoral researchers are sponsored, including two in the Computer Laboratory. The current research programs are as follows: Business Model of Internet Services (Alcatel Bell); Network Security (Hitachi); Diverse Services Universal Networks (Hitachi); Network Management Architectures (Micromuse); Interactive Participatory Media (Microsoft); Bioinformatics and Genomics (Bristol-Myers Squibb). Being a non-profit research institute supported entirely by industry, CCSR fosters strong links between academic research and industrial take-up. In choosing timely research topics, it has the same opportunist strategy as the Computer Laboratory and will evolve in cooperation with it.

Recruitment Policy: The Department has undertaken substantial recruitment of academic staff over the past four years taking great care to maintain the standards of excellence. There are only three members of staff over 50, with no retirements scheduled during the next five years. We have chosen to recruit promising researchers at the lecturer level, and this has been very successful. During the past five years, five academic staff members have been appointed through internal promotion, and we have an unusually youthful age distribution; we also have one of the highest female:male academic staff ratios in the UK (6F:10M). Prof. Luo was promoted to lead the new Computer Aided Reasoning Group, joined by Dr Callaghan in 1999 and Dr McKinna (see section 6c). Prof. Munro continues to lead the Reverse Engineering and Software Visualisation Group, also including Dr Robson, and joined by Dr Burd in 1999. A major development has been the establishment of the Distributed Systems Engineering Group, led by Dr Boldyreff (Reader) and Dr Xu (who joined in 1998), supported by Dr Thomas (1998) and Dr Bradley (1997). Our AI group has changed direction since 1996; the previous strength was in Natural Language Engineering, and this group (of 4 academic staff) left to set up a very successful local spin-off company (3F Ltd.). Dr Fox has been appointed Reader to lead the Planning group, supported by Dr Long. New recruits in Planning include Dr Porteous (joined 1999) and Dr Coddington (2000). Prof. Bennett continues to lead the Transformation and Evolution Group, which forms part of the inter-university Pennine Group (see below).

The School’s success in research parallels that of the whole University, which has won seven JIF grants (one involving our own School). This success, together with anticipation of early retirements and application of rigorous research management policies, has enabled us to make a number of strong appointments. Finlayson, Hordley and Zwiggelaar (Sept. 2001) join the Computer Vision group to work on Computational Colour and Medical Imaging; Breen, Milner (both ex BT) and Mandic (ex Imperial College) strengthen the Signal Processing group. Hayward (returned under UOA14), a joint appointment with the Schools of Biological and Chemical Sciences, supports the new Bioinformatics laboratory. Janacek and Bagnall, a joint appointment with the School of Mathematics, support the statistical foundations of Data Mining. Kruse supports compression and MPEG aspects of applied multimedia.

Pattern Analysis and Neural Networks
The PANN group has a total of five academics, one visiting Professor, one research fellow, one research assistant and twelve PhD students. Over the assessment period, members of the group have published 120 refereed papers (47 in journals) and attracted more than £800K in grants, with 46 papers (21 in journals) and more than £500K grant income since 1999 --- virtually all from EPSRC research grant awards.

The application of neural network technology to pattern analysis is the core shared interest of the group. The patterns may be derived from images (medical images, scene analysis, OCR), from time series data (EEG, financial stocks), from sensors (ultrasound, radar, audio, visual, infrared), and from text (documents). Prof. Partridge, Dr Singh, Dr Everson, Dr Henderson and Dr Zhang share an interest in applying well-established inductive technologies to the analysis of patterns using probabilistic and multiple-classifier approaches. Traditional pattern analysis research on feature extraction and selection is also characteristic of the group’s research.

4.2. Parallel computing. Dr Juhász is working in parallel image processing (see RA2 Juhász:2), parallel discrete-event simulation, and parallel performance prediction (see RA2 Juhász:1). He has industrial collaboration with Continental Teves Gmbh, Germany, and external consultancies with Outsource Laboratories Inc. (USA) and Obvis Ltd (UK). He has academic collaborations with the University of Genoa (Italy), Nanyang Technological University (Singapore), the University of Cardiff, and other departments within his home university of Vezprem (Hungary). Dr Juhász continues productive collaboration on performance-prediction techniques for parallel simulation with Prof Stephen Turner (formerly senior lecturer) who left the department in June 2000 to take up a chair at Nanyang Technological University in Singapore. Dr Juhász is a regular visitor to the Department and his contract will be renewed in future years.

Research structure and environment

The aim of the Computing Laboratory is to undertake research and teaching of the highest international standards in Computer Science. We believe this is best done through a relatively small number of strong research groups, each with a distinct identity, which encourage collaborations between groups within, and external to, the Laboratory. Every member of staff belongs to at least one research group which organises its own series of seminars, and promotes intra-group and inter-group interactions, including joint research projects and publications.

A Research Executive (comprising the Director, Deputy Director, Head of Research and Heads of Research Groups) is responsible for overall strategic research planning, including providing support for young researchers, and promoting strategic collaborations outside the Laboratory. Heads of Research Groups give advice within their own groups, e.g. on research grant applications. Each member of academic staff receives an annual individual budget to support their activities – for example, to support conference attendance. In addition, the Research Executive (through the Head of Research) allocates additional funds to supplement the individual allocations (often in support of newer members of staff) and to support research students. The total amount of resource (excl. staff) allocated in this way in the current year is approx. £44k. The Laboratory provides the traditional “well-found laboratory” in the form of technical support (6 FTE staff support research full-time, including a full-time Research Support Administrator), dedicated computing equipment for each member of staff, and dedicated laboratories for research groups that need them (e.g. for the Networks and Distributed Systems Group). It also provides specialist equipment (e.g. within the Multimedia Laboratory supporting Roberts’ work in visualization).

The Laboratory has strong industrial collaborations, which have led, in 1998, to the Laboratory being designated a Sun Microsystems Authorised Academic Java Campus (the first in Europe) and, in 2000, becoming a Sun Target University (the first outside the USA). These collaborations cover the complete range of Laboratory activities, including research projects. We also have research collaborations with BT, Hewlett-Packard, IBM, Nortel Networks, Philips Research Laboratories, Rational and Trireme International.

Staffing policy

The Laboratory operates a policy of appointing only staff who can contribute to its aim of undertaking research of the highest international standards. Staff new to the academic role are required to attend the University’s Postgraduate Certificate in Higher Education (accredited by SEDA/ILT), which includes elements of research training; all such staff are required to have a mentor (who provides research support). Newly appointed members of staff either have EPSRC-supported research students under the CASE for New Academics (CNA) Scheme (Timmis) or have obtained industrial sponsors to allow this to happen (Johnson, de Lemos, Roberts). Staff are engaged in an annual appraisal process, which may result in staff development in research topics, and are encouraged to take periodic research leave: within the RAE period, 14 members of staff have done so.

General developments since 1996

The 1999/2000 academic year saw the retirement of several senior staff, many of whom have given outstanding service to the Laboratory. These include Professors H Brown, PJ Brown, Slater and Turner; Professor L Johnson has also left to take an appointment elsewhere. Several new staff have recently been appointed to take their places (de Lemos, Hatton, C G Johnson, Kent, Mander, Roberts, Timmis), and others (Bowman, Derrick, King, Thompson, Utting) promoted to senior positions. These changes have allowed the Laboratory to focus its research into six main areas – Theoretical Computer Science (TCS) and Networks & Distributed Systems (NDS); two areas that have been developed since 1996 – Systems & Software Engineering (SSE), and Applied & Interdisciplinary Informatics (AII); and two smaller, more focused areas – Concurrency (CC) and Computer Science Education (CSE). The Laboratory’s work in Software Tools & Electronic Publishing is now largely concluded, though some recent achievements are reported under the Applied & Interdisciplinary Informatics Research Group.

Research achievements since 1996

Systems and Software Engineering (SSE)
Researchers: Barnes, de Lemos#, Hatton#, Hopkins, Kent#, Mander#. Category B: Brown (P). # = new since 1996.
Background/current activities: This group was formed in 1999 around the interests of members of staff new to Kent in that year; two other staff with related interests also joined the group. The overall research goal of the group is to improve the quality of systems and software. Three main strands run through this work: model-driven development, metrication and testing, and work on dependable systems.
Achievements since 1996:
Model-driven development: Work in this area has focused on the development of new visual modelling notations, rearchitecting the definition of UML and the application of modelling techniques to industrial problems. We have developed a visual notation for expressing constraints, adapting mathematical notation for general users [Kent 1,3] and have applied this to object-oriented modelling [Kent 3,4]. For modelling dynamic behaviour, a 3D notation that combines multiple views has also been developed [Kent 2]. We have been actively engaged in the precise definition and rearchitecting of UML. With Evans (York) and Clark (King’s, London), and with industrial support, have been invited to join the consortium framing the main response to the request for proposals for the revision of UML to version 2.0. We have developed a precise subset of UML for modelling service level agreements and their mappings to underlying network structures. These models have been taken up by Nortel Networks allowing them to develop network configuration and monitoring tools [Kent, work under a non-disclosure agreement].
Metrication and testing: We have developed a framework for analysing project lifecycles in concurrent engineering environments, which allows easier identification of process variations, and facilitates the identification and evaluation of process improvements; we have applied this in Rolls Royce [Mander 2]. We have developed methods for the effective and efficient automated generation of test-data using optimisation techniques; the effort required to find such test data is significantly lower than that required by manual techniques or tool-supported proof attempts [Mander 3]. We conducted an early study of a large volume of data originating from the HENSA Unix Web proxy cache [Barnes 4], identifying pertinent factors in usage and growth of the Web likely to have a high impact on the configuration requirements and effectiveness of using a proxy Web cache to address problems of limited available network bandwidth. We have studied the quality of numerical software and the adequacy of its associated testing process [Barnes 1, Hopkins], showing that certain software metrics (particularly knot and path counts) are good indicators of the presence of defects in numerical software [Hopkins 3].
Dependable systems: We have shown that repetitive failure modes are dominant causes of systems failure [Hatton 2] and have explained the unusually high vulnerability of small components to defect [Hatton 1]. We have demonstrated the importance of diagnosis in the improvement of software-based systems [Hatton 4]. Hatton has developed fundamental principles constraining the use of intrinsically unsafe but widely-used programming languages such as C in high-integrity systems, laying the foundation for standards such as MISRA, the international standard which has been taken up by the car industry. We have developed a method based on diverse sources of qualitative evidence that combines model checking with deductive and inductive techniques, and increases confidence in the outcome of safety analysis [de Lemos 2]. We have defined a method and notations for incorporating exception handling within the software lifecycle [de Lemos 3]. We have defined architectural notations for dependable systems that are sufficiently flexible for supporting both run-time [de Lemos 1] and design-time evolution [de Lemos 4].

Concurrency (CC)
Researchers: Welch, Wood.
Background/current activities: This group focuses on concurrency as a core enabling technology for future computing, unifying the design of hardware and software systems both for general purpose and specialist application. A key research goal is to construct a secure model of components from the idea of communicating processes and to use that to achieve scalability in computer systems– where scaling means the ability to ramp up functionality (i.e. to stay in control as complexity increases) as well as physical metrics (e.g. performance). The research is particularly applicable to low-power, fast, small-footprint computing technology such as internet routers and smart-cards.
Achievements since 1996: We have developed a CSP model of the monitor primitives of Java, giving formal semantics (for the first time) for Java multithreading [Welch 1]. In collaboration with Jeremy Martin (Oxford), we have used this model to construct a formal proof of correctness of the channel classes provided by Welch's CSP library for Java (JCSP) [Welch 2,3], which has also been developed in this period. New secure synchronisation primitives that enable greater concurrency have been introduced, formally defined and implemented with ultra-low overheads [Welch, Wood 2]. Occam has also been made considerably more flexible, enabling it to be used way beyond its original target application area (embedded systems). Extensions include user-defined operators, native thread support, dynamic process loading, persistence and mobile processes - a key research issue being to achieve all this without compromising parallel security or efficiency [Wood 3]. A full open-source (Linux) occam system, supporting libraries and run-time kernel has been developed and released [Wood 1,2,4].

Computer Science Education (CSE)
Researchers: (main interest) Fincher#; (secondary interest) Barnes (SSE group), Cooley (AII group), Utting (NDS group). Category B: Slater. # = new since 1996.
Background/current activities: Since 1994 the Laboratory has led a number of major nationally-funded projects in the area of teaching and learning (Computer Science Discipline Network – CSDN, Effective Project work in COmputer Science – EPCOS) which gave the Laboratory a national profile in Computer Science Education. In 1997, we established the Computer Science Education Research Group through a maturing of these activities into a research area, in which the group now has an international profile. The group’s research strategy is to focus on the theoretical aspects of computing-specific education research and on well-founded empirical studies, often in collaboration with colleagues at other universities, e.g. Leeds, Open and Uppsala.
Achievements since 1996: In the theoretical area we have undertaken survey and synthesis studies in areas general to the nature of the discipline. We have applied the techniques of patterns and pattern languages (more commonly used in software engineering) to pedagogy, and shown their particular fitness for Computer Science [Fincher 1]. We have also compared pedagogic approaches in Computer Science with other disciplines [Fincher 4]. We have shown how practice in Computer Science project work can be enhanced by the application of Bruner and Wenger’s constructivist approaches in student-led learning [Fincher 3, Utting 1].
Empirical studies include a comparative analysis of technical questions asked by students in two public forums – an anonymous course web page, and a non-anonymous bulletin board – which provided strong evidence that the anonymous course web page was a more effective means of both addressing student queries and reducing the support load on teaching staff [Barnes 2]. [Barnes 3] introduces an anonymous question-asking forum that demonstrates that the application of key software-engineering skills, such as analysis and refinement, can thereby be encouraged and enhanced by facilitating a critical approach to assessment. We have developed computer-supported knowledge elicitation techniques to facilitate the construction of adaptive tests (i.e. tests of competence that adapt during delivery to students responses) [Cooley 3].

The following activities are noteworthy indicators of this progress:
TCS The path coupling technique of Bubley and Dyer is now a standard tool for research into Markov chain algorithms. This is illustrated by the Machtey Award at the 1999 IEEE Symp. on Foundations of Computer Science presented to Vigoda (Berkeley) for his paper on an application of this method.
KRR Work in Qualitative Spatial Reasoning (QSR) in developing the oft-cited Region Connection Calculus (RCC) and new QSR algebras for vagueness, orientation and location is at the forefront of international activity (e.g. researchers at Amsterdam, Freiburg, Newcastle (Australia), Ulster, Linkoping have all built on RCC, and SRI (Palo Alto) plans to use RCC in DARPA-funded work).
CVL The group has pioneered the novel use of stochastic process models for representing behaviour (e.g. the first use of variable-length Markov models in computer vision) and has developed new kinds of applications such as its widely-reported work on novelty detection for surveillance and monitoring.
SCV Berzins, Brodlie and Jimack’s work on unstructured mesh algorithms and visualization has led to the founding of the CPDE Unit and the Iris Explorer Centre of Excellence which have attracted industrial funding of £0.5M and collaborations with leading US groups in this area at Caltech (Poole), the University of Utah (Johnson) and the University of California at San Diego (Bank).
Inf Dew’s work on virtual environments (best paper prize, ASME 2000 IDETC-CIE) is one example of the work underpinning a major multidisciplinary informatics initiative which has been launched funded by £1.3M JREI and HEFCE capital bid grants, building on Dew’s grants of £1.2M since RAE96.

RA5.1 Research Structure and Environment
RA5.1.1 Research Management Since RAE96 the School’s Research Committee, led by its Directors, first Cohn and now Berzins, has invested £600K to ensure the continuing excellence of the research groups. £430K of this has ensured that staff have enhanced their research through international sabbaticals (10% of staff per year) at institutions such as MIT and Microsoft (Seattle). The investment of £112K on strategic staff pump-priming activities has further expanded research. The groups are led by Professors Dyer, Cohn, Hogg, Berzins and Dew, each of whom has an established reputation for research leadership and individual excellence. Their roles are to guide the growth of the research groups and to ensure the vitality of these activities through supervision, fundraising, external activities and seminars. For example, the KRR group co-hosts the Leeds-York Distinguished Lectures in KR with recent speakers such as McCarthy (Stanford) and Selman (Cornell). Other speakers include Lesk (NSF, USA), Informatics and Johnson (Utah), SCV. Each group leader is responsible for the development of the activities of individual staff and students in conjunction with the Staff Development and Promotions Committee. The overall welfare of, and policy relating to, PDRA staff on fixed term contracts is monitored in line with the University policy linked to the Concordat. University computing research is steered by the Research Director’s membership of the Faculty Research Board and by his promotion to Engineering Research Dean.
RA5.1.2 Graduate Research The Graduate Education Committee under Dew oversees the recruitment and monitoring of research students. Ph.D. student completions number 64 in this RAE period as opposed to 34 in the last period. New students are assigned to research active staff and are monitored and mentored throughout their Ph.D.s with an annual review and a formal monthly supervision check. A weekly „research corner“ and frequent seminars provide a natural framework for multidisciplinary insights, ideas and support to be generated. Funding is available to students to attend and present a paper at a minimum of one conference per year. Postgraduate numbers have held steady in the face of competition from a lucrative commercial sector. Studentship funding from EPSRC is supplemented by an internal studentships fund (£290k since RAE 96).
RA5.1.3 Research Infrastructure The School has consistently maintained a well-founded laboratory with 12 staff to support a common research and teaching infrastructure. In addition, each research group maintains its own dedicated laboratory with a small extra spend (£50K) ensuring that there is no mismatch between immediate equipment needs and funding awards. Two particularly significant developments are that: (i) a Leeds JREI-funded (HEFCE £390k) consortium led by Dew provided a 32-processor Origin 2000 and a 20-processor Beowulf parallel machine that, together with a 16-processor School Beowulf system, facilitate parallel processing work, and (ii) the Informatics group is already making a significant contribution to research by providing a multidisciplinary research laboratory established with a HEFCE capital project grant of £800k and a JREI grant of £427k for a state-of-the-art Virtual Environments (VE) Laboratory with a TAN Holodesk (to create a virtual 3D volume of space), cybergloves, haptic interface devices and an intelligent conference room. A 12-processor SGI Onyx3 system services these facilities. A recent Wolfson grant of £80k will link this activity to upgraded Bioinformatics laboratories as part of the developing Leeds informatics network.

RA5.2 Staffing Policy Academic leadership has been strengthened by the University’s promotion of Berzins, Brodlie and Cohn to personal chairs and Jimack to a Readership during the RAE period. Continuity in the five research groups is provided by the best one third of researchers submitted in RAE96. Since RAE96 six staff have been promoted in moves to other Universities, three have retired, two have moved to industry and three have had administrative university promotions related to teaching. The number of teaching assistants has increased from 2 to 8 to allow research active staff to be just that. The recruitment of nine outstanding young staff has enhanced existing strengths in the research groups and has reflected international and University priorities in a major new activity: multidisciplinary Informatics (Inf). All these recent appointees have exceptional research ability. The appointments are: TCS (Vuskovic, Müller), KRR (Stell, Zakharyashev), CVL (Bulpitt), SCV (Hubbard) and Inf (Bullock, Noble, Ruddle). Bullock and Noble have been appointed in open cross-University competition as a result of the University Research Fellowships scheme that allows them to concentrate on Informatics research for the first five years of their careers at Leeds.

RA5.3c Computer Vision and Language Group (CVL) (Prof. Hogg, Drs Bod, Boyle, and Bulpitt, 12 Ph.D. students, 6 PDRAs, £1,002k research spend, 71 papers) has three main interests:
Behaviour modeling research centres on the acquisition, representation and application of spatio-temporal models, with particular emphasis on the domains of human and animal behaviour. As a prerequisite to behaviour modelling, the group has developed a number of influential methods for shape modelling and tracking, extending the predictive accuracy of Baumberg’s contour tracker with learnt stochastic dynamics [Hogg1;Boyl4], developing a new method for dealing with discontinuous dynamics using a Markov process between multiple linear shape spaces [Hogg2] and proposing an entropy measure for parameter scaling within learning systems based on principal component analysis [Boyl2]. The group has pioneered the development and application of several kinds of stochastic process models for representing behaviour. In their prize-winning work, Hogg's students, Johnson and Galata (see RA6), and Bulpitt [Bulp4] have developed neural network architectures and variable-length Markov models to represent long-term spatio-temporal patterns of object behaviour; the first application of the latter within computer vision. Several novel applications of such models have been explored, notably for the prediction of animal behaviour [Bulp4;Boyl4], human-computer interaction, and surveillance [Hogg3]. Hogg has collaborated with the EU Joint Research Centre in prize-winning work on 3D reconstruction [Hogg4], undertaken in part to provide spatial backgrounds for graphical animation of behaviours. The work has been supported by EPSRC (£155k), an EU-HCM research network (£112k), and an EU-ACTS project (£340k), together involving the Universities of Reading, Edinburgh, Grenoble, IST-Portugal, Genoa and the EU Joint Research Centre at Ispra. An EU-IST project, COGVIS, (EU €590k) has recently been approved to study cognitive aspects of vision in collaboration with Cohn, and in partnership with the Universities of Genoa, KTH-Stockholm, ETH-Zurich, and the Max-Planck Institute in Tübingen. The results of research on 3D reconstruction [Hogg4], poultry tracking [Boyl3], and on the recognition of music scores [Boyl1] are being exploited via two companies and Ministry of Agriculture Fisheries and Foods (MAFF).
Medical Imaging and Bioinformatics Major achievements have been Bulpitt’s work on the development and application of a bifurcating mesh for extracting shape from Magnetic Resonance and Computed Tomography data [Bulp2]. This work is continuing under a recently awarded EPSRC grant (£145k) [Bulp3] and plays a primary role in the Centre for Medical Imaging Research (COMIR) along with Berry and Smith (Medical Physics) and Mardia (Statistics). Bulpitt is now working with Westhead (Biochemistry) on Bioinformatics research originating in work on rigid registration [Bulp1] and linking to the Informatics Research Institute (BBSRC/EPSRC Bioinformatics £134k).
Natural Language Processing Leeds has a distinguished record in statistical natural language processing. The Data-Oriented Parsing (DOP) model [Bod2] competes with the best existing work in natural language parsing (see [Bod4]). The model subsumes standard probabilistic models as special cases and has been tested using different grammars and application areas. This has been extended to the linguistic representations of Lexical-Functional Grammar theory in work with Kaplan [Bod3] and, practically, the model has been used in dialogue processing and spoken language understanding systems [Bod3]. Theoretical work on DOP has shown the existence of a stochastic analogue to the famous Chomsky hierarchy of (non-stochastic) formal languages [Bod2]. Bod’s Advanced Research Fellowship (EPSRC £229k 50% FTE averaged over a decade) is devoted to combining linguistic and statistical information to arrive at improved language models for speech. Cooperation with Xerox PARC (Kaplan’s NL group) has resulted in a linguistically motivated statistical parser which has been successfully tested on the Verbmobil and Homecentre corpora [Bod4].

RA5.3e Informatics (Inf) (Profs Dew (75%) and Wren (30%), Drs Bullock, Noble and Ruddle; 22 Ph.D. students, 10 PDRAs, £2,128k research spend, 76 papers). Since its formation in 1999, the group has attracted £1.7M+ (see RA5.1.3) for multidisciplinary informatics research by developing new computational techniques to solve challenging problems from specific domains. Recent appointments (Bullock, 9/99; Noble, 9/00; Ruddle 01/01) bring domain-specific expertise to this activity as demonstrated by papers in leading biology [Bull1, Nobl1] and psychology [Rudd1] journals. Current research strengths are reported in three multidisciplinary areas:
Virtual Environments (VE) research aims to improve the realism and interactivity of virtual environments. Dew’s research on the assessment of cosmetic quality within a VE applied to the automobile industry in a joint project (EPSRC £214k) with Strathclyde, Rover, Managa and SGI has led to [Dew4] (best paper at ASME IDETC-CIE 2000) and to commercial exploitation. Ruddle’s VE [Rudd1,2] and HCI [Rudd3,4] expertise has made it possible to extend this work to virtual buildings and cluttered environments. Dew’s study of Collaborative Virtual Environments (CVEs) [Dew2] in manufacturing was in collaboration with the Keyworth Institute for Manufacturing and Information Systems Engineering, a centre of excellence for the application of IT to manufacturing, which he co-founded with Prof. de Pennington (UoA 30). Dew's research with the School of Geography and the University Library (£2M funding) on CVEs for knowledge transfer has led to the Leeds Virtual Science Park, an Internet knowledge service provider, and has spun off a company (Symularity, formerly VWS Ltd). New research [Dew3] on collaborative interactive software architectures (initially with British Telecom and now with Symularity) with Bath’s HCI Group (EPSRC £175k) extends this work to study model-based software architectures for CVEs that take into account the social and contextual issues surrounding the way that people work in networked communities.
Biosystems Bullock and Noble pursue interdisciplinary research applying AI techniques to challenging biological problems [Bull3] and vice versa [Nobl1]. Noble and Bullock (EPSRC £66k) have pioneered the use of computer simulation to model biological adaptive systems, falsifying models of the evolution of symmetry [Bull1], initiating simulation research into the evolutionary dynamics of signalling systems [Bull2, Nobl2,3], explicating the links between mechanistic and functional explanations for parental investment [Bull4], and refuting a proposed role for aggressive displays in natural populations [Nobl4]. Ongoing collaboration with Dr. Cliff (Hewlett-Packard Labs £100k) exploits the dynamic behaviour of biological and biologically inspired systems in domains such as software agents for e-commerce. A recent joint grant with Biochemistry (Wolfson £81k) facilitates Bulpitt's development of new algorithms for analysing biological data derived from genome sequences (BBSRC/EPSRC £145k) in joint work with the CVL group.
Transport Scheduling Wren’s work is at the forefront of using and combining mathematical programming and metaheuristics [Wren1] (4 EPSRC grants and £297k industrial funding since RAE 96) to address the NP-hard combinatorial optimisation problem of bus and train driver scheduling. Research (EPSRC £116k) completed in 1996 subsequently resulted in a system used commercially by many bus and train companies [Wren2,3] and recently adopted by the UK’s largest bus group against leading international competitors after extensive testing. The system now incorporates results from a current EPSRC grant (£142k) that solves very large real driver scheduling problems through column generation in an integer linear program (ILP). The development of a genetic algorithm [Wren4] that learns from the relaxed solution of an ILP enables more complex instances to be solved than by previous mixes of ILP and heuristics. Not only have better solutions been obtained to problems near the previous ILP limit, but new hybrid algorithms combining the relaxed ILP approach with constraint programming and tabu search (EPSRC £260k) will address future applications needs.

• Logic, Algorithms and Complexity
The research area covered is: the design, analysis and engineering of parallel and sequential algorithms; the complexity of computation; logical aspects of computation relating to algorithms and complexity; and computational aspects of group and semigroup theory. Much of the group’s research lies at the interface between Mathematics and Computer Science.

• Distributed and Reactive Systems
This research group is concerned with the specification, verification, design and security of real-time, fault-tolerant and distributed systems. Whilst primarily concerned with theoretical aspects of distributed and reactive systems, its work has strong links with applications involving, for example, hybrid systems, computer security, applied formal methods and object-oriented systems.

• Semantics
The primary focus of this research group is the study of the more qualitative aspects of programming and programming languages. The techniques and methods used are mainly related to category theory, type theory, rewriting and operational semantics, but the group also has interests in applying its research to areas such as software reasoning and verification.

In addition, there are many interactions between the three groups, so that the overall research is coherent. As a consequence, general group activity is of interest to all and extremely well supported. This activity includes: a regular Computer Science Seminar to which a speaker from another university is invited; a regular Internal Seminar at which staff and postgraduate students speak; and numerous internal Reading Groups and Lecture Series addressing inter-group themes. Furthermore, Computer Science at Leicester is involved in the Midlands Graduate School in the Foundations of Computing Science, a joint venture between Computer Science departments in the Universities of Leicester, Birmingham and Nottingham. Each department provides a variety of lecture courses for the postgraduate students in all three departments. In addition, all Computer Science postgraduate students at Leicester undertake our Graduate Programme, designed to support postgraduate students in their research activities.

Research Group 1 Logic, Algorithms and Complexity

Staff Professor I.A. Stewart (Group Leader), Professor R. Raman, Professor R.M. Thomas,
Dr D. Kuske, Dr S. Yang.

Scientific Aims
• to explore the link between logical definability and solvability using resource-bounded models of computation;
• to examine the relative expressibilities of logics, also in comparison with the computational power of models of computation used in concurrency theory;
• to investigate computational aspects of groups and semigroups, in particular, classes of automatic groups and semigroups;
• to study, both mathematically and empirically, the practical performance of sequential and parallel algorithms;
• to develop new and improved sequential and parallel algorithms for fundamental problems in computing;
• to help develop the rapidly-emerging field of algorithm engineering which includes the exact (constant-factor) and empirical analysis of algorithms and heuristics and the implementation and fine-tuning of (non-numerical) algorithmic software libraries.

Current Research Descriptive Complexity Theory and Finite Model Theory. Capturing complexity classes using logics (IAS). Normal forms for logics and complexity-theoretic completeness (IAS). Positive Turing machines and logical monotonicity (IAS). Computational power of classes of program schemes (IAS,PhD). Definability in monadic second-order logic (IAS). Zero-one laws (IAS). Ehrenfeucht-Fraïssé games, locality and database theory (IAS,ResAss). Constraint satisfaction problems (IAS,PhD).
Logical Calculi and Concurrency. Finite-state models of concurrent systems, in relation to order theory, topology and automorphism groups (DK). Expressive power of finite-state models in relation to monadic second-order logic, rational expressions and monoids (DK). Temporal logics (DK).
Formal Language and Automata Theory. Sub-classes of context-sensitive languages (RMT,PhDs). Formal languages and word problems (RMT,PhDs). Rational and recognisable sets in monoids (RMT,DK). Generalised notions of automata (RMT,PhD). Syntactic monoids (RMT,PhD).
Computational Aspects of Groups and Semigroups. Automatic groups and semigroups (RMT,DK, ResAss,PhDs). Computational complexity of word problems in groups and semigroups (IAS,RMT, ResAss,PhDs). Rewriting in groups and semigroups (RMT,ResAss,PhDs).
Algorithm Engineering. Mobile ad hoc networks and dynamic graphs (IAS,PhD). Implementation and experimental evaluation of hybrid data structures (RR,ResAss). Data cache behaviour of both uniform and non-uniform distribution sorting algorithms (RR,PhD). General techniques for data cache and translation-lookaside buffer optimisation (RR,PhD). Hybrid adaptive neural network, constraint satisfaction adaptive neural network, heuristic and genetic algorithm approaches to problems in combinatorial optimisation (SY). Traditional and generalized maximum flows for network problems (SY).
Algorithm Design and Analysis. Algorithms for parallel heap construction (RR). Dynamic closest-pair problems (RR). Parallel and sequential integer sorting (RR). Routing on meshes with buses (RR). Single-source shortest paths problems (RR). Construction of perfect hash functions (RR). Inter-connection networks for (faulty) distributed-memory multiprocessors (IAS,PhD). Greedy algorithms in graphs (IAS,PhD).

Highlights of Achievements IAS is one of the world experts in descriptive complexity, particularly in the explicit links between complexity classes and (Lindström) logics and the ensuing logical translations. His work receives international recognition; for example, a particular logical normal form has been named Stewart Normal Form [see Georg Gottlob: Relativized logspace and generalized quantifiers over finite ordered structures, Journal of Symbolic Logic 62 (1997) 545-574]. In publication [IAS2], a robust notion of positive polynomial-time was developed and an open problem posed by Michelangelo Grigni and Mike Sipser in 1992 was solved.
RR is a leading international researcher in the design and analysis of algorithms, and is one of the world’s experts in the rapidly emerging field of algorithm engineering; for example, he has twice been invited to contribute papers to special issues of the ACM Journal of Experimental Algorithms (the leading journal in the field) devoted to selected papers from internationally leading conferences. In [RR1], he gave new algorithms for the permutation routing problem and the k-k routing problem in multi-dimensional meshes. This paper appeared in a special issue of the journal Algorithmica consisting of the best 8 papers from 140 submissions to the first European Symposium on Algorithms.
RMT is a researcher of world reknown in the theory of computation in algebraic structures. RMT and his co-workers have pioneered entirely new approaches to reason about, and compute in, semigroups and groups; for example, in [RMT2], a mixture of theoretical and computational techniques were used to completely answer a question of Donald Coxeter that had been an open problem since the 1930's.
DK is a world leader in the applications of finite automata to the theory of concurrency. He introduced the concept of a k-chain covering and used this technique, for example, to describe the expressive power of asynchrounous cellular automata in [DK2]. In [DK1], he answered an open question (in the negative), posed by Paolo Boldi, Felice Cardone and Nicoletta Sabadini in 1993, on the partial order of traces.
SY is a young researcher who received his PhD in 1999 and spent one year as a postdoc before winning a lecturership at Leicester in November 2000. He has made a very impressive start to his career primarily in the area of hybrid approaches to job-shop scheduling.

Research Group 2 Distributed and Reactive Systems

Staff Dr Z. Liu (Group Leader), Mr Y. Chen, Dr G. Lowe, Dr I. Ulidowski, Dr N. Yoshida.

Scientific Aims

Agent Theory (Wooldridge, Parsons, Fisher, Dixon, Hustadt).
Work in the agent theory area has been carried out in collaboration between the Agent ART group (Wooldridge and Parsons) and the Logic and Computation group (Fisher, Dixon, Hustadt). A number of issues have been explored, with particular emphasis placed on the use of modal (epistemic, temporal) logics for the specification and verification of multi-agent systems, particularly in the specification of social processes (such as cooperative problem solving). In joint work with Professor Gabbay (Kings College London), proof methods for epistemic temporal logics have been developed (EPSRC Grant GR/K57282).

In the period 1996 – 2000 we have seen sustained growth in the Department. We have made 14 new academic appointments, both to strengthen and to broaden our fields of activity; 7 staff have left (3 retirements, 3 to senior appointments at other institutions and 1 out of academia). Of the new staff, 12 are in post and 2 new senior lecturers (Huth and McCann) arrive in July 2001. In addition, the Department was successful in a bid to the Research Councils for the creation of a new research group in Bioinformatics. We have appointed Muggleton to a Research Chair in Bioinformatics (starting in July 2001) and expect to appoint at least one supporting position in the near future. This will enhance existing activity and strengthen our links with the Life Sciences, the Imperial College School of Medicine and the new Institute of Genetics and Genomics at Imperial. During the assessment period we have also made appointments which strengthen our existing activities in Visual Information Processing and Custom Computing and created a new group in Data Mining; two of our recent appointments are experts in probabilistic computation and will enhance Quantum Computation activities with members of the Departments of Physics and Electrical and Electronic Engineering within the College.

In 1999 the College repeated the Governors' Lectureship scheme, successfully introduced in 1994. The purpose of the scheme was to encourage "new blood" appointments by providing central funding for an initial period to support the appointment of promising young researchers to lectureships. Departments competed for appointments under this scheme, and Computing was successful in making two appointments (Lupu and Toni) included in the numbers mentioned in the preceding paragraph.

Mentors are appointed for all new lecturers; these are more experienced academics who have the responsibility to advise the new lecturer in all academic matters. The mentor is involved in the probationary review process. The progress of new lecturers is formally reviewed annually. The College operates a sabbatical scheme for established staff. During the assessment period, 11 members of staff had sabbaticals.

The Department has a research committee, chaired by the Director of Research (Hankin) and including research group leaders, the Director of the Imperial College Parallel Centre, ICPC, (Darlington) and the Head of Department (Kramer). The Department has strong links with industry. We have been successful in attracting substantial donations that fund PhD bursaries, equipment and laboratories (including Arthur Andersen, Deutsche Bank, Fujitsu, HP, IBM, Microsoft and Symbian). Our objective has been to foster long term links with industry that encourage the exchange of ideas and technology and that can influence research focus and direction. Professors Shigeru Sato (Fujitsu), Michael Jackson (M J Associates) and Ian Page (Celoxica) are Visiting Professors in the Department. Most of the groups have active seminar series which frequently feature international speakers; this is supplemented by a Departmental series which includes talks of more general interest from industrialists and leading international speakers.

Our research investigates and develops both theory and practice. This dual approach is intended to ensure that the techniques we develop are theoretically sound, directed at real needs, and suitable for integration with other established and emerging technologies. In our 1996 return, we identified 23 technical objectives. In all cases we achieved or surpassed our objectives (see achievements in the following section). The achievements listed are all backed by publication in peer-reviewed articles. Many of our achievements over the assessment period have direct application to, or have anticipated, the UK and international GRID initiatives and the new EU–initiatives in Global Computing. With new appointments in quantitative computing and Bioinformatics, we are ensuring that we stay at the forefront of Computer Science research.

Research achievements and plans

1. Distributed Software Engineering
This grouping involves researchers DSE 1 - 8. Their work is focussed on software architecture, design and analysis, distributed systems, and requirements engineering.

3. Minimax algorithms will be explored for applications to engineering design. Optimal decision making requires efficient optimisation algorithms with efficient search procedures. Advanced interior point and sequential quadratic programming algorithms will be investigated, tested and extended to large-scale problems for high performance computing. (Rustem)

4. To investigate optimisation of mobile telephone networks. Initial work is applying optimisation methods to systems modelled by networks of non-standard queues. For example we are investigating the minimisation of the loss rate for video traffic and the response time of data traffic subject to constraints on maximum video response time and maximum data loss rate. (Harrison, Knottenbelt, Rustem)

5. To research and develop the software and hardware techniques that will allow the integration of geographically distributed high performance physical and software resources (parallel machines, data archives, scientific instruments, data feeds, modelling techniques, visualisation capabilities, software components and packages) to provide an integrated and unified computational resource that can be accessed and used in a seamless and transparent manner. The importance of such developments has been highlighted by the recent Government Science White Paper that set out an ambitious programme for the realisation of e-science in many application areas. (Darlington, Field, Guo)

6. To develop further the internet-based data analysis technology adopted in the Kensington system to realise an infrastructure supporting full scale e-science activities. The research will devise new mechanisms of discovery driven information browsing, a tight integration of data mining with information retrieval for dynamic knowledge management, and a systematic way of managing intellectual properties. (Darlington, Guo)

7. To research, develop and implement a content-based multimedia information retrieval system integrating media such as videos, images, music, the web and text repositories. (Rueger)

3. Interactive Media
This grouping involves researchers IM 1 - 6. Their work is focussed on image processing and custom computing.

The main technical objectives for the coming period are:

1. To design and implement next generation interactive simulation and augmented reality environment for medicine, including surgical skills training and assessment, prediction of complications, and instrument design. (Gillies, Rueckert, Yang)

2. To develop novel ultra-fast interactive anatomical/functional imaging and reconstruction techniques for cardiovascular magnetic resonance. (Yang)

3. To explore psychophysical models of human visual search and to investigate the use of probabilistic inference and visual tracking for establishing a new framework for decision support systems in image understanding. (Gillies, Yang)

4. To explore and implement multi-modal image fusion techniques based on structural/functional modelling and registration, and to establish novel image based rendering techniques for visual augmentation in virtual environments. (Rueckert, Yang)

5. To understand the unifying principles and generic analysis and synthesis techniques for developing custom computers, and to apply such principles and techniques in producing effective custom computing tools and systems, particularly for applications involving media processing. (Luk, Mencer)

5. To further develop and implement our domain-theoretic model for solids and geometry to provide a proper framework for CAD engineers. We will also construct and implement a domain-theoretic data-type for differential equations which can give solutions to those equations which are either ill-conditioned or are defined using partial functions. (Edalat)

6. To develop languages and models describing evolving object oriented software (eg objects changing class, classes dynamically loaded and checked, classes being extended on the fly) in a type-safe manner. (Drossopoulou, Eisenbach)

The Algorithm Design Group (ADG) was formed in 1991 and it has an established international presence. Research has followed the directions laid out in the 1996 RAE. It has achieved strong results in string regularities and matching, parallel computing, word-level parallelism, image decomposition, data structures, computer-assisted music analysis and network optimisation. Research was extended to the area of dynamic graph algorithms with the appointment of Christoph Zaroliagis (March 1998 until July 1999) and to network communication with the appointment of Ralf Klasing (Sept., 2000). While continuing theoretical research on design and analysis of algorithms, the ADG has recently increased its profile substantially in algorithm engineering, which includes experimental work on practical performance and applicability of newly developed algorithmic techniques.

Tomasz Radzik derived new bounds on the time complexity of computing approximate solutions for the multicommodity flow problem and implemented new efficient algorithms for it, as well as the generalised flow problem and dynamic graph algorithms.

Costas Iliopoulos has designed methods for optimal prefix matching, string covering and dictionary matching in two dimensions, algorithms to discover all the squares and covers of a Fibonacci string in linear time, the design of algorithms for linear-time decomposition, and analysis of partially occluded images and their impact on wide ranging applications.

Richard Overill developed a model of heterogeneous parallel computing in which a single task represented by an explicit parallelism profile function is optimally partitioned between the components of a heterogeneous parallel processor consisting of a parallel vector computer (PVC) tightly coupled to a massively parallel processor (MPP).

Rajeev Raman has obtained the best deterministic bounds for the single-source shortest-paths problem on directed graphs with non-negative weights. He has developed optimal dynamic algorithms for the closest-pair problem. He also studied the effect of cache and TLB effects in distribution sorting algorithms.

Christoph Zaroliagis designed the optimal solution for the shortest path and max-flow/min-cut problems, and he developed a new parallel priority queue with multiple insertions and multiple decrease-key in constant time. He has also contributed in the experimental study of several dynamic algorithms.

Costas Iliopoulos, Dr Raman and Prof Winder designed efficient methods for finding repeated motifs in a music score, as well as computing evolutionary paths in monophonic and polyphonic pieces of music.

Ralf Klasing investigated different network types as candidates for parallel architectures or communication networks. He also developed approximation methods for the solution of hard (e.g., NP-hard) problems and in the proving of the non-existence of effective approximation algorithms.

Objectives of the ADG for the next assessment period include:

1. Design and analysis of algorithms on combinatorial string problems with applications to the analysis of partially occluded images, data compression, music analysis and melodic recognition, and molecular sequence analysis.

2. Deriving efficient approximation algorithms and heuristics for network communication tasks in general network topologies; investigating fault-tolerance and communications models in optical networks.

3. Investigating the trade-off between the approximation quality and the running time of computation.

4. Improving methods for handling constraints, such as the finite precision arithmetic, in design, analysis, and implementation of network optimisation algorithms.

The NLP is a new group in DCS. It started with the arrival of Jonathan Ginzburg and Shalom Lappin at KCL in 1999, and Chris Fox in 2000. The main areas of research of the group are formal and computational semantics, implemented constraint-based grammar formalisms, and computational modelling of dialogue. The group has three PhD students working on funded research projects in these areas.

Shalom Lappin implemented ellipsis and fragment resolution systems that run on top of a typed feature structure grammar-parser, constructed a framework for a hyperintensional semantics of natural language (joint work with Chris Fox), explored the formal and computational properties of alternative grammar formalisms, developed a semantics for vague generalized quantifiers in natural language, and explored the logical properties of the semantic types of natural language.

Jonathan Ginzburg has done work in the formal and computational representation of dialogue, and he has just published a joint monograph with Ivan Sag of Stanford University on the syntax and semantics of interrogatives. He works with Robin Cooper’s dialogue group at the University of Goethenburg.

Chris Fox has worked in the area of computational semantics, developing a semi-decidable theory of discourse using dependent types within a classical, first-order framework. He has written a book on foundational issues in formal semantics. He has also been working on an axiomatic analysis of questions and answers, and has done some preliminary work on an analysis of vernacular mathematics.

Costas IIliopolous is working on data compression with application to natural language strings with linguists from the University of Marne la Vallée.

Objectives of the NLP Group for the next assessment period include:

1. Developing and extending the existing dialogue management system. This work is intended to yield an implemented prototype that handles a wide range of dialogue interaction types found in the British National Corpus and other large dialogue corpora.

The LCG was formed 2 years ago with the arrival of Dov Gabbay, and it now includes eminent international researchers such as Michael Zakharyaschev, and David Makinson. It is in the process of recruiting Andrew Jones from Oslo. Research in the group concentrates on the following topics: logical foundations, proof theory, labelled deductive systems, automated deduction and goal-directed theorem proving, artificial intelligence and knowledge representation, modal and description logics, temporal logic and actions, belief revision, deontic logic, foundations and extensions of logic programming, deductive databases, fibring and combining systems, practical reasoning and non-monotonic logic, legal reasoning, and computational linguistics.

David Makinson works on deontic logic. He was head of publications at UNESCO before joining he Department as a Senior Research Fellow at the rank of Professor.

Odinaldo Rodrigues has been working on several aspects of non-monotonic theory change. More recently he has been working on the revision of non-classical logics and the comparison between the resulting operation and classical revision.

The SEG was formed recently from the DKEG, which existed at the beginning of the assessment period, with the appointment of Profs Russel Winder and Tom Maibaum, the departure of several staff in the area of Information Systems and the arrival of several new staff in the area of software engineering. It reached its present form in 1999 and has doubled in size in the last 2 years. The group has longstanding collaborating with other academic and research institutions as well as with industrial partners in the UK, Europe and the USA and has 5 Research Assistants and 6 PhD students in place during the current academic session. The groups interests include: object oriented notations and tools, operational semantics and meta-notations, the development of reactive systems in B, using temporal logic specifications, the semantics of statecharts; legal reasoning and applications of artificial intelligence techniques in e-commerce and the law, business process modelling (where we have a EU sponsored project), specification languages, such as VDM and B, co-ordinated systems, requirements analysis and the epistemological basis of software engineering. A subgroup continues to work on information systems and focuses on development and assessment of methods and the analysis and assessment of security related issues in IT systems, including internet based systems.

Tom Maibaum came to King’s from Imperial College, where he had served as Head of Department and was a major figure in the software design part of the program. He has further developed an abstract theory of specification, using a framework of general logics and category theory. Some of the ideas were applied to developing a framework (with José Fiadeiro) for specifying reactive, multi-component systems. These ideas were applied to develop a toy programming language for concurrent, multi-component computation, generalising the concepts of superposition. The worlds of specification and programming were related in a compositional framework using categorical approaches. The ideas were applied to foundations for software architecture. An approach to (software) engineering design was developed based on the ideas of logical empiricists (Carnap and his successors) and this is emerging as a potentially powerful organizing principle for software engineering.

Chris Fox has developed a fully automatic conditioned program slicer, which exploits symbolic execution, theorem proving, and semantic preserving program transformations.

Kevin Lano did work on VDM++ which resulted in a significant commercial product and a sophisticated semantic framework. He worked on OO semantics, and this resulted in several significant contributions to the semantics of various notations, development of a refinement notion based on patterns and the devlopment of ideas related to subsystems in OO. He did research on software engineering for process control systems that has had significant successes and resulted in several collaborations. An environment based on B, using principles from OO and temporal logic, is being developed at KCL in collaboration with several PhD students.

Russel Winder has worked on the development of a new computing machine architecture based on the Turing model rather than the von Neumann model of a computer, computational support in Musicology, and use of Web technologies in Medical Informatics. The work on computing architectures is a collaboration with OneEighty Software Ltd. The architecture, which is called ORIGIN and is capable of both hard- and soft- implementation, allows software systems that are very much smaller than equivalent systems using traditional architectures to be written. A clean-room Java execution platform ("JVM"), called GENEVA, has been implemented using only the ORIGIN architecture. This has generated a great deal of interest in the smacrtcard, embedded control and PDA markets. The work cannot yet be published (for commercial reasons), but it will lead, in the near future, to some significant publications.

David Clark finished his PhD during the assessment period, focusing on abstract interpretation and graph rewriting. He continued working on the topics, helping to solve a 13 year old problem, of formalising the Clean strictness analyser without artificially restricting the class of allowed term graphs, by taking a purely operational view of the rewriting. He started work on using techniques from abstract interpretation to analyse security properties of programs and on the analysis of safety related properties of statechart formalisms.

Tony Clark’s research has addressed the problem of rigorous system development using object-oriented notations and methods. Results have included a formal method for the composition and refinement of OO behaviours, precisely defining UML profiles that allow OO notations to be tailored to specific application domains.

Aspassia Daskalopulu finished her PhD during the period and joined KCL in 2000 after appointments at Brunel and the Open University. During the assessment period her research focused on formal analysis and representation of legal contracts for a variety of applications in the context of legal information systems, such as management, administration and drafting. Extensions to this work led to first-order logic formalisations of speech acts that establish contractual relations between parties, in the context of modelling formal aspects of e-commerce applications.

Richard Overill has collaborated extensively with the International Centre for Security Analysis (based in War Studies at KCL) on joint research, development and consultancy projects for government (DERA/MoD, Cabinet Office) and industry (BAe Systems), in collaboration with an industrial partner, AGSL (Anite Government Systems Ltd). He collaborated with ICSA, AGSL and the Post Office in winning funding for a DTI/EPSRC 3-year LINK project under the Management of Information (MI) programme on fraud detection in electronic systems

Nahed Stokes has worked on the development of information systems methods. In particular, she has attempted to address the need for leaner and fitter methods of development, easier to master and easier to adapt to particular project circumstances.

Objectives of the SEG for the next assessment period include:

1. Promoting increased use of formality in the UML by, inter alia, developing semantics-based methods and tools for the use of UML as a modelling language.
2. Developing a practical formal method for reactive systems, based on statecharts and B.
3. Promoting application of relevant formal methods in safety and security-critical systems.
4. Investigating the semantics of subsystems in OO languages.
5. Developing a logic for reasoning about reconfiguration and mobility in multi-component systems.
6. Developing semantics of software architecture concepts, their application in product line architectures for specific business domains, and their relationship to concepts of co-ordination.
7. Continuing work on the static analysis of imperative programs, in particular the theory of slicing.
8. Investigating models of reliability for electronic contract negotiation and e-commerce applications.
9. Investigating the development of formal languages for business process modelling and multi-agent systems.
10. Developing a technical basis for software engineering, based on ideas first put forward by the logical positivists (eg, Carnap) concerning the language and practice of science.
Research Grant Income
The aggregate value of grants held by current members of the Department, at any institution where they have worked during the assessment period, was £4-5M, from the following sources: EPSRC, EU, AHRB, ESRC, JISC, British Council, Royal Society, Royal Academy of Engineering, Wellcome Trust, NATO, Hermes Publishers, OUP, First Foundation (Israel), and internal KCL research funds.

Support for Research

The Department has increased the number of PhD students in the research program significantly in the past few years, going from 6 students in 1996 to 23 in 2001. This increase is primarily due to the expansion of our research active staff and the rise in our grant income, which has made it possible to support more students. We believe that as a Department of 25 academic staff (planned size of the Department by 2002) we should have a stable population of at least 50 PhD students and at least 25 Research Assistants. We are developing ways of funding and recruiting such students. Our quota studentships from EPSRC should grow alongside our portfolio of research grants. We are encouraging staff to apply for studentships associated with grants whenever possible. Some staff hold grants from ESRC and AHRB and we expect to secure further funding from these agencies. We are beginning to obtain industrial sponsorship (e.g., HP Labs) and expect this source to expand.

Support for grants and contracts, on the one hand, and development of Intellectual Property, on the other, are provided by KCL Enterprises, a wholly owned KCL company. Recently, the College appointed a Development Officer, sponsored by a HEROBC award, to support the development of industrial links in the southeast for several groups within the College, including the DCS. We are beginning to exploit this mechanism and have already made some useful contacts. The help of the Development Officer was crucial in organising the recent Faraday Partnership bid led by DCS/KCL.

Other mechanisms used for exploiting research include several important consultancies with key organisations in industry and government and participation in start-ups. An example of the latter is the leading role Prof Winder has played in the start-up OneEighty Software Ltd.

Interdisciplinary work

One of the joys of KCL is the wide range of disciplines in which it is engaged. There are large numbers of potential partners for interdisciplinary work and the department has exploited these possibilities and will expand on these in the upcoming planning period. Existing work includes collaborations with the Music Department on algorithms for music analysis; work with the Department of Philosophy on linguistics, work with the War Studies Department on security analysis and electronic terrorism and work with the Medical school and NHS Authorities on medical information systems. We will continue with these efforts and investigate new partnerships where the importance of software is growing. This is clearly the case for many areas of science and engineering, where software is being used to implement what has been implemented previously using physical components and, furthermore, enabling the implementation of new devices and mechanisms that were not possible to implement using only physical devices. A further area of interdisciplinary work is that of electronic services over distributed systems (e-commerce, e-science, telemedicine, etc), where we believe that we will have important impact, via work with War Studies, Management and Law, on the automation of legal, regulatory and security aspects. This strand of work has already led to a Faraday Partnership bid, with a wide range of external partners, including a number of major commercial, science and government organisations. We hope to build on this initiative.

LOGIC AND FOUNDATIONS OF PROGRAMMING
This group is among the strongest in the world in its area and is concerned in a broad range of activity including: the semantics and implementation of functional, imperative and logic programming; program correctness, theorem proving and proof-editing; knowledge representation and reasoning; process calculi and concurrency; proof theory, type theory, model theory and category theory.

The top priority of the group is scientific output. Virtually all its members have established international research reputations and many have been associated with bodies of work which are making a significant scientific impact. There is a small but stable population of high-quality PhD students and projects have been funded by EPSRC, EU, MathFIT and the British Council.

The achievements of the group are led by O'Hearn and Pym's work on the logic of bunched implications, BI [Pym 3]. One way to view this is as a proof system and term calculus, including the solution of the longstanding problem of giving a semantically clean 'linear' dependent type theory, for a form of relevant logic. From this aspect it has the good proof-theoretic properties demanded by modern logicians, together with a link to the kind of relevant logics that have traditionally lacked any kind of proof theory at all. Another view is as a logical analysis of a semantic model of the sharing and privacy of resources. This allows the modelling of various programming features, including the long-standing problem of local reasoning about mutable data structures (such as Hoare logic for pointers and garbage collection), and contrasts sharply with the restricted analysis supplied by linear logic. The work will be applicable outwith computer science.

This example illustrates the dual aspect of much of our foundational work described here. The results are of independent mathematical interest but are also aimed at impacting directly on the design and construction of computer systems through enhanced modelling and reasoning techniques and through functionally elegant design principles.

Pym is one of the world's leading experts on semantics of proof theory, the proof theory and semantics of logical frameworks, and the theory of proof-search. [Pym 1] solved the long-standing problem in type theory of how to define a linear dependent function space, thereby giving a basis for a logical framework for representing substructural and program logics. Other work involves type-theoretic and semantic accounts of proof-search and provides the first substantial step towards a model-theoretic semantics for reductive logic which adequately handles both denotational and operational concerns.

O'Hearn has been a major figure in moving theoretical work from functional to more realistic programming languages. With Reynolds he has provided a semantic account of the irreversible nature of state change in imperative languages [O'Hearn 4]. More recently, his work on bunched typing has opened up a promising new direction for formalisms that account for the locality of a program's resource access [O'Hearn 2]. This is the basis of his EPSRC project Local Reasoning about State (with Bornat and Pym).

Robinson is a leading category theorist, setting standards of conceptual clarity in semantics. His work (with Power) on premonoidal categories has been influential in opening up a range of uses in the semantics of non-functional languages [Robinson 3]. [Robinson 2,4] show the completeness of a variant of logical relations for reasoning about data abstraction in two different settings. His work on Dyads is aimed at the rapid generation of special-purpose compilers: this extends Moggi's notion of monads to give, for example, a natural handling of threaded state [Robinson 1].

Malacaria is, perhaps, best known for his collaboration with Abramsky and Jagadeesan in building the first syntax-independent, fully abstract model of PCF thereby giving a solution to the longest standing open problem in the semantics of languages. A preliminary version was published in 1994 and, although publication of the full version has been unfortunately delayed until 2001, it has been widely available and has acted as a springboard for a series of similar, previously intractable results. The operational insight the model provides has since led to a theory of program analysis with state of the art performance which is correct by construction. In turn, this has been used (with Hankin, IC) in compiler optimisers [Malacaria 2], in the definition of generalised flowcharts [Malacaria 1] and in the field of computer security where a cubic algorithm for detecting security leakage in higher-order languages has been developed [Malacaria 3].

Honda's work has been concerned with capturing representative programming language constructs, such as call-by-value, as typed process behaviour. He has made significant contributions both to the basic theory behind this [Honda 3,4] and in its applications, using results from games semantics, to capture particular classes of computation [Honda 1,2]. The aim of his current EPSRC project is to provide fundamental, descriptive primitives for distributed computing based on his earlier highly influential and extensively cited development of the asynchronous pi-calculus.

Riis' appointment marks an expansion of our activities into the field of complexity theory where he is particularly motivated by the most famous open problems in the area. [Riis 1,2] both present results surrounding his solution of a long-standing technical problem related to the status of different counting principles in models of bounded arithmetic. [Riis 4] was one of the first papers to apply algebraic methods to link these results to propositional proof systems and this technique now plays a central role in propositional proof complexity. In more speculative, ongoing work Riis is applying group representation theory to prove curious 'complexity gaps' in propositional proof systems, one by-product being a neat uniform method of generating difficult tautologies from the symmetric group.

The Dynamo project (Bell, White and Hodges of Mathematics) was concerned with the model-based implementation of pragmatic logics [White 3] and has led to current work on frameworks for abstract and perspicuous languages for qualitative reasoning about action and change.

Taylor's book [2] unifies categorical and type-theoretic methods in the foundations of computing and mathematics, and provides a novel categorical notion of recursion (well founded coalgebras) that has application to recursive programs. He is now working on a computational treatment of general topology having already [3] shown the relationship between (in) equality and the quantifiers with discrete, Hausdorff, compact and open spaces.

The focus of Gong's research is predominantly on the visual interpretation of moving objects captured in image sequences. In his research monograph [Gong 3], he comprehensively examines the computational nature of human face recognition under constant dynamic scene change. This study provides, probably for the first time, a unified treatment of face recognition as a special case in dynamic vision. [Gong 1] is just one of a series of publications on his investigations into a computationally efficient approach to learning gestures from examples by modelling them probabilistically as sequences of events. Gong led his research group in introducing and developing the pioneering notion of modelling, through learning, temporal structures of facial identity and skin-tone colour changes under varying viewing and lighting conditions [Gong 2]. Among other recent achievements are original contributions to the problem of modelling non-linear face space across the view-sphere where their results show that orientation-selective Gabor filters enhance differences in pose and that different filter orientations are optimal at different poses. This work has been published in numerous journals and conferences (e.g. [Gong 4]).

McOwan is also concerned with motion detection but his interests stem from human cognitive architecture and, in particular, from the ways in which the visual cortex stores and processes information. His main work lies in the implementation of models to replicate this behaviour. In a collaborative project (with Dept of Psychology, UCL) a new biologically-plausible mathematical model of the human cortical pathway demonstrated for the first time that a single motion-processing system could be responsible for the perceived effects in luminance and contrast-modulated stimuli [McOwan 1]. This spatio-temporal gradient model has since been implemented in a real-time demonstrator [McOwan 4]. One objective of his current EPSRC project is to develop the first explicit neural model for active motion camouflage.

de Agapito is the most recent recruit to the department. During her post-doctoral work at Oxford she has been studying difficult problems in the automatic calibration of cameras in active computer vision systems and has developed a set of novel methods drawn from algebraic projective geometry that enable cameras to be calibrated directly from video sequences [de Agapito 1-4]. These can be used to recover the focal length and camera motion when the camera is panned and zoomed. This work has defined the state of the art in the field and is a major, scientific achievement with significant commercial potential.

Liddell's main interest has been in parallel applications but we have reported her under this group on the basis of the strong conceptual links that have existed between the areas within our department and her role as a senior academic in the early development of the vision group. Since taking early retirement she has continued these associations, being joint author with Gong of five international conference papers in 2000 alone (e.g. [Liddell 2]). Her earlier, leading involvement with LPAC is described in RA6a.

RISK ASSESSMENT AND DECISION ANALYSIS (RADAR)
RADAR was formed as a new research group at Queen Mary in March 2000. It is based on the long-standing work of Fenton and Neil, formerly at the Centre for Software Reliability, City University. More recently Marsh (see RA6c) has been recruited from ERA Technology. The level of activity is high, Fenton being (co)-author of more than 30 refereed journal and conference papers since 1996.

The group has its foundations in Fenton and Neil's research in software metrics and software engineering standards based on empirical work with industry and using ideas from measurement theory [Fenton 1-3]. This has provided a rigorous framework for the field of software metrics area and has been widely adopted in industry (see RA6a). Their recognition that software metrics are primarily a tool for managing risk has now shifted their emphasis in this area toward software project risk assessment and reduction where recent work has produced improved methods for predicting and managing software resources.

The current focus of RADAR is now on their pioneering work on Bayesian Net (BN) applications to critical systems. The aim of this is to inject scientific rigour, using BNs and multi-criteria decision aids, to the whole process of decision making in high-stakes and safety-critical environments. The main idea is to explicitly represent and manipulate in Bayesian models both subjective probabilities elicited from experts as well as objective data gathered from system test and in-field use. These models are more easily understood by decision-makers and hence lead to improved processes, better decisions and, ultimately, reduced risks. Some recent work here has resulted in significant interest [Fenton 4].

RADAR's projects include SCULLY and SIMP, both of which started in 2000. SIMP (Systems Integration for Major Projects) is part of EPSRC's Systems Integration Initiative and is addressing the problem of risk and uncertainty management in large-scale systems engineering. In particular, it is applying BNs, coupling analysis and scenario analysis to support BAE Systems with risk, uncertainty and requirements conformance management. SCULLY (Scaling Up Bayesian Nets for Software Risk Assessment, with Philips and Hugin) is developing methods and tools to allow the methodical and rigorous construction of BN applications. The tools are designed to support the initial construction of the net topology, allow the net to be manipulated by experts and non-experts alike and provide a means for maintaining changes. A new project that has recently been announced is SCORE (in collaboration with Dept. of Psychology, Liverpool and worth £421K to Queen Mary over 3 years). The basis of the project is the recognition that many critical failures in complex socio-technical systems can be traced to cultural issues relating to risk. One element of the work is to build a risk accounting system using BNs that will monitor an organization's risk exposure over time taking account of changes to their risk culture.

Much of the technology resulting from RADAR's research is applicable outside computer science and software engineering due to its 'systems' approach to problems. We firmly believe that it is essential for the health of the discipline that it throws up research that is of more general relevance.

NETWORK COMPUTING
The department has had a strong presence in parallel and distributed systems for many years. Over time, the emphasis has changed and the appointment of Avresky in Sep 2000 marks a distinctive move into the core systems area of network computing.

In order to support the transfer of Avresky's activities to the UK the department has established a Network Computing Laboratory to provide the platform for the new group forming under him to pursue his continuing work in these areas.

INFORMATION, MEDIA AND COMMUNICATION
Information, Media and Communication is a newly established multi-disciplinary group whose main areas of research are information retrieval, computer-mediated communication and multi-media information systems. Although these retain links with long standing concerns in the department, the series of appointments from 1999 of several energetic, young researchers with rapidly emerging international reputations has given this area a new momentum and fresh directions.

The activity in Information Retrieval encompasses a variety of formal, empirical and AI approaches. The central focus of Lalmas' wide-ranging research is the development and evaluation of effective formalisms for modelling information in the places and forms that it appears in an IR system. Her original work in applying the Dempster-Shafer theory of evidence to capture the uncertainty inherent in the representation of content is becoming increasingly influential in the field of web-based search and retrieval [Lalmas 4]. She has subsequently developed her research in several new directions. One example is her development of a model that copes with the disparity between different types of components (multi-media, distributed and multi-lingual) in heterogeneous documents [Lalmas 3]. Another is a novel framework for combining document representations that both incorporates the semantics of the information and aggregates the uncertainties of the individual representations. This provides the significant benefit of a comprehensive retrieval language [Lalmas 1].

Roelleke's overlapping work on logical models adds further breadth, particularly through his concern for practical techniques which can effectively and efficiently be applied to large amounts of data. This has resulted in the design and implementation of the HySpirit system which provides a platform for knowledge representation with a focus on combined content, fact and structure retrieval [Roelleke 2]. He has developed a novel approach that introduces the concept of 'virtual contexts' for structured document retrieval and applies four-valued logic to meet the requirements of contradictory and incomplete knowledge sources [Roelleke 1]. He has also established the probabilistic relational algebra PRA as a generalization of the standard database model thereby enabling an optimal level of integration of databases with IR bringing with it all the advantages of DBMS [Roelleke 3].

Reid's research in user-centred evaluation of IR complements these activities nicely. During her PhD work she developed a promising new framework centred on the task, rather than the query, as the primary unit of evaluation [Reid 2]. This takes account of various deficiencies of previous evaluation paradigms by incorporating organizational and social factors. Her contributions also include a new, task-based notion of relevance, task relevance, and, to take account of the wider context beyond the task performer, she has extended this with a new evaluation criterion, information value [Reid 1].

Collaborative research projects in IR build on the complementary expertise of the various members of the group (including Healey). The aim of the EPSRC-funded FOCUS projects (with the University of Dortmund) is to develop and implement new models for structured document retrieval and to evaluate their effectiveness on a large collection of XML documents [Lalmas 3]. The EU project GRIS (with the HCI Lab at Ris/o National Labs, Denmark) is investigating the information seeking behaviours of users with the aim of predicting users' strategies and the development of models to support these.

Healey's research aims at applying theories of communicative practices developed in the social sciences to the analysis of remote, multi-modal communication where he is making an acknowledged impact in the field of graphical communication. He is PI on the ESRC/EPSRC PACCIT project MAGIC (with ATR and the universities of Glasgow and Edinburgh) where current research is focussed on generic mechanisms of co-ordination in interaction. A further EPSRC project (with King's College, London) is developing themes from Healey's PhD work to examine the problems posed by imperfect communication [Healey 1].

Healey's work was successfully applied to the final phase of the Mushroom project, the first stages under Coulouris being concerned with the design of general-purpose, distributed systems to support co-operative work. His analysis of the communicative practices of the various parties involved in diabetic health-care led to a novel framework for modelling asynchronous collaboration based on artefacts, information flow and the participants' level of grounding [Healey 2]. This has attracted the interest of the US company Avaya who are keen to exploit the results for the design and evaluation of multi-modal communication in the context of Wilbur's work on 'virtual clubs', developed during her series of projects with BT and Bell Labs/Lucent Technologies [Wilbur 1,2].

Paker's research concentrates on parallel architectures for advanced multimedia processing, based on his work on the EU Mona Lisa and AMPA projects which pioneered virtual studios [Paker 4]. PROMETHEUS, a LINK Broadcast Technology project led by the BBC, is the flagship of UK research effort in 3D television. Paker's role is to explore how parallelism can be used to meet the challenging requirements of 3D motion capture, modelling, transmission and display, in particular in compressed form [Paker 1]. The work is linked to the 3D scientific visualization research of the Computational Science Centre, Dept. of Chemistry, with the support of a JREI-99 grant for an SGI Onyx installation.

Paker's EU CustomTV project involving the use of digital TV for multimedia content broadcasting has been followed by the Framework 5 IST project SAMBITS aimed at integrating interactive broadcast media with the internet (with the Dept of Elec Eng and several major broadcasters). Lalmas and Healey are working alongside Paker as contributors to the project, in particular with the development of multimedia studio technology for off-line and real-time design of interactive services. Lalmas is directing work in the retrieval of diverse types of content, including video, and Healey is responsible for interface design and evaluation. The research team has published four international conference papers since Sep 2000.

Links with the foundational areas of the department are actively sustained through Rowson and White. The EPSRC-funded ARAMIS project was focused around the development of the first interactor model to have the crucial property of compositionality, thereby allowing interactors to be 'plugged together' without loss of generality [Rowson 1,2]. Rowson's experience in protocol verification was central to the novel definition of the key notion of task conformance [Rowson 4].

Since 1996 the Department has been on a strong upward trend in terms of the quality and quantity of its publications, level of external funding, research student numbers and, particularly, the international impact of its research. This trend is accelerating, especially in the latter part of the review period.

Over the review period the Department has developed its research structure into two interrelated research groups: Computer Learning, and Theory of Computing.

1. Our activities in Computational Learning have strengthened further. In 1998 the College established The Computer Learning Research Centre (CLRC; Director Prof Alex Gammerman; 10 academic staff members, including 6 professors) which has become a focus for fundamental research in the field of machine learning, inductive inference and high-dimensional data analysis.

2. The Theory of Computing group (TOC; Director Prof John Shawe-Taylor; 6 members of academic staff, including 2 professors) provides for academic leadership and cohesion of research planning in constraint satisfaction; safety and security; and combinatorial algorithms and complexity. It evolved from smaller groups working in these areas, which shared a common theme of theory of computing, and has successfully led to a fruitful interchange of ideas and a focus for strategic development.

Naturally, though, the research themes cut across the group division, for instance, work on constraint satisfaction and learning theory is going on in both groups.

In addition we have established a network of our 8 Visiting Professors from Europe, USA and Australia who with other academic visitors are involved in collaborative "distributed“ research in the form of joint publications, seminars, grant-funded projects and additional supervision of PhD students. This arrangement also gives us flexibility to develop research in distinct areas such as bioinformatics and computational finance.

Since 1996 the Information Security Group (ISG) has moved fully into the Mathematics Department, consistent with its own developing research focus and in support of its MSc programme. The group is submitted under UoA 22. Collaborative research however continues between the ISG in Maths and TOC in Computer Science. The Signal Processing group completed and published the work planned in 1996, before several members departed or retired, and the remaining staff have joined CLRC since their interests are in pattern recognition and evolutionary algorithms.

One of our strategic goals is to create a new Bioinformatics Group to utilise the department's strength in machine learning for biological sequence analysis. This has been initiated by new appointments, with early recognition by the award of a BBSRC/EPSRC grant.

Research policy and environment
The Departmental Research Management Committee is the policy forum which initiates and co-ordinates research activities, and advises on strategic plans for research development. It reviews the Department’s research plan and administers the research budget. The Committee funds innovative small-scale projects and pilot studies not yet suitable for external funding. This stimulates originality and encourages development in new (unpredicted) research directions. It also considers applications for sabbatical leave, and monitors its outcome. Every academic has a research plan, which is discussed with the Head of Department at appraisal. The special needs of young staff are addressed both in this process, and via College training schemes. The Committee attempts to ensure that our research is consistent with national and regional priorities as identified by the Office of Science and Technology, the DTI, the Research Councils, and the local R&D community. It is a departmental policy to expand the postgraduate community and our Postgraduate Management Committee monitors the progress of research students (both PhD and MSc in Computer Science by Research), and assists their development through activities such as training sessions in conducting research, presentation skills and writing papers. Research students are encouraged to participate in conferences, workshops and seminars and to make research visits to other institutions in the UK and overseas, and the Department provides funds to meet all requests of merit.

Activities which promote a thriving research culture in the Department and an environment conducive to research (see www.rae.cs.rhul.ac.uk with links to URLs mentioned below) include:

Some of the above such as Statistical Learning Theory were forecast in the 1996 submission; while Algorithmic Randomness, Predictive Complexity and Complexity Approximation Principle are completely new discoveries in this period.

All other 1996 plans have been fulfilled and published: 1) analysis of the structural risk minimization principle; 2) analysis of MDL and other inductive principles; 3) the Support Vector Machine algorithm; 4) study of causal models; 5) application of probability theory in finance; 6) neural network techniques for vision system design; 7) evolutionary algorithms for developing digital hardware. The links with AT&T have also been strengthened, and the NeuroCOLT collaboration has expanded (NeuroCOLT2).

Our current research activities can be broadly classified as Universal Learning, General Algorithms, and Specialized Algorithms, according to the universality of algorithms developed and architectures used (see www.clrc.rhul.ac.uk/research/activities.html).

Universal learning. The methods studied here are universal and optimal, but they are computable only in a weak sense, and the task is to find various computable approximations. The main technical tool in universal learning is Kolmogorov complexity, which formalizes the optimal performance of the learner in the game of coding. The classical notion of Kolmogorov complexity has been generalized, by Gammerman, Vovk and Watkins, to a wide class of other popular games, resulting in the notion of predictive complexity [Watkins3]. This has made it possible to generalise Rissanen's Minimum Description Length (MDL) and Wallace's Minimum Message Length (MML) principles to what we call the Complexity Approximation Principle [Gammerman3]. Our current research here is concerned with the study of the structure of predictive complexities for different games; a recent result by our PhD student Kalnichkan is the characterization of the class of games of prediction for which predictive complexity exists (prize awarded - see RA6).

Another activity in this area is the development of the algorithmic theory of randomness. A new set of inductive and transductive algorithms for estimating confidence of prediction, based on Kolmogorov theory of randomness, has been found by Gammerman, Vapnik and Vovk [Gammerman1,2]. This is a general method of constructing and adapting machine learning algorithms to assign meaningful levels of confidence to their prediction [Gammerman2, Saunders2]; the basic ideas have been filed by Gammerman and Vovk for two patents (PCT/GB99/03737 and GB0017740.2).

Our future plans include the development of the algorithmic theory of randomness and predictive complexity in the direction of a new game-theoretic approach to the foundations of probability proposed by Vovk and Shafer. In their new book "Probability and Finance" (to be published by Wiley, New York, in 2001) they develop that approach and apply it to limit theorems of probability, statistics and computational finance.

General algorithms. These algorithms can be used to solve a wide class of learning problems without fixing any particular architecture. One of the main technical tools is the Vapnik-Chervonenkis (VC) dimension, which has its origin in computational (or statistical) learning theory, often regarded as the core area of machine learning.

The most recent development in computational learning theory has been the introduction of several new learning algorithms. Among these the Support Vector Machine (Vapnik) is based on the "generalized portrait“ learning algorithm developed earlier (Vapnik and Chervonenkis) with the addition of kernel techniques. Vapnik's recent book "Statistical learning theory“ [Vapnik1] is the most authoritative exposition of the field by its originator. Also in this area Chervonenkis has worked on new methods for dependency reconstruction [Chervonenkis4] and properties of non-finite VC-dimension sets; and Shawe-Taylor has published a rigorous justification for the beneficial effect of large margins on the generalisation performance of learning systems [Shawe-Taylor1,2]. Our work on Support Vector Machine (SVM) has spawned a significant sub-area in the artificial intelligence community resulting in novel algorithms (e.g. large margin perceptron decision trees, ridge regression in dual variables) and further analyses (e.g. of boosting). Future work will focus on kernel-based learning methods. One of the challenges here is to develop specialist kernels for biological data, text and other applications together with data-dependent kernels.

The first general algorithm in the area of prediction with expert advice has been proposed by Vovk. This theory explores models with no stochastic assumptions. Instead, it is assumed that the learner has access to the predictions made by a pool of experts, and his goal is to predict not much worse than the best expert. Surprisingly, this goal can be attained in many situations, even where the pool of experts is infinite, e.g. in regression problems, as shown in [Vovk1,2]. The theory of prediction with expert advice has already been successfully applied in computational learning theory (boosting, as developed in AT&T), reinforcement learning and the theory of Kolmogorov/predictive complexity. Versions of this for several predictive games motivated by financial theory have been introduced and studied by Vovk and Watkins; it has turned out that those modifications generalize the standard coding game [Vovk3]. Other fruitful applications can be expected in future.

Future research is also planned in reinforcement learning, based on Watkins’ earlier Q-learning algorithm that is model-free and provably convergent. A new hierarchical approach is being investigated which avoids dynamic programming and may scale up to larger problems.

Specialized algorithms and architectures. There are many specialized algorithms which either solve a narrow class of problems (e.g. speech or hand-written digit recognition) or solve problems when restricted to some kind of architecture such as neural networks, Bayesian belief networks, decision trees, genetic algorithms.

Chervonenkis, a co-inventor of the modern theory of machine learning, has published new methods of reconstruction of conditional distributions with applications to random fields estimation in environmental science and geostatistics [Chervonenkis1].

Gammerman applied Bayesian Belief Networks to forensic science problems in a joint project with the Home Office [Gammerman4] (best paper award - see RA6).

Davies has developed pattern recognition algorithms in machine vision. He has designed novel sampling procedures typically attaining 100-fold speed-up of inspection algorithms [Davies3] and new filtering techniques based on an underlying theory of 2D filtering [Davies1]. This has been successfully applied to the identification of contaminants in grain and published in a monograph "Image processing for the food industry" (World Scientific, 2000).

Evolutionary algorithms have been developed for several signal processing applications [Flockton2,3] including a robust adaptive method of extracting direction of arrival information from noisy data [Flockton4]. A novel use, foreshadowed in the 1996 RAE, has been for analogue circuit design directly evaluated in hardware [Flockton1]. Future work will concentrate on evolutionary algorithms, and their links with bioinformatics.

Main applications of research in CLRC
In addition to those mentioned above, applications involving collaboration with industry and government include: fault diagnosis of electronic equipment (IFR Ltd - formerly Marconi Instruments); development of machine learning software (AT&T); pattern recognition algorithms and support vector machine software (DERA); text categorisation (Reuters and Xerox); learning methods for imputation problems (Office for National Statistics); diagnosis of ovarian cancer (St.Bartholomew's Hospital, London); prediction of renal failure (Glasgow Royal Infirmary); prediction of pollution in Lake Geneva (Lausanne University).

TOC - Theory of Computing

The Theory of Computing group performs research on mathematical modelling and algorithmic development. The group's activities include constraint satisfaction, combinatorial algorithms and complexity, complexity of learning theory and formal methods of analysis for security protocols and safety critical systems.

Members of the group are Professors Gutin and Shawe-Taylor, and Drs Cohen, Schneider, Scott, Treharne, and a distinguished visiting professor Leonid Levin (Boston University) – one of the originators of the theory of NP-completeness (together with S A Cook and R Karp).

The key achievements of the TOC group during the review period are:
* Delineation of polynomial solvable classes of important combinatorial problems in constraint satisfaction and directed graphs. These results are not only major theoretical advances, but provide important tools for the design of exact algorithms for these problems (Gutin and Cohen);
* The development of a general theory of data-dependent structural risk minimisation and analysis of the effect of large margins on the generalisation of thresholded classifiers (Shawe-Taylor).
* The introduction of important new modelling techniques, with proof tool support, for analysing and formally verifying security protocols (Schneider).

In the area of constraint satisfaction our work has resulted in the determination of properties of constraint sets that render constraint satisfaction problems tractable [Cohen1,3]. Efficient algorithms have been developed to detect when a particular set of constraints is "easy“, by providing a test for determining tractability (see also RA6). Furthermore we have developed techniques for generating novel tractable classes from existing known tractable classes [Cohen2,4]. This has led to the application of higher order constraints to the problem of frequency assignment for mobile telephony. Future work will extend the analysis of tractability of different constraint satisfaction problem settings, for example combining effects of underlying structure and constraint relations.

In the area of graph theory, a similar strategy has been adopted for the famous hamiltonian cycle problem (HCP). In [Gutin2], a long standing problem on the complexity of the HCP restricted to well-studied semicomplete multipartite digraphs is settled. The polynomial algorithm described is non-trivial and is based on several recently proved properties of semicomplete multipartite digraphs. [Gutin1] introduces, for the first time, a series of necessary conditions for a directed graph to be hamiltonian. These conditions can be incorporated in software systems which investigate properties of directed and undirected graphs. Other important results by Gutin can be found in the recently published monograph on digraphs (see RA6). The HCP on digraphs has numerous applications to the travelling salesman and other optimisation problems and future work in this area is planned, supported by a new EPSRC grant.

In the area of complexity of learning, the applicability of the expected complexity of algorithms relies on the quality of probabilistic model used. In [Shawe-Taylor3] a full ergodic model appropriate for the interactions of DNA sequences is used to analyse the expected performance of a novel string matching algorithm. This more accurate model of the problem domain suggests better algorithmic solutions. By deriving a suitable abstract model [Shawe-Taylor4] showed that a very wide range of invariant pattern recognition techniques fit within a uniform mathematical framework provided by a combination of representation theory and feedforward neural network architectures. [Shawe-Taylor1] defined a generalised theory of Structural Risk Minimisation (SRM) principle, known as data-dependent SRM. Future work will focus on the analysis of other data dependent measures.

Safety and Security. One of the key toolkits available for mathematical analysis of computer systems are so-called formal methods. Schneider has pioneered the inclusion of timing analysis within CSP. His recent book "Concurrent and Real-time Systems: the CSP approach“ [Schneider3] gives the first definitive account of Timed CSP, both in its own right and in terms of its relationship to CSP through his work on ‘timewise refinement’ [Schneider1]. Work on order types of termination ordering has been done [Scott1]; Scott has also started new work on language analysis and reverse compilation [Scott2,3,4], and future plans assume further expansion of this research.

Work on safety critical software has enabled two modelling techniques to be used simultaneously without compromising consistency. The state-based B-method can thus be combined with the event-based CSP, enabling control executives to be developed and verified for B systems in a formal and in a well-founded way. In [Treharne1,3] techniques are shown for ensuring the consistency of the two views.

A major success of the group in its mathematical modelling work has been the pioneering application of formal methods to the verification of security protocols as presented in [Schneider4], a key component of secure electronic commerce and defence communications. The rank function approach [Schneider2] allows a whole spectrum of security properties to be expressed, and a wide variety of security protocols to be verified against them. It has proved effective in uncovering both known and unknown weaknesses in standard protocols. This work provides an important link with the Information Security Group (entered under Mathematics UoA 22). Future work will involve tool support and the inclusion of timing to handle real-time protocols.

NETWORKS, MULTIMEDIA and DISTRIBUTED SYSTEMS (Group A): Jon Crowcroft, Saleem Bhatti, Hermann deMeer, Steve Hailes, Vicky Hardman, Peter Kirstein, Graham Knight, Dave Lewis, Steve Wilbur, plus other researchers and research students.

INTELLIGENT and ADAPTIVE SYSTEMS (Group D): John Campbell, Peter Bentley, Bernard Buxton, Chris Clack, Denise Gorse, Mark Herbster, Robin Hirsch, Sean Holden, Anthony Hunter, William Langdon, Philip Treleaven, John Washbrook, plus research assistants and p/g students.

VISION, IMAGING, AND VIRTUAL ENVIRONMENTS (VIVE) (Group E): Bernard Buxton, Danny Alexander, Simon Arridge, Yiorgos Chrysanthou, Mel Slater, Anthony Steed, plus other researchers and research students.

The AVRRC led by Kalawsky researches high performance visual computing, Virtual Reality and wearable/mobile computing. The AVRRC was opened by HRH Duke of Edinburgh in 1996 and incorporated the first Reality Centre to be established in a UK University. Research contracts from EPSRC, HEFCE, MOD, Lotteries Board, the Arts Council and industrial support from international companies such as Silicon Graphics Inc., SEOS Displays, PTC, MultiGen-Paradigm Inc. and BT have resulted in over £2.8m investment. Funding from EPSRC and the JISC Technology Applications Programme established the human factors evaluation framework underpinning the detailed human performance evaluation studies which have resulted in new VR related human performance evaluation tools. These are now in use by research laboratories and industry across the world. Successful transfer of human factors research knowledge to industry has led to further substantial industrial support through the provision of a Vision Dome, three-pipe Onyx computer and Immersive Wall to facilitate future research in multi-modal interaction in immersive environments. Recent MoD funded work has also led to a major contribution to the field of augmented reality as a means of providing online embedded training through the understanding of cognitive performance. The resulting research involved hundreds of carefully designed cognitive performance evaluation trials over a two-year period. Support from MoD and industry has enabled the AVRRC to extend its research into wearable/mobile computing. Research collaborations in the wearable computing area are already underway with several organisations including Motorola and BT. One of the first international conferences on augmented reality and wearable computing in the UK was held at Loughborough.

Edwards researches the support of ISO 9000/14000 Quality Assurance processes in the automotive industry (Jaguar). This research led to the development of 'Synergy', a Computer Supported Co-operative Working system for industry and commerce. Further research with web based client-server applications has resulted in important developments for the management of human capital in the emergent knowledge economy. The results of this research are important for international collaboration between businesses in the form of Global Strategic Alliances.

PÅRC, led by Schröder, is focused on theoretical problems behind computationally challenging tasks of practical interest. The research activities are concentrated on four major areas: 1) vision and visualisation; 2) signal processing; 3) future architectures of parallel computers; and 4) fundamental theoretical research. Schröder has produced efficient parallel systolic algorithms, e.g. line detection algorithms based on Hough transform, 2D and 3D image construction in computer tomography, transformation and compression algorithms in signal processing. He has worked on approximation algorithms and contributed significantly to research in reconfigurable meshes for load balancing and in image compression.

Bez researches the analysis of curve and surface algorithms for computer graphics and geometric modelling. Recent results have shown that the use of group theoretic methods provide comprehensive answers to fundamental questions concerning the properties of curve and surface algorithms used in CAGD. He was also engaged in a drape simulation project using finite element methods, in a garment design project and in image processing.

Edirisinghe researches in monocular and stereo image compression, video coding, shape coding, object recognition and image/video coding standards.

Sykora’s research addresses low crossing planar, straight line, book and two-layer graph drawing. He also undertakes research on static and dynamic properties of interconnection and communication networks based on advanced WDM technology.

Edmonds’ multidisciplinary work in the area of support for creative thought and creative cognition led to the establishment of C&CRS. In 1998 Edmonds led a Mission sent by the DTI to look at Art and Technology Intersection in Japan as part of the Technology Foresight activity. C&CRS was formed as a direct result of its findings. C&CRS is a leading centre in creative and technological research.

Funding for the C&CRS is from 15 research grants awarded by EPSRC, HEFCE, industry and the Arts Council for England. A JREI award for a laboratory for the study of Art and Technology worth nearly £0.5M was unique in the UK. EPSRC funded an innovative feasibility study (COSTART), involving an artists-in-residence programme, and followed it up by funding a full study beginning in 2001. An EPSRC Visiting Fellowship enabled Prof. Hewett of Drexel University USA to add to the COSTART research by bringing a psychology of HCI perspective. C&CRS provides a base for activities such as the international conference series Creativity & Cognition, now sponsored by ACM SIGCHI and supported by leading figures such as Minsky, Shneiderman and Fischer. The work with Japanese partners on the Strategic Knowledge and Concept Formation Workshops, held in Loughborough and then Iwate, is developing a new sub-discipline in that area. Digital artists have taken a prominent role in the research, and an award was made in 2000 to support five artists to work in C&CRS as part of the national Year of the Artist scheme.

Creativity in Design has formed a basis of much of the work and funded projects have been successfully completed with Lotus Engineering, British Aerospace, BIM, SAAB and many other companies. Much of this work has concentrated on two primary issues: support in early creative conceptual design and support for globally distributed design. HCI research is continuing through the System Engineering Data Representation and Exchange Standardisation (SEDRES) and SEDRES II European projects. These projects research interface standards to allow the complete set of tools in design of aircraft and spacecraft and their avionics systems to communicate, so that an integrated project support environment is available from commercial tools.

The 2 members of C&CRS have attracted £1.1m in grants and gifts, produced 16 journal papers, 21 conference papers 2 chapters in books and 5.5 PhD completions.

The group is carrying out major projects in computer-aided safe plant design in collaboration with the Department of Chemical Engineering (McCoy & Chung). The work on operating procedure synthesis using AI planning techniques received a certificate of recognition from the Expert System 99 conference (Chung). Some of the ideas generated from the accident database project are incorporated into the accident database developed and marketed by the Institution of Chemical Engineers. An IT company has been set up to exploit the automated hazard identification system.

Chung transferred to Gradients from Chemical Engineering to consolidate AI research. He was funded by the British Council, the Education Committee of China and the Japan Society for the Promotion of Science to collaborate with Dortmund University, Zhejiang University and Okayama University, respectively.

The interest was stimulated by the award of a large research grant of £400k from the EU (MEMO – Multimedia for Mobiles) to carry out research into Digital Audio Broadcasting (DAB). The MEMO project produced GSM up-links to DAB systems and the work played a key role in defining European standards for DAB applications. The group is a founder member of the European DAB forum that guides the development of DAB.

In 1998, a research contract of £89k from the DTI was awarded to develop the world’s first commercial DAB portable radio receiver with Siemens and the UK radio manufacturer Roberts Radio. This was supported by a further grant of £46k in 1999. The research now centres on MP3 transmissions in DAB at very low bit rates. The success of IMPACT led to a JREI award (Alty and Knott) from EPSRC in 1999 of £180k (with matching funds from BT, BAE SYSTEMS and Nortel) to provide a DAB transmitter and a DAB laboratory. The laboratory, officially opened in January 2001, examines WAP, Bluetooth and DAB. There is substantial interest from the commercial DAB community in this facility enabling research in new applications.

Process Control research grew out of the PROMISE project. Alty won a research grant from the EU to develop an agent based adaptive interface for process control applications in Italy and Spain (£100k), with Alcatel (France), Softeco and Elsag (Italy) and Iberdrola (Spain). Yang won an EPSRC grant (£70k) to support research into remote process control.

IMPACT was chosen by the German Government to lead the interface design of a (DM40million) Chemical Distance Learning project with 15 German Universities including Berlin, Dresden, Tübingen and München (Alty). This work is funded for 4 years at £220k.

Phillips' research focus is on Network Performance Measurement, networking mobile devices in an ad-hoc manner; and improving internet use by whole communities. Network performance measurement includes techniques for measurement and display of current performance through collaboration with Electronic and Electrical Engineering at Loughborough. BT funds the research that measures BT's SMDS service).

RJ Dawson researches project management methods used in companies (Rolls-Royce Naval Marine, Rolls-Royce Aerospace, The Danwood Group, NSB Retail Systems, Gehe). He concentrates on empirical research with project management data associated with information systems and software development, particularly related to cost, examining the requirements gathering and software development processes and their relationship to e-commerce. This work has resulted in 3 industrial grants. The work on whole life costing (RJ Dawson) resulted in a prize for a paper and substantial savings for the organisations (Rolls-Royce and The Danwood Group).

Work on the management of change and the effective use of technology (RJ Dawson & Newman) has led to publications on educating engineers to design and produce effective software in "real world" environments. This work has attracted industrial sponsorship, including student prizes, and has resulted in Loughborough students winning prizes in industrially sponsored, national (IBM) and international (NASA) competitions.

The generation of integrated, robust, expandable systems (covering distribution and web based delivery) (Newman), built on the technical successes achieved in the GENIE and POINTERS distributed information management projects. Many of the ideas are incorporated in a book produced by the IFIP WG2.7 (Design Principles for Interactive Software). The development of tools to support the effective use of components has been supported by a BT allocated CASE award.

Application of AI methods to hydrological modelling of river flow (CW Dawson) has been supported by the Environment Agency for an ecological study of the Test and Itchen rivers in Hampshire, and by the University of Yichang (China) for collaborative work on the River Yangtze. CW Dawson is a co-founder of UK Hydroinformatics Group. Further environmental work includes development of Statistical Downscaling Modelling Software for the Canadian Climate Impacts Scenarios Group. CW Dawson is also researching risk management with Experian and has published papers on flexible methods in software project management with RJ Dawson.

Cooke & Hussak are primarily concerned with using accessible mathematical notations to define the requirements and specifications of systems. These can be used to reason about correctly implemented systems and/or used to derive necessarily correct system designs. Specific interests include logics for requirements engineering of concurrent systems (Hussak), the nature of refinement from requirements to a system specification, and the use of temporal logic and quantifications to produce abstract specifications which are devoid of implementation bias (Cooke).

The research groups are Dependability, Distributed Systems, Parallelism, Theory, and VLSI Design; there is strong co-operation and synergy between the five groups. The department’s researchers are active across the spectrum from theory to implementation. The groups share a common commitment to research that will affect the creation of computer systems (a few examples on which we are actively involved include distributed transaction systems, the putative Electronic Health Record that depends crucially on acceptance by society, and VLSI systems built with asynchronous logic).

The overlaps between the areas provide a crucial advantage: some researchers contribute to two or three groups and the stimulus of testing new ideas on challenges posed by applications is strong. For example, formal methods research is pursued in the Theory Group and problems are often derived from –and solutions or techniques evaluated in– Dependability Group activities to mutual benefit. Petri-nets, object-oriented methods and transaction models are among other key topics that impinge on multiple groups.

The systems view results in an emphasis on applicable research; applicability is obvious in the case of the Distributed Systems research that has created widely-used software for distributed transaction systems and given rise to a spin-off company: Arjuna Solutions Ltd. The VLSI Group provides tools for asynchronous system design to groups in other universities and industry. The Theory Group firmly subscribes to "Theory in the service of systems development" and –alongside its role in international research– collaborates with all of the other research groups in the Department.