Generating Compact MTBDD-Representations from Probmela Specifications

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

The purpose of the paper is to provide an automatic transformation of parallel programs of an imperative probabilistic guarded command language (called Probmela) into probabilistic reactive module specifications. The latter serve as basis for the input language of the symbolic MTBDD-based probabilistic model checker PRISM, while Probmela is the modeling language of the model checker LiQuor which relies on an enumerative approach and supports partial order reduction and other reduction techniques. By providing the link between the model checkers PRISM and LiQuor, our translation supports comparative studies of different verification paradigms and can serve to use the (more comfortable) guarded command language for a MTBDD-based quantitative analysis. The challenges were (1) to ensure that the translation preserves the Markov decision process semantics, (2) the efficiency of the translation and (3) the compactness of the symbolic BDD-representation of the generated PRISM-language specifications.

Details

Original languageEnglish
Title of host publicationModel Checking Software
EditorsKlaus Havelund, Rupak Majumdar, Jens Palsberg
Place of PublicationBerlin, Heidelberg
PublisherSpringer, Berlin, Heidelberg
Pages60-76
Number of pages17
ISBN (electronic)978-3-540-85114-1
ISBN (print)978-3-540-85113-4
Publication statusPublished - 2008
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science
Volume5156
ISSN0302-9743

Workshop

Title15th International SPIN Workshop on Model Checking of Software
Abbreviated titleSPIN 2008
Conference number15
Duration10 - 12 August 2008
Website
Degree of recognitionInternational event
LocationUniversity of California, Los Angeles (UCLA)
CityLos Angeles
CountryUnited States of America

External IDs

Scopus 54249166241
ORCID /0000-0002-5321-9343/work/205988101

Keywords