The Quest for Minimal Quotients for Probabilistic Automata

Christian Eisentraut; Holger Hermanns; Johann Schuster; Andrea Turrini; Lijun Zhang

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

The Quest for Minimal Quotients for Probabilistic Automata

Christian Eisentraut
, Holger Hermanns
, Johann Schuster
, Andrea Turrini
, Lijun Zhang

Department of Applied Mathematics and Computer Science

Saarland University
Bundeswehr University Munich

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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
Title of host publication	Tools and Algorithms for the Construction and Analysis of Systems : 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings
Publisher	Springer
Publication date	2013
Pages	16-31
ISBN (Print)	978-3-642-36741-0
ISBN (Electronic)	978-3-642-36742-7
DOIs	https://doi.org/10.1007/978-3-642-36742-7_2
Publication status	Published - 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 http://www.etaps.org/2013/tacas13

Conference

Conference	19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013)
Country/Territory	Italy
City	Rome
Period	16/03/2013 → 24/03/2013
Internet address	http://www.etaps.org/2013/tacas13

Series	Lecture Notes in Computer Science
Volume	7795
ISSN	0302-9743

Keywords

Algorithms
Polynomial approximation
Automata theory

Access to Document

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

OpenUrl availability

Check availability in DTU Findit

Cite this

Eisentraut, C., Hermanns, H., Schuster, J., Turrini, A., & Zhang, L. (2013). The Quest for Minimal Quotients for Probabilistic Automata. In Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings (pp. 16-31). Springer. https://doi.org/10.1007/978-3-642-36742-7_2

Eisentraut, Christian ; Hermanns, Holger ; Schuster, Johann et al. / The Quest for Minimal Quotients for Probabilistic Automata. Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings. Springer, 2013. pp. 16-31 (Lecture Notes in Computer Science, Vol. 7795).

@inproceedings{6b4e98b710514550862af4bf472dba3d,

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 = "Algorithms, Polynomial approximation, Automata theory",

author = "Christian Eisentraut and Holger Hermanns and Johann Schuster and Andrea Turrini and Lijun Zhang",

year = "2013",

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

language = "English",

isbn = "978-3-642-36741-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "16--31",

booktitle = "Tools and Algorithms for the Construction and Analysis of Systems",

note = "19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013) ; Conference date: 16-03-2013 Through 24-03-2013",

url = "http://www.etaps.org/2013/tacas13",

}

Eisentraut, C, Hermanns, H, Schuster, J, Turrini, A & Zhang, L 2013, The Quest for Minimal Quotients for Probabilistic Automata. in Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings. Springer, Lecture Notes in Computer Science, vol. 7795, pp. 16-31, 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013), Rome, Italy, 16/03/2013. https://doi.org/10.1007/978-3-642-36742-7_2

The Quest for Minimal Quotients for Probabilistic Automata. / Eisentraut, Christian; Hermanns, Holger; Schuster, Johann et al.
Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings. Springer, 2013. p. 16-31 (Lecture Notes in Computer Science, Vol. 7795).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - The Quest for Minimal Quotients for Probabilistic Automata

AU - Eisentraut, Christian

AU - Hermanns, Holger

AU - Schuster, Johann

AU - Turrini, Andrea

AU - Zhang, Lijun

PY - 2013

Y1 - 2013

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 - Algorithms

KW - Polynomial approximation

KW - Automata theory

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

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

M3 - Article in proceedings

SN - 978-3-642-36741-0

T3 - Lecture Notes in Computer Science

SP - 16

EP - 31

BT - Tools and Algorithms for the Construction and Analysis of Systems

PB - Springer

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 -

Eisentraut C, Hermanns H, Schuster J, Turrini A, Zhang L. The Quest for Minimal Quotients for Probabilistic Automata. In Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings. Springer. 2013. p. 16-31. (Lecture Notes in Computer Science, Vol. 7795). doi: 10.1007/978-3-642-36742-7_2

The Quest for Minimal Quotients for Probabilistic Automata

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this