Generating Compact MTBDD-Representations from Probmela Specifications

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
TitelModel Checking Software
Redakteure/-innenKlaus Havelund, Rupak Majumdar, Jens Palsberg
ErscheinungsortBerlin, Heidelberg
Herausgeber (Verlag)Springer, Berlin, Heidelberg
Seiten60-76
Seitenumfang17
ISBN (elektronisch)978-3-540-85114-1
ISBN (Print)978-3-540-85113-4
PublikationsstatusVeröffentlicht - 2008
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science
Band5156
ISSN0302-9743

Workshop

Titel15th International SPIN Workshop on Model Checking of Software
KurztitelSPIN 2008
Veranstaltungsnummer15
Dauer10 - 12 August 2008
Webseite
BekanntheitsgradInternationale Veranstaltung
OrtUniversity of California, Los Angeles (UCLA)
StadtLos Angeles
LandUSA/Vereinigte Staaten

Externe IDs

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

Schlagworte