The quest for minimal quotients for probabilistic automata

Christian Eisentraut; H. Hermanns; Johann Schuster; Andrea Turini; Lijun Zhang

doi:10.1007/978-3-642-36742-7_2

The quest for minimal quotients for probabilistic automata

Christian Eisentraut, H. Hermanns, Johann Schuster, Andrea Turini, Lijun Zhang

Research output: Contribution to conference › Paper

14 Citations (Scopus)

Abstract

One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms.

Original language	English
Pages	16-31
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-36742-7_2
Publication status	Published - Mar 2013
Event	19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013 - Rome, Italy Duration: 16 Mar 2013 → 24 Mar 2013 Conference number: 19

Conference

Conference	19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013
Abbreviated title	TACAS
Country/Territory	Italy
City	Rome
Period	16/03/13 → 24/03/13

Keywords

EWI-27343
EC Grant Agreement nr.: FP7/295261
EC Grant Agreement nr.: FP7/318490
IR-101830
EC Grant Agreement nr.: FP7/318003
EC Grant Agreement nr.: FP7/2007-2013

Access to Document

10.1007/978-3-642-36742-7_2

Cite this

@conference{49cc67a626604a4aba12a126876149e8,

title = "The quest for minimal quotients for probabilistic automata",

abstract = "One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms.",

keywords = "EWI-27343, EC Grant Agreement nr.: FP7/295261, EC Grant Agreement nr.: FP7/318490, IR-101830, EC Grant Agreement nr.: FP7/318003, EC Grant Agreement nr.: FP7/2007-2013",

author = "Christian Eisentraut and H. Hermanns and Johann Schuster and Andrea Turini and Lijun Zhang",

note = "Foreground = 10%; Type of activity = conference; Main leader = DTU; Type of audience = scientific community; Size of audience = 75; Countries addressed = international;; 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013, TACAS ; Conference date: 16-03-2013 Through 24-03-2013",

year = "2013",

month = mar,

doi = "10.1007/978-3-642-36742-7_2",

language = "English",

pages = "16--31",

}

TY - CONF

T1 - The quest for minimal quotients for probabilistic automata

AU - Eisentraut, Christian

AU - Hermanns, H.

AU - Schuster, Johann

AU - Turini, Andrea

AU - Zhang, Lijun

N1 - Conference code: 19

PY - 2013/3

Y1 - 2013/3

N2 - One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms.

AB - One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms.

KW - EWI-27343

KW - EC Grant Agreement nr.: FP7/295261

KW - EC Grant Agreement nr.: FP7/318490

KW - IR-101830

KW - EC Grant Agreement nr.: FP7/318003

KW - EC Grant Agreement nr.: FP7/2007-2013

U2 - 10.1007/978-3-642-36742-7_2

DO - 10.1007/978-3-642-36742-7_2

M3 - Paper

SP - 16

EP - 31

T2 - 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013

Y2 - 16 March 2013 through 24 March 2013

ER -

The quest for minimal quotients for probabilistic automata

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this