In this paper we consider two relations over stochastic automata, named lumpable bisimulation and exact equivalence, that induce a strong and an exact lumping, respectively, on the underlying Markov chains. We show that an exact equivalence over the states of a non-synchronising automaton is indeed a lumpable bisimulation for the corresponding reversed automaton and then it induces a strong lumping on the time-reversed Markov chain underlying the model. This property allows us to prove that the class of quasi-reversible models is closed under exact equivalence. Quasi-reversibility is a pivotal property to study product-form models. Hence, exact equivalence turns out to be a theoretical tool to prove the product-form of models by showing that they are exactly equivalent to models which are known to be quasi-reversible. Algorithms for computing both lumpable bisimulation and exact equivalence are introduced. Case studies as well as performance tests are also presented.

Lumping-based equivalences in Markovian automata: Algorithms and applications to product-form analyses

Alzetta, Giacomo;Piazza, Carla;
2018-01-01

Abstract

In this paper we consider two relations over stochastic automata, named lumpable bisimulation and exact equivalence, that induce a strong and an exact lumping, respectively, on the underlying Markov chains. We show that an exact equivalence over the states of a non-synchronising automaton is indeed a lumpable bisimulation for the corresponding reversed automaton and then it induces a strong lumping on the time-reversed Markov chain underlying the model. This property allows us to prove that the class of quasi-reversible models is closed under exact equivalence. Quasi-reversibility is a pivotal property to study product-form models. Hence, exact equivalence turns out to be a theoretical tool to prove the product-form of models by showing that they are exactly equivalent to models which are known to be quasi-reversible. Algorithms for computing both lumpable bisimulation and exact equivalence are introduced. Case studies as well as performance tests are also presented.
File in questo prodotto:
File Dimensione Formato  
iac17.pdf

accesso aperto

Descrizione: Versione Pre-print
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 508.82 kB
Formato Adobe PDF
508.82 kB Adobe PDF Visualizza/Apri
main.pdf

accesso aperto

Descrizione: Versione post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 539.77 kB
Formato Adobe PDF
539.77 kB Adobe PDF Visualizza/Apri
1-s2.0-S0890540118300634-main-2.pdf

non disponibili

Descrizione: Versione editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 937.6 kB
Formato Adobe PDF
937.6 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1142576
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 14
social impact