Statistical and logical methods for property checking

P. Daca, Statistical and Logical Methods for Property Checking, IST Austria, 2017.

Download
OA 1.03 MB

Thesis | Published | English
Department
Series Title
IST Austria Thesis
Abstract
This dissertation concerns the automatic verification of probabilistic systems and programs with arrays by statistical and logical methods. Although statistical and logical methods are different in nature, we show that they can be successfully combined for system analysis. In the first part of the dissertation we present a new statistical algorithm for the verification of probabilistic systems with respect to unbounded properties, including linear temporal logic. Our algorithm often performs faster than the previous approaches, and at the same time requires less information about the system. In addition, our method can be generalized to unbounded quantitative properties such as mean-payoff bounds. In the second part, we introduce two techniques for comparing probabilistic systems. Probabilistic systems are typically compared using the notion of equivalence, which requires the systems to have the equal probability of all behaviors. However, this notion is often too strict, since probabilities are typically only empirically estimated, and any imprecision may break the relation between processes. On the one hand, we propose to replace the Boolean notion of equivalence by a quantitative distance of similarity. For this purpose, we introduce a statistical framework for estimating distances between Markov chains based on their simulation runs, and we investigate which distances can be approximated in our framework. On the other hand, we propose to compare systems with respect to a new qualitative logic, which expresses that behaviors occur with probability one or a positive probability. This qualitative analysis is robust with respect to modeling errors and applicable to many domains. In the last part, we present a new quantifier-free logic for integer arrays, which allows us to express counting. Counting properties are prevalent in array-manipulating programs, however they cannot be expressed in the quantified fragments of the theory of arrays. We present a decision procedure for our logic, and provide several complexity results.
Publishing Year
Date Published
2017-01-02
Acknowledgement
First of all, I want to thank my advisor, prof. Thomas A. Henzinger, for his guidance during my PhD program. I am grateful for the freedom I was given to pursue my research interests, and his continuous support. Working with prof. Henzinger was a truly inspiring experience and taught me what it means to be a scientist. I want to express my gratitude to my collaborators: Nikola Beneš, Krishnendu Chatterjee, Martin Chmelík, Ashutosh Gupta, Willibald Krenn, Jan Kˇretínský, Dejan Nickovic, Andrey Kupriyanov, and Tatjana Petrov. I have learned a great deal from my collaborators, and without their help this thesis would not be possible. In addition, I want to thank the members of my thesis committee: Dirk Beyer, Dejan Nickovic, and Georg Weissenbacher for their advice and reviewing this dissertation. I would especially like to acknowledge the late Helmut Veith, who was a member of my committee. I will remember Helmut for his kindness, enthusiasm, and wit, as well as for being an inspiring scientist. Finally, I would like to thank my colleagues for making my stay at IST such a pleasant experience: Guy Avni, Sergiy Bogomolov, Ventsislav Chonev, Rasmus Ibsen-Jensen, Mirco Giacobbe, Bernhard Kragl, Hui Kong, Petr Novotný, Jan Otop, Andreas Pavlogiannis, Tantjana Petrov, Arjun Radhakrishna, Jakob Ruess, Thorsten Tarrach, as well as other members of groups Henzinger and Chatterjee.
Page
163
IST-REx-ID

Cite this

Daca P. Statistical and Logical Methods for Property Checking. IST Austria; 2017. doi:10.15479/AT:ISTA:TH_730
Daca, P. (2017). Statistical and logical methods for property checking. IST Austria. https://doi.org/10.15479/AT:ISTA:TH_730
Daca, Przemyslaw. Statistical and Logical Methods for Property Checking. IST Austria, 2017. https://doi.org/10.15479/AT:ISTA:TH_730.
P. Daca, Statistical and logical methods for property checking. IST Austria, 2017.
Daca P. 2017. Statistical and logical methods for property checking, IST Austria, 163p.
Daca, Przemyslaw. Statistical and Logical Methods for Property Checking. IST Austria, 2017, doi:10.15479/AT:ISTA:TH_730.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:11:26Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar