11th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

Efficient Computation of Renaming Functions for ρ-reversible Discrete and Continuous Time Markov Chains

  • @INPROCEEDINGS{10.4108/eai.5-12-2017.2274305,
        author={Matteo  Sottana and Carla  Piazza and Andrea  Albarelli},
        title={Efficient Computation of Renaming Functions for ρ-reversible Discrete and Continuous Time Markov Chains},
        proceedings={11th EAI International Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2018},
        month={8},
        keywords={reversibility modulo renaming discrete and continuous time markov chains algorithms},
        doi={10.4108/eai.5-12-2017.2274305}
    }
    
  • Matteo Sottana
    Carla Piazza
    Andrea Albarelli
    Year: 2018
    Efficient Computation of Renaming Functions for ρ-reversible Discrete and Continuous Time Markov Chains
    VALUETOOLS
    ACM
    DOI: 10.4108/eai.5-12-2017.2274305
Matteo Sottana1, Carla Piazza2, Andrea Albarelli1,*
  • 1: Università Ca' Foscari Venezia
  • 2: Università di Udine
*Contact email: albarelli@unive.it

Abstract

With the introduction of ρ-reversibility, the basic notion of reversible Markov chain has been relaxed by allowing a wider range of scenarios. Specifically, the reversibility properties are not just sought on the chain itself, but also on all the possible topology-preserving renamings of its state space. Such renamings, called Renaming Functions, exhibit many interesting properties which can be exploited in different contexts. Unfortunately, finding a renaming function for a Markov chain is a very computationally intensive task. Using a naive approach it could require to check for all the possible state space permutations, which is unfeasible for all but the most trivial chains. As a matter of facts, we prove that the corresponding decision problem is polynomially equivalent to Graph Isomorphism. Nevertheless, we introduce an algorithm that, exploiting some necessary conditions for ρ-reversibility, is able to efficiently prune the search space and then verify the remaining renaming candidates. The correctness of the method is theoretically demonstrated and its practical effectiveness is shown over a significant set of discrete and continuous ρ-reversible Markov chains.