Symbolic algorithms for graphs and markov decision processes with fairness objectives Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Monika; Loitzenbauer, Veronika; Oraee, Simin; Toman, Viktor
Title: Symbolic algorithms for graphs and markov decision processes with fairness objectives
Title Series: LNCS
Affiliation IST Austria
Abstract: Given a model and a specification, the fundamental model-checking problem asks for algorithmic verification of whether the model satisfies the specification. We consider graphs and Markov decision processes (MDPs), which are fundamental models for reactive systems. One of the very basic specifications that arise in verification of reactive systems is the strong fairness (aka Streett) objective. Given different types of requests and corresponding grants, the objective requires that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All ω -regular objectives can be expressed as Streett objectives and hence they are canonical in verification. To handle the state-space explosion, symbolic algorithms are required that operate on a succinct implicit representation of the system rather than explicitly accessing the system. While explicit algorithms for graphs and MDPs with Streett objectives have been widely studied, there has been no improvement of the basic symbolic algorithms. The worst-case numbers of symbolic steps required for the basic symbolic algorithms are as follows: quadratic for graphs and cubic for MDPs. In this work we present the first sub-quadratic symbolic algorithm for graphs with Streett objectives, and our algorithm is sub-quadratic even for MDPs. Based on our algorithmic insights we present an implementation of the new symbolic approach and show that it improves the existing approach on several academic benchmark examples.
Keywords: model checking; Markov Decision Processes; Reactive system; Markov processes; Symbolic algorithms; Specifications; Computer aided analysis; graphic methods; Computer circuits; Fundamental models; Algorithmic verification; Explicit algorithms; Implicit representation; State-space explosion
Conference Title: CAV: Computer Aided Verification
Volume: 10982
Conference Dates: 14 - 17 July, 2018
Conference Location: Oxford, UK
ISBN: 03029743 (ISSN); 9783319961415 (ISBN)
Publisher: Springer  
Date Published: 2018-07-18
Start Page: 178
End Page: 197
Copyright Statement: CC BY 4.0
DOI: 10.1007/978-3-319-96142-2_13
Notes: Acknowledgements. K. C. and M. H. are partially supported by the Vienna Science and Technology Fund (WWTF) grant ICT15-003. K. C. is partially supported by the Austrian Science Fund (FWF): S11407-N23 (RiSE/SHiNE), and an ERC Start Grant (279307: Graph Games). V. T. is partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie Grant Agreement No. 665385.
Open access: yes (OA journal)
IST Austria Authors
  1. Viktor Toman
    2 Toman
Related IST Austria Work