IPA has three major fields of research: Algorithms and Complexity, Formal Methods and Software Technology & Engineering. A comprehensive description of these fields was first given in the "KNAW-erkenningsaanvraag". During 1998, these descriptions were revised and rearranged, making them more suitable as a guideline for research cooperation. In 2001, at the end of the second period of recognition by the KNAW, the descriptions were updated. As part of this update, the area Software Technology was renamed into Software Technology & Engineering because this better reflects the wider range of research topics addressed by the various groups in IPA.
Algorithms are the building blocks of all software systems, and the performance of a software system is often directly related to the choice of the underlying algorithms. It is not surprising, therefore, that algorithms research forms one of the core areas within computer science.It is based on a solid foundation that gives methods for the design of algorithms, for the analysis of their efficiency (so that a choice can be made between different algorithmic solutions to the same problem), and for classifying problems according to their inherent computational complexity. The goal of algorithms research is on the one hand to provide efficient solutions to specific computational problems, and on the other hand to develop general techniques to design and analyze algorithms and data structures.
There are many application areas that pose challenging algorithmic problems: logistics (planning and scheduling), network design, biology, computer-aided design and manufacturing, geographic information systems, and so on. In several of these applications,it is not possible to compute exact solutions to the problems at hand with provably efficient algorithms, for example because the size of the data sets is prohibitive, or because the problem is NP-hard. In such cases one has to settle for approximation algorithms, or maybe for heuristics that may not have a probable performance guarantees but that perform well in practice. In these (and other) situations, experimentation also plays an increasingly important role. Indeed, over the past decade or so, algorithms research has developed from a mostly theoretical research area to an area where theory and experimentation often go hand in hand. For example, the European Symposium on Algorithms (ESA) now features two tracks, one on ``Design and Analysis'' and one on ``Engineering and Applications", and there are several workshops dedicated purely to algorithm engineering. Moreover, there are several algorithms libraries to facilitate this research.
The work within IPA reflects these different aspects and the variety of algorithms research. Algorithms research in IPA can roughly be divided into two closely related and partially overlapping areas: more traditional algorithmics where the focus is on computational complexity, and algorithmic research inspired by or based on nature.
Complexity-oriented algorithmics. Part of the algorithms research within IPA concerns established areas such as graph algorithms and computational geometry. A common theme of much of the IPA research in these areas is to develop algorithms that are provably efficient for certain well-defined classes of problem instances. For example, in graph algorithms there are many problems that are hard for general graphs, but that can be solved efficiently on graphs of bounded treewidth. Hence, algorithms for graphs of bounded treewidth and, more generally, parametrized complexity is currently an active topic of research within IPA. On a similar note, spatial data in practical applications often have favorable properties that one can formalize and exploit to obtain faster solutions. This leads to the study of so-called realistic input models for computational geometry, another topic being studied within IPA. Also combinatorial optimization, in particular for planning and scheduling, is an important topic within IPA. This work is complemented with fundamental research on complexity issues, for example on Kolmogorov complexity.
Nature-inspired computing. A significant part of the algorithms research in IPA uses techniques that are inspired by or based on natural sciences, in particular physics or biology. Sometimes these techniques are implemented on traditional (sequential or parallel) machines---this is for instance the case when neural networks or evolutionary algorithms are applied. In other cases, even the hardware itself is inspired by nature---this happens in our research on evolutionary DNA computing and quantum computing. Some of the research in IPA uses computer simulations (sometimes involving neural networks or evolutionary algorithms) to study biological processes, often with medical applications. Research is furthermore conducted on projects related to using molecular biology to implement evolutionary algorithms (Evolutionary DNA Computing), using data mining and optimization methods for drug design. Algorithms for agent technology are also studied, with applications ranging from e-commerce to planning and scheduling. (The latter applications provide interesting links with the combinatorial-optimization research done within IPA.) Finally, there is a large and active group working on various aspects of quantum computing including quantum algorithmics and quantum information theory.
IPA groups involved in Algorithms and Complexity are:
This area concerns the use of the formal reasoning in the area of verification and testing of software (and hardware) systems, and the implementation of these formal reasoning systems in software tools.
Foundational research in this area is concerned with axiomatic and algebraic approaches, most often rendered as deductive systems. A paradigm case is that of the lambda-calculus with its various typed extentions, as well as the general framework of rewriting (including term graph rewriting). Also the family of pi-calculi for mobile systems in concurrency are situated here. Often the framework of the deductive systems in this section is equational, as is the case in the axiom systems for process algebra; but a non-equational style of established importance is found in the SOS paradigm. The equational style is in many instances fruitfully employed to yield executable calculi corresponding to the axiomatizations based on deductions. The equational framework has turned out to be flexible enough to facilitate many extensions in a smooth way, in particular the inclusion of non-functional aspects such as time, probability, mobility etc.
We distinguish three types of formal reasoning:
Logical reasoning. This concerns the implementation and use of proof checkers and theorem provers such as PVS, COQ, HOL and others. Steadily, the power of these systems and their user-friendliness is improved. They are applied to mathematical proofs, and to correctness proofs of communication protocols and distributed algorithms.
Algebraic reasoning. This concerns research on the algebraic verification of systems and its support by software tools, such as the Chi, mCRL2 and LOTOS toolkits. Industrial contacts in manufacturing and embedded systems are fostered in institutions like the Laboratory for Quality Software (LaQuSo) at the TU/e and RU, and the Embedded Systems Institute (ESI) in Eindhoven.
Operational reasoning. Many industries (such as AT &T, Intel) nowadays use model checkers to verify formal models of their systems. Much research in this area concerns dealing with state explosion, by means of parallel verification algorithms, abstraction, partial order reduction, and symbolic methods. Often, formal verification is only applied to well-chosen key elements of a system, or instead of full verification, model-based testing is used. An important new development is software model checking, where not a model of the software is verified, but the software itself.
Classic application areas of formal methods are embedded, distributed, hybrid and safety-critical systems. System properties that are verified mostly concern functional behavior, timing requirements, and probabilistic aspects. An important new application area is security. Formal reasoning is used in the analysis of security protocols, software security, and smartcards. Notable security issues (e.g. in on-line banking) that play an important role are confidentiality (protected, private data or communications should not be visible to unauthorized parties), integrity (private data should be protected against modification by unauthorized parties), availability (data and services should be protected against Denial of Service attacks, so that they are accessible by authorized parties), authenticity (parties involved in communication should have certainty about each other's identity), and non-repudiation (parties involved in communication should not be able to deny the actions that they performed).
We envision that a key application area for the near future will be life sciences (e.g.\ formally specifying and analyzing the computational aspects of a living cell).
IPA groups involved in Formal Methods include:
With the increasing size of software systems it becomes mandatory to control the construction process. Increased control is desirable in order to satisfy requirements regarding delivery time, costs, reliability, safety, maintainability, and the like. However, the requirements for software systems are in a continuous flux and it is at the same time essential that the construction process has an evolutionary character.
We distinguish three strands of research within IPA:
Component and coordination architectures. It is a good idea to base the construction process on a flexible architecture and to build or buy the parts of a system as separate components. Where possible, components are automatically generated. Prototyping, simulation and animation, can give early insights in the behavior of the system under construction. Version and configuration management support the (possibly distributed) construction process. Methods and tools for testing and performance analysis enable the analysis of the functional behavior and the efficiency of the system.
This approach is compatible with current trends in research to remove the strict boundaries between operating systems, data bases and networks in order to promote flexibility and reuse. This trend towards evolving dynamic systems results in collections of stand-alone components with clearly described functionality and small interfaces (objects in the sense of object- oriented programming) that can be combined into larger systems in a simple and flexible way. Using this approach, one can first create a simple prototype of a system and gradually replace simple components by more sophisticated ones. This topic is related to Service-oriented Architectures (SOA) and Service-oriented Computing (SoC).
Compilers and program generation. The classical example of the automatic generation of executable programs is compiler construction: starting with a formal language definition (consisting of a lexical and context-free syntax, context conditions, and dynamic semantics) and a formal definition of the architecture of the target machine it is possible to generate optimizing compilers. More and more advanced analysis of the formal descriptions is applied (using, for instance, abstract interpretation) to achieve efficient implementations. The ultimate goal is to generate from formal descriptions executable programs that are as fast as handwritten ones.
A first illustration of program generation is generating support for so-called domain-specific languages. This concerns languages in a broad variety of application areas (for instance, user-interfaces, definition of financial products, description of production processes or safety requirements) that already contain domain-specific concepts and therefore simplify the development of new applications in that domain. This is strongly related with various approaches to Model-driven Architecture (MDA). This research will typically be carried out with partners from the software industry, major financial institutions, and government.
Maintenance and renovation. Directly related to constructing new software systems is the maintenance and renovation of old systems. Given the tremendous economic importance of this topic, many aspects of software analysis and software transformation need to be studied in the context of software renovation. Typical topics are program and system understanding, cluster and concept analysis, object and aspect identification, software metrics, grammarware engineering, information extraction, information visualization, automatic transformation, and renovation factories.
The driving force behind software renovation is the strong need to maintain and renovate parts of the software volcano. This implies that software renovation research has to be carried out in close cooperation with industrial partners that can contribute problems that have to be solved. Typical partners come from the software industry, embedded systems, manufacturing, financial institutions and government.
Fortunately, we can be confident that progress in areas like compiler and programming language technology and in formal method, will continue to offer the relevant tools. At the same time, the analysis of legacy systems provides the empirical foundation for programming language research. It uncovers the effects, both positive and negative, of years of intensive use of a programming language in the real world.
Software renovation research also reveals new challenging problems. Techniques for analysis or code generation that were satisfactory from the perspective of a traditional compiler may no longer be satisfactory from the perspective of interactive program understanding. The gigantic scale of renovation projects presents implementation problems (and opportunities) that may inspire research for many years to come.
The biggest challenge is to try to bridge the gap between research aimed at building new software and research aimed at maintaining or renovating old software. It is likely that an integrated approach to both is the best way to proceed. This implies introducing maintenance and renovation considerations much earlier in the software construction process than is usual today. This also implies designing new languages and programming environments that are more amenable to maintenance and renovation.
IPA groups involved in Software Technology & Engineering include: