NDLI: Finite horizon analysis of Markov Chains with the Murϕ verifier

Content Provider	Springer Nature Link
Author	Penna, Giuseppe Della Intrigila, Benedetto Melatti, Igor Tronci, Enrico Zilli, Marisa Venturini
Copyright Year	2006
Abstract	In this paper we present an explicit disk-based verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. Given a Markov Chain and an integer k (horizon), our algorithm checks whether the probability of reaching an error state in at most k steps is below a given threshold. We present an implementation of our algorithm within a suitable extension of the Murϕ verifier. We call the resulting probabilistic model checker FHP-Murϕ (Finite Horizon ProbabilisticMurϕ). We present experimental results comparing FHP-Murϕ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Murϕ can handle systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems).
Starting Page	397
Ending Page	409
Page Count	13
File Format	PDF
ISSN	14332779
Journal	International Journal on Software Tools for Technology Transfer
Volume Number	8
Issue Number	4-5
e-ISSN	14332787
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-04-04
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Automatic verification Model checking Markov chains Probabilistic model checking Probabilistic verification Software Engineering/Programming and Operating Systems Software Engineering Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Probabilistic reachability for parametric Markov models

Numerical vs. statistical probabilistic model checking

Exploiting transition locality in automatic verification of finite-state concurrent systems

On hypothesis testing for statistical model checking

A formal analysis of bluetooth device discovery

Probabilistic symbolic model checking with PRISM: a hybrid approach

Automatic verification of the IEEE 1394 root contention protocol with KRONOS and PRISM

Constructive model-based analysis for safety assessment

Developments in automated verification techniques

Finite horizon analysis of Markov Chains with the Murϕ verifier

Similar Documents

Probabilistic reachability for parametric Markov models

Numerical vs. statistical probabilistic model checking

Exploiting transition locality in automatic verification of finite-state concurrent systems

On hypothesis testing for statistical model checking

A formal analysis of bluetooth device discovery

Probabilistic symbolic model checking with PRISM: a hybrid approach

Automatic verification of the IEEE 1394 root contention protocol with KRONOS and PRISM

Constructive model-based analysis for safety assessment

Developments in automated verification techniques

Finite horizon analysis of Markov Chains with the Murϕ verifier