Quantitative notions of bisimulation are well-known tools forthe minimization of dynamical models such as Markov chains and ordinarydifferential equations (ODEs). In forward bisimulations, each state inthe quotient model represents an equivalence class and the dynamicalevolution gives the overall sum of its members in the original model.Here we introduce generalized forward bisimulation (GFB) for dynamicalsystems over commutative monoids and develop a partition refinementalgorithm to compute the coarsest one. When the monoid is (R,+), werecover probabilistic bisimulation for Markov chains and more recentforward bisimulations for nonlinear ODEs. Using (R,·) we get nonlinearreductions for discrete-time dynamical systems and ODEs where eachvariable in the quotient model represents the product of originalvariables in the equivalence class. When the domain is a finite set suchas the Booleans B, we can apply GFB to Boolean networks (BN), a widelyused dynamical model in computational biology. Using a prototypeimplementation of our minimization algorithm for GFB, we finddisjunction- and conjunction-preserving reductions on 60 BN from twowell-known repositories, and demonstrate the obtained analysisspeed-ups. We also provide the biological interpretation of thereduction obtained for two selected BN, and we show how GFB enables theanalysis of a large one that could not be analyzed otherwise. Using a randomized version of our algorithm we find product-preserving(therefore non-linear) reductions on 21 dynamical weighted networks fromthe literature that could not be handled by the exact algorithm.
Join at: http://imt.lu/conference