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