Extending the scope of modular analysis for the validation of large systems. The increasing complexity of computer systems has severe implications for verification and validation, especially for critical systems (e.g. medical supervision, avionics mission systems). The standard approach is to build a formal model of the system and automatically analyse its behaviour. Such models can be captured in a modular, high-level description, but the number of states is usually so large as to preclude an ....Extending the scope of modular analysis for the validation of large systems. The increasing complexity of computer systems has severe implications for verification and validation, especially for critical systems (e.g. medical supervision, avionics mission systems). The standard approach is to build a formal model of the system and automatically analyse its behaviour. Such models can be captured in a modular, high-level description, but the number of states is usually so large as to preclude analysis. The modular analysis proposed in this project matches the analysis technique to the structure of the model. Preliminary results are promising and motivate the extension of the technique to a larger class of modular descriptions.Read moreRead less
Algorithmics for Interactive 2.5D Graph Drawing. Technological advances have provided a data deluge over the past few years, and consequently have led to many large and complex network models in many domains. This includes terrorrist networks and biological networks, software engineering structures, and webgraphs. Visualisation is an effective tool in helping humans to understand such networks. This project aims to provide a new direction in network visualisation, using 2.5 dimensions. The algor ....Algorithmics for Interactive 2.5D Graph Drawing. Technological advances have provided a data deluge over the past few years, and consequently have led to many large and complex network models in many domains. This includes terrorrist networks and biological networks, software engineering structures, and webgraphs. Visualisation is an effective tool in helping humans to understand such networks. This project aims to provide a new direction in network visualisation, using 2.5 dimensions. The algorithms developed in the project will help security analysts to detect abnormal behavious such as money laundering, help biologists understand protein-protein interaction networks, and help engineers to understand large software systems.Read moreRead less
Efficient Pre-Processing of Hard Problems: New Approaches, Basic Theory and Applications. Computers store even larger amounts of data about all aspects of human and industrial activity. However, they have not become significantly better at solving common problems in optimization and search. Traditional complexity theory indicates many of these problems require algorithms that are very unlikely to exist. The Parameterized Complexity approach allows us to obtain very efficient algorithms for a lar ....Efficient Pre-Processing of Hard Problems: New Approaches, Basic Theory and Applications. Computers store even larger amounts of data about all aspects of human and industrial activity. However, they have not become significantly better at solving common problems in optimization and search. Traditional complexity theory indicates many of these problems require algorithms that are very unlikely to exist. The Parameterized Complexity approach allows us to obtain very efficient algorithms for a large variety of problems, but the machinery required was diverse and complicated. This research will organize the machinery into a new approach that systematically finds good algorithms by applying simplifications around a parameter of the domain of the problem. As a result, efficient algorithms are obtained for many diverse areas.Read moreRead less
Multivariate Algorithmics: Meeting the Challenge of Real World computational complexity. This Project will result in better methods for designing the algorithms that all computer applications depend on. Algorithms are the instruction sets that tell computers how to process information. Some information processing tasks are intrinsically difficult, even for computers working at enormous speeds. This Project will deliver new mathematical approaches to overcome these difficulties. More efficient al ....Multivariate Algorithmics: Meeting the Challenge of Real World computational complexity. This Project will result in better methods for designing the algorithms that all computer applications depend on. Algorithms are the instruction sets that tell computers how to process information. Some information processing tasks are intrinsically difficult, even for computers working at enormous speeds. This Project will deliver new mathematical approaches to overcome these difficulties. More efficient algorithmic approaches for difficult problems enable advances in all areas of computer applications such as medical diagnosis and health prediction, national security, communications efficiency, industrial productivity and all fields of science and engineering.Read moreRead less