A counterexample-guided abstraction-refinement framework for markov decision processes
Authors:
Open Access
- 1 October 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 12 (1) , 1-49
Abstract
The main challenge in using abstractions effectively is to construct a suitable abstraction for the system being verified. One approach that tries to address this problem is that of counterexample guided abstraction refinement (CEGAR) , wherein one starts with a coarse abstraction of the system, and progressively refines it, based on invalid counterexamples seen in prior model checking runs, until either an abstraction proves the correctness of the system or a valid counterexample is generated. While CEGAR has been successfully used in verifying nonprobabilistic systems automatically, CEGAR has only recently been investigated in the context of probabilistic systems. The main issues that need to be tackled in order to extend the approach to probabilistic systems is a suitable notion of “counterexample”, algorithms to generate counterexamples, check their validity, and then automatically refine an abstraction based on an invalid counterexample. In this article, we address these issues, and present a CEGAR framework for Markov decision processes.Keywords
All Related Versions
Funding Information
- Division of Computing and Communication Foundations (CCF 0429639CCF 0448178CNS 0509321)
This publication has 31 references indexed in Scilit:
- Probabilistic CEGAR2008
- A game-based framework for CTL counterexamples and 3-valued abstraction-refinementACM Transactions on Computational Logic, 2007
- Probability and Nondeterminism in Operational Models of Concurrency2006
- Why Waste a Perfectly Good Abstraction?2006
- Don’t Know in Probabilistic Systems2006
- On finite-state approximants for probabilistic computation tree logicTheoretical Computer Science, 2005
- Comparative branching-time semantics for Markov chainsInformation and Computation, 2005
- Abstraction Refinement for Termination2005
- Counterexamples for Timed Probabilistic Reachability2005
- Deciding Bisimilarity and Similarity for Probabilistic ProcessesJournal of Computer and System Sciences, 2000