Parameterized and algebro-geometric advances in static program analysis

By: Goharshady, Amir
Material type: TextTextPublisher: IST Austria 2021Online resources: Click here to access online
Contents:
Abstract
Dedication
Acknowledgments
About the Author
List of Publications
List of Abbreviations
1 Introduction
2 Preliminaries
3 Faster Algorithms for Data-Flow Analysis
4 Faster Algorithms for Quantitative Analysis of MCs and MDPs
5 Faster Algorithms for Data Packing
6 Invariant Generation for Polynomial Programs
7 Reachability Analysis for Polynomial Programs
8 Termination Analysis for Polynomial Programs
References
Summary: In this thesis, we consider several of the most classical and fundamental problems in static analysis and formal verification, including invariant generation, reachability analysis, termination analysis of probabilistic programs, data-flow analysis, quantitative analysis of Markov chains and Markov decision processes, and the problem of data packing in cache management. We use techniques from parameterized complexity theory, polyhedral geometry, and real algebraic geometry to significantly improve the state-of-the-art, in terms of both scalability and completeness guarantees, for the mentioned problems. In some cases, our results are the first theoretical improvements for the respective problems in two or three decades.
List(s) this item appears in: IST Austria Thesis | New arrivals January 2022
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Call number Status Date due Barcode Item holds
Book Book Library
Available AT-ISTA#002459
Total holds: 0

Thesis

Abstract

Dedication

Acknowledgments

About the Author

List of Publications

List of Abbreviations

1 Introduction

2 Preliminaries

3 Faster Algorithms for Data-Flow Analysis

4 Faster Algorithms for Quantitative Analysis of MCs and MDPs

5 Faster Algorithms for Data Packing

6 Invariant Generation for Polynomial Programs

7 Reachability Analysis for Polynomial Programs

8 Termination Analysis for Polynomial Programs

References

In this thesis, we consider several of the most classical and fundamental problems in static analysis and formal verification, including invariant generation, reachability analysis, termination analysis of probabilistic programs, data-flow analysis, quantitative analysis of Markov chains and Markov decision processes, and the problem of data packing in cache management. We use techniques from parameterized complexity theory, polyhedral geometry, and real algebraic geometry to significantly improve the state-of-the-art, in terms of both scalability and completeness guarantees, for the mentioned problems. In some cases, our results are the first theoretical improvements for the respective problems in two or three decades.

There are no comments for this item.

to post a comment.

Powered by Koha