Confluence Reduction for Probabilistic Systems (extended version)

Research output: Working paperProfessional

10 Downloads (Pure)

Abstract

This paper presents a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We prove that this reduction preserves branching probabilistic bisimulation and can be applied on-the-fly. To support the technique, we introduce a method for detecting confluent transitions in the context of a probabilistic process algebra with data, facilitated by an earlier defined linear format. A case study demonstrates that significant reductions can be obtained.
Original languageUndefined
Place of PublicationIthaca, NY, USA
PublisherArXiv e-prints
Number of pages28
Publication statusPublished - 10 Nov 2010

Publication series

Name
PublisherarXiv.org
No.1011.2314

Keywords

  • State space reduction
  • Probabilistic automata
  • EWI-19088
  • EC Grant Agreement nr.: FP7/214755
  • IR-75221
  • Branching probabilistic bisimulation
  • Probabilistic process algebra
  • METIS-276225
  • EC Grant Agreement nr.: FP7-ICT-2007-1
  • Confluence

Cite this

@techreport{d1ed29a34ea34f4e99345bcd1152e09e,
title = "Confluence Reduction for Probabilistic Systems (extended version)",
abstract = "This paper presents a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We prove that this reduction preserves branching probabilistic bisimulation and can be applied on-the-fly. To support the technique, we introduce a method for detecting confluent transitions in the context of a probabilistic process algebra with data, facilitated by an earlier defined linear format. A case study demonstrates that significant reductions can be obtained.",
keywords = "State space reduction, Probabilistic automata, EWI-19088, EC Grant Agreement nr.: FP7/214755, IR-75221, Branching probabilistic bisimulation, Probabilistic process algebra, METIS-276225, EC Grant Agreement nr.: FP7-ICT-2007-1, Confluence",
author = "Mark Timmer and Stoelinga, {Mari{\"e}lle Ida Antoinette} and {van de Pol}, {Jan Cornelis}",
note = "eemcs-eprint-19088eemcs-eprint-19088",
year = "2010",
month = "11",
day = "10",
language = "Undefined",
publisher = "ArXiv e-prints",
number = "1011.2314",
type = "WorkingPaper",
institution = "ArXiv e-prints",

}

TY - UNPB

T1 - Confluence Reduction for Probabilistic Systems (extended version)

AU - Timmer, Mark

AU - Stoelinga, Mariëlle Ida Antoinette

AU - van de Pol, Jan Cornelis

N1 - eemcs-eprint-19088eemcs-eprint-19088

PY - 2010/11/10

Y1 - 2010/11/10

N2 - This paper presents a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We prove that this reduction preserves branching probabilistic bisimulation and can be applied on-the-fly. To support the technique, we introduce a method for detecting confluent transitions in the context of a probabilistic process algebra with data, facilitated by an earlier defined linear format. A case study demonstrates that significant reductions can be obtained.

AB - This paper presents a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We prove that this reduction preserves branching probabilistic bisimulation and can be applied on-the-fly. To support the technique, we introduce a method for detecting confluent transitions in the context of a probabilistic process algebra with data, facilitated by an earlier defined linear format. A case study demonstrates that significant reductions can be obtained.

KW - State space reduction

KW - Probabilistic automata

KW - EWI-19088

KW - EC Grant Agreement nr.: FP7/214755

KW - IR-75221

KW - Branching probabilistic bisimulation

KW - Probabilistic process algebra

KW - METIS-276225

KW - EC Grant Agreement nr.: FP7-ICT-2007-1

KW - Confluence

M3 - Working paper

BT - Confluence Reduction for Probabilistic Systems (extended version)

PB - ArXiv e-prints

CY - Ithaca, NY, USA

ER -