Probabilistic Bisimulation: Naturally on Distributions

D 2014

Probabilistic Bisimulation: Naturally on Distributions

HERMANNS, Holger, Jan KRČÁL a Jan KŘETÍNSKÝ

Základní údaje

Originální název

Probabilistic Bisimulation: Naturally on Distributions

Autoři

HERMANNS, Holger (276 Německo), Jan KRČÁL (203 Česká republika) a Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí)

Vydání

Heidelberg Dordrecht London New York, CONCUR 2014 - Concurrency Theory - 25th International Conference, od s. 249-265, 17 s. 2014

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/14:00073710

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-44583-9

ISSN

DOI

http://dx.doi.org/10.1007/978-3-662-44584-6_18

Klíčová slova anglicky

stochastic systems; probability; bisimulation; non-determinism; process algebra; coalgebra

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2015 05:44, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition re- fines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

MUNI/A/0765/2013, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

MUNI/A/0855/2013, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace III. (Akronym: FI MAV III.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace III., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

HERMANNS, Holger, Jan KRČÁL a Jan KŘETÍNSKÝ. Probabilistic Bisimulation: Naturally on Distributions. In CONCUR 2014 - Concurrency Theory - 25th International Conference. Heidelberg Dordrecht London New York: Springer, 2014, s. 249-265. ISBN 978-3-662-44583-9. Dostupné z: https://dx.doi.org/10.1007/978-3-662-44584-6_18.

@inproceedings{1187166,
   author = {Hermanns, Holger and Krčál, Jan and Křetínský, Jan},
   address = {Heidelberg Dordrecht London New York},
   booktitle = {CONCUR 2014 - Concurrency Theory - 25th International Conference},
   doi = {http://dx.doi.org/10.1007/978-3-662-44584-6_18},
   keywords = {stochastic systems; probability; bisimulation; non-determinism; process algebra; coalgebra},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Heidelberg Dordrecht London New York},
   isbn = {978-3-662-44583-9},
   pages = {249-265},
   publisher = {Springer},
   title = {Probabilistic Bisimulation: Naturally on Distributions},
   year = {2014}
}

TY  - JOUR
ID  - 1187166
AU  - Hermanns, Holger - Krčál, Jan - Křetínský, Jan
PY  - 2014
TI  - Probabilistic Bisimulation: Naturally on Distributions
PB  - Springer
CY  - Heidelberg Dordrecht London New York
SN  - 9783662445839
KW  - stochastic systems
KW  - probability
KW  - bisimulation
KW  - non-determinism
KW  - process algebra
KW  - coalgebra
N2  - In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition re- fines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.
ER  -

HERMANNS, Holger, Jan KRČÁL a Jan KŘETÍNSKÝ. Probabilistic Bisimulation: Naturally on Distributions. In \textit{CONCUR 2014 - Concurrency Theory - 25th International Conference}. Heidelberg Dordrecht London New York: Springer, 2014, s.~249-265. ISBN~978-3-662-44583-9. Dostupné z: https://dx.doi.org/10.1007/978-3-662-44584-6\_{}18.

Podrobný výpis o publikaci