Confluence reduction for probabilistic systems

Mark Timmer; Jaco van de Pol; Mariëlle Stoelinga

Confluence reduction for probabilistic systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

109 Downloads (Pure)

Abstract

In this presentation we introduce a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We proved 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. We present a case study, demonstrating that significant reductions can be obtained.

Original language	English
Title of host publication	Proceedings of the 2nd Young Researchers Workshop on Concurrency Theory (YR-CONCUR 2010), Paris, France. September, 2010
Place of Publication	Eindhoven, The Netherlands
Publisher	Eindhoven University of Technology
Pages	87-90
Number of pages	4
Publication status	Published - Sept 2010
Event	2nd Young Researchers Workshop on Concurrency Theory 2010 - Paris, France Duration: 4 Sept 2010 → 4 Sept 2010 Conference number: 2

Workshop

Workshop	2nd Young Researchers Workshop on Concurrency Theory 2010
Country/Territory	France
City	Paris
Period	4/09/10 → 4/09/10

Keywords

Probabilistic automata
State space reduction
EC Grant Agreement nr.: FP7-ICT-2007-1
Branching probabilistic bisimulation
Confluence
EC Grant Agreement nr.: FP7/214755
Probabilistic process algebra

Access to Document

AbstractFinal published version, 104 KB

Confluence Reduction for Probabilistic Systems
Timmer, M., Stoelinga, M. & van de Pol, J., Mar 2011, Proceedings of the 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2011. Abdulla, P. A. & Leino, K. R. M. (eds.). Berlin: Springer, p. 311-325 15 p. (Lecture Notes in Computer Science; vol. 6605).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
14 Link opens in a new tab Citations (Scopus)

178 Downloads (Pure)

Cite this

@inproceedings{049e1d0b2cd24a489c460228584ba7f4,

title = "Confluence reduction for probabilistic systems",

abstract = "In this presentation we introduce a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We proved 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. We present a case study, demonstrating that significant reductions can be obtained.",

keywords = "Probabilistic automata, State space reduction, EC Grant Agreement nr.: FP7-ICT-2007-1, Branching probabilistic bisimulation, Confluence, EC Grant Agreement nr.: FP7/214755, Probabilistic process algebra",

author = "Mark Timmer and \{van de Pol\}, Jaco and Mari{\"e}lle Stoelinga",

year = "2010",

month = sep,

language = "English",

pages = "87--90",

booktitle = "Proceedings of the 2nd Young Researchers Workshop on Concurrency Theory (YR-CONCUR 2010), Paris, France. September, 2010",

publisher = "Eindhoven University of Technology",

address = "Netherlands",

note = "2nd Young Researchers Workshop on Concurrency Theory 2010 ; Conference date: 04-09-2010 Through 04-09-2010",

}

Timmer, M , van de Pol, J & Stoelinga, M 2010, Confluence reduction for probabilistic systems. in Proceedings of the 2nd Young Researchers Workshop on Concurrency Theory (YR-CONCUR 2010), Paris, France. September, 2010. Eindhoven University of Technology, Eindhoven, The Netherlands, pp. 87-90, 2nd Young Researchers Workshop on Concurrency Theory 2010, Paris, France, 4/09/10.

Confluence reduction for probabilistic systems. / Timmer, Mark ; van de Pol, Jaco ; Stoelinga, Mariëlle.
Proceedings of the 2nd Young Researchers Workshop on Concurrency Theory (YR-CONCUR 2010), Paris, France. September, 2010. Eindhoven, The Netherlands: Eindhoven University of Technology, 2010. p. 87-90.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Confluence reduction for probabilistic systems

AU - Timmer, Mark

AU - van de Pol, Jaco

AU - Stoelinga, Mariëlle

N1 - Conference code: 2

PY - 2010/9

Y1 - 2010/9

N2 - In this presentation we introduce a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We proved 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. We present a case study, demonstrating that significant reductions can be obtained.

AB - In this presentation we introduce a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We proved 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. We present a case study, demonstrating that significant reductions can be obtained.

KW - Probabilistic automata

KW - State space reduction

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

KW - Branching probabilistic bisimulation

KW - Confluence

KW - EC Grant Agreement nr.: FP7/214755

KW - Probabilistic process algebra

M3 - Conference contribution

SP - 87

EP - 90

BT - Proceedings of the 2nd Young Researchers Workshop on Concurrency Theory (YR-CONCUR 2010), Paris, France. September, 2010

PB - Eindhoven University of Technology

CY - Eindhoven, The Netherlands

T2 - 2nd Young Researchers Workshop on Concurrency Theory 2010

Y2 - 4 September 2010 through 4 September 2010

ER -

Confluence reduction for probabilistic systems

Abstract

Workshop

Keywords

Access to Document

Fingerprint

Research output

Confluence Reduction for Probabilistic Systems

Cite this