Logo der Universität Wien

Efficient Algorithms for Computer Aided Verification

Table of content
Grafik

Further details
Type
R&D projects, public funding
Duration
2016 - 2019
Executive
Research Group Theory and Applications of Algorithms
Links
http://thekla.taa.univie.ac.at/efalcoaid/
Abstract

This project builds upon our successful project called Modern Graph Algorithmic Techniques in Computer Aided Verification (2011-2015). In the past project we developed new techniques for specific basic problems arising in verification, namely for maximal end-component decomposition and Büchi games and successfully reduced their running time. In this project we will study algorithmic approaches for more general problems in verification. We will explore four different aspects in this project, two of them are approaches for more efficient algorithms, the third is exploring lower bounds for problems in verification, under the assumption that some other problems are algorithmically hard, and the fourth aspect is an experimental evaluation of our new algorithms on real-world examples. The new aspects of our project are (A) the new algorithmic techniques that we will employ, namely, a hierarchical graph decomposition technique, interior point methods and spectral graph theoretic approaches, (B) that in parallel to the algorithms development we will prove lower bounds for the running time of these problems, which will guide us in the development of the algorithms, and (C) that we will implement and experimentally evaluate our new algorithms in the PRISM toolbox on case studies from the PRISM benchmarks and on graphs generated by the analysis of various scheduling algorithms on task sets from a real-time systems benchmark.

Grafik Top
Associates
  • Krishnendu Chatterjee of IST
Grafik Top
Universität Wien | Universitätsring 1 | 1010 Wien | T +43-1-4277-0