Towards supervisory control of Interactive Markov Chains: Plant minimization

We extend a model-based systems engineering framework for supervisory control of nondeterministic stochastic discrete-event systems with controllability-preserving minimization of the unsupervised system. This is a second out of four phases outlined in the development of the framework. In the first phase, we proposed a process theory that captures the notion of controllability of the underlying model of Interactive Markov Chains using a behavioral relation termed Markovian partial bisimulation. Interactive Markov Chains extend (nondeterministic) labeled transition systems with Markovian (exponential) delays. The Markovian partial bisimulation is a stochastic extension of partial bisimulation that captures controllability by stating that controllable events should be simulated, whereas uncontrollable events should be bisimulated. The stochastic behavior is preserved up to lumping of Markovian delays. We develop a minimization algorithm for the preorder and equivalence induced by the Markovian partial bisimulation based on the most efficient algorithms for simulation and Markovian bisimulation.