Research Programme 2007-2012

In 2006, IPA evaluated its research spearheads which were defined in 2001. For the next six years five “focus areas” were chosen, areas within the scope of IPA where we expect important developments in the field in the near future. These areas are: Beyond Turing, algorithms & models for the life sciences, hybrid systems, model-driven software engineering, and software analysis.

Beyond Turing

The future challenges of computing require new concepts that are no longer adequately modeled by the classical Turing machine paradigm. Systems become increasingly interactive with their environment and learn and adapt, consist increasingly of autonomous and even mobile components that self-configure and operate by own mechanisms, control rather than compute and are always on, and they must deal with ever more complex contexts and masses of data. Moreover,the notion of computing is no longer exclusively used for artificial gadgets only. Biologists frequently speak of of living cells as complex information processing systems and even `swarms’ of living organisms are sometimes said to have a collective intelligence akin to computational systems. Also in other sciences, processes are increasingly understood in novel computational terms.

The new forms of `non-classical’ computing that manifest themselves lead us to explore the limits of what the Turing machine models allows us to do and often lead us beyond it. Even in traditional applications, the existing theory is often not sufficient. The reason is that modern computing systems, if they aren’t already following the new paradigms, do not just have an unbounded uniform memory but in fact a whole memory hierarchy with non-uniform access costs. To obtain the best performance, the hierarchical nature of the memory should be taken into account in both the design and the analysis of algorithms, which is normally not done in traditional theory. New computational principles as in quantum computation may revolutionize computers in the future and require entirely new approaches to efficient computation and complexity theory as well.

The paradigm shift away from classical Turing machine-based computational to newer paradigms corresponds to a shift in thinking about computation. The future models are nonuniform, learn and adapt, and are operating on the basis of algorithmic mechanisms rather than deterministic control. The behaviour is emergent from their many parts instead of from a central machine. The underlying network structures fluctuate by `link-free’ connections based on proximity or negotiation. The principles of these adaptive structures and algorithms are much less understood than those of (dynamic) discrete algorithms and use new ideas from many sources, ranging from the theory of evolving systems to notions from economic games and market-oriented programming. The many developments in novel processing structures and principles and new complexity measures like energy, transcend the current theories of computation.

Connecting to the theme of the “Computer of the Future” and “The Data Explosion” of the National Research Agenda ICT 2005-2010 (NWO/IPN) and to the challenges of several of the “ICT Technology Pillars” of the FP7 theme “Information and Communication Technologies”, IPA’s focus area “Beyond Turing” aims to further the understanding of the foundations and computational abilities of non-classical computing. The priority area builds on the strengths within IPA in the areas of I/O-efficient algorithms, constraint programming, sensor-based computing systems, evolving systems, and quantum computing.The potential of the new computational paradigms from both a foundational c.q complexity-theoretic viewpoint as well as from an application-oriented viewpoint in solving hard problems in a novel way, will be explored. The priority area will be the breeding ground for the novel developments that underly the novel computational systems of the future.

Algorithms & models for life sciences

Nowadays computer science plays an essential role in many aspects of the life sciences: DNA sequencing, drug design, medical imaging, etc. all crucially depend on tools and techniques developed within computer science. We believe that this trend will only become stronger and that computer science will play a pivotal role in the further development of the life sciences. Indeed, understanding how biological systems work is for a large part a question of understanding how information is being processed by the system—and information processing is exactly what computer science is all about.

The focus area “Algorithms & models for life sciences” aims at applying the strengths of IPA in Algorithms and Complexity and in Formal Methods to contribute to this exciting area: we wish to apply algorithmic theory and formal models to solve fundamental and practical problems posed by or inspired from the life sciences, in collaboration with biologists and others researchers from the life sciences. In particular, we are interested in applying these techniques to increase the understanding of biological processes. This involves various aspects:

Algorithms for the management and analysis of biological data. In bioinformatics massive amounts of data are generated. To understand the underlying biological processes, these data have to be analyzed to extract patterns and to make the step from data to model in order to predict biological structure and function. For this techniques from data mining are essential. In addition, the efficient processing of such massive amounts of data poses many challenging algorithmic questions.

Construction of formal models of biological entities and phenomena. One of the great challenges in the study of biological systems is to understand them to such an extent that predictions can be made as to how they will react under certain circumstances. To this end, one has to model the system under study (with the help of the analysis of the available experimental data). Formal methods, for example from concurrency theory, may provide a good way of modeling and analyzing biological systems–for instance the pi-calculus could be used for compositional and modular modeling of protein-level interactions. Formally modeling biological systems also opens possibilities for verification of properties.

Simulation of biological processes. Systems Biology is trying to reconstruct networks of biochemical interactions (metabolic networks, extra and intracellular networks, networks of genetic regulation). In Computational Biology the step is made from model to simulation: the computational modeling, the prediction of the dynamics, and testing underlying model assumptions. For the modeling it is essential to have insight in the interaction between local and global phenomena and the different time scales they use. This is carried out with experimental and simulated data. To do the simulations efficiently, good algorithmic techniques (e.g. in parallel processing) are needed.

Hybrid systems

Hybrid systems are dynamical systems with both continuous and discrete dynamics. Such systems have become increasingly important in applications. Research on hybrid systems has gained a considerable momentum during the last two decades, both from mathematical systems theory and from computer science. Examples of hybrid systems are continuous systems controlled by digital controllers, systems operating in different modes, and embedded systems where continuous and discrete components interact. Application areas include professional systems (medical equipment, process control, VLSI lithography), high-volume systems (consumer electronics, automotive systems), and sensor networking systems (monitoring and control, personal health care, maintenance systems). Generally, hybrid systems are ubiquitous in modern technological systems and should function in a dependable and safe way. Therefore the societal importance of this research can hardly be overestimated. In addition, the fact that hybrid systems span the communities of computer science, and systems and control theory, provides a profound scientific challenge. The many and multifaceted technical topics can be naturally organized into three areas:

Modeling and Simulation. Here the main quest is to create modeling formalisms that are applicable on an industrial scale. Such formalisms should have the flexibility to be turned into domain dependent methods; compositionality is an important issue. Furthermore, clear relations and mappings should be established with other models like functional, timed, and stochastic models. Both mappings and formalisms should be supported by modeling and simulation tools.

Analysis. The desired dependability of hybrid systems asks for mature analysis techniques that can assess key properties like correctness, stability, and robustness. A central topic in verification is the support of model checking by abstraction techniques that are parameterized by both model features and property domains.

Control Synthesis and verification of controllers become major technical challenges in the presence of discontinuities, distribution, and the interplay between discrete and continuous aspects. Hybrid controllers will have to address various (and often simultaneous) control objectives like functionality, stability, robustness, and optimality. Game theory is expected to be a promising paradigm in this field.

Model-driven software engineering

In Model-Driven Software Engineering formal models play a key role in the software development process. Formal models are being used to specify (parts of) the (desired) functionality, structure and/or behavior of a system. A specification is said to be formal when it is based on a, possibly graphical, language with a well-defined syntax and semantics.

Model-Driven Software Architectures (MDA’s) are getting more and more popular both in industrial and scientific communities.Traditionally, modeling techniques have successfully been used to model Information Systems using specification techniques like NIAM, ERM, and FOM. Nowadays model driven approaches are being used for many other application domains. The model driven approach is among others advocated by the international Object Management Group. They regard MDA’s as the way to develop long-living architectures for distributed component based systems. The specification of the functionality of a system in a formal model is ideally done in a platform independent way and model mappings are used to turn these specification into a platform specific model which on its turn is used for the generation of the application for that platform. Modeling in the OMG style is often done using OMG standards such as UML, XML, XMI, MOF, and CWM.

However, the computer science community offers many ways to model the functionality and properties of systems, each having its own advantages and limitations. For instance, any type system can be regarded as a modeling language that can be used to check or infer certain properties of a particular specification or program. With modern software techniques like generic programming one can generate complete applications using types (models) as input.

There are many open questions:

Modeling Languages. There are many problem domains. What are suitable formalisms for modeling and for which kinds of domains are they best suited? What kind of modeling language is best suited to define the different aspects of a system like its desired functionality, its structure, and/or its behavior?

Generating Systems From Models. How can we describe properties in a way that does not depend on a certain technology, yet use the same description to generate concrete applications?

Quality. How do we determine the quality of the models and the associated software? What kind of properties can we derive from a model? Does the software behave as specified in the model, how can we automatically test the conformance of a system and its model? How can we use the model to formally prove (e.g. by model checking) properties of the system?

Software Evolution. The world keeps on changing, therefore models will have to be adjusted as well. How can we realize changes incrementally in the models and the associated software with as little work as possible? How can we assure that old and new systems derived from the models keep working together in a proper way?

Software analysis

Quality software can be characterized in many ways. Of course, software should first and foremost satisfy its functional requirements, but there are many non-functional quality aspects as well. For instance, availability, modifiability, performance, security, testability and usability are also important qualities of software. For each of these it is desirable to have analysis and measurement instruments to determine to what extent a software system satisfies them. Analysis starts with extracting relevant facts from the source code. This is a detailed step that is largely dependent on the programming languages that have been used during the construction of the source code and of the forms of analysis that are required. It is not uncommon that several languages have been used and in those cases cross-language fact extraction and analysis are necessary. Language-parametric techniques for fact extraction are highly desirable but mostly still lacking.

After fact extraction, direct analysis of these facts can be done for certain applications such as call graph analysis, dead code removal, analysis of information flows and the like. For other applications a more abstract model has to be constructed that describes certain domain-specific properties of the system that is implemented by the source code. In this area fall, for instance, protocol analysis, dead lock analysis and determining certain security properties. It is crucial to guarantee that the abstract model faithfully represents relevant properties of the original source code. Achieving scalability and usability of the involved validation techniques is a major challenge.

A final aspect to consider is the way in which the results of software analysis are presented. It is important to develop new methods for information visualization that will increase the usability of software analysis.

Software analysis is essential for getting insight in the quality aspects of software. This is true for old software that has evolved over the years, but also for new software that has to be accepted from a third party. Software analysis will therefore become more and more important as the outsourcing of software becomes more popular as well. It is also of particular importance in the area of open source software, where there is typically not a single producer that can be held responsible, but (by the very nature of the development process) the source code itself is available, providing extensive opportunities for analysis. Software analysis may reveal certain defects in software that have to be repaired. It is therefore also a prerequisite for refactoring, transformation, renovation and other forms of software improvement. The seamless integration of software analysis with software transformation is a rich area for research.

We feel that this making progress in this area is both urgent and timely for several reasons: It is urgent because the ever increasing dependence of our society on software systems and the high-profile failures of some of those systems makes it mandatory to invest in techniques that can measure various quality attributes of software in order to prevent such failures. It is timely because progress in source-code analysis techniques enables the extraction of facts for more advanced analysis and validation than is currently done, and because improvements of validation techniques by way of algorithmic enhancements or concurrent execution enable the analysis of increasingly large problems.