Determination of weak simulative relationships on interactive Markov chains
Xing Jing-hong · Journal of Lanzhou University of Technology · 2008
The algorithm of the weak simulative,preclusive relationship on interactive Markov chains(IMCs) was discussed.When such relationship was to be judged,the emphasis was put on the judgment of the simulative preclusive relationship on the probability transition.Meanwhile,the influence of internal action on the system should be considered.By introducing appropriate variables,the Markov transition condition in the definition of weak simulation on IMCs was translated into the solution of a liner programming problem.By using the numerical solution for the latter,the solutions could be found in polynomial-time complexity.Therefore,the polynomial-time algorithm was obtained for determining whether two processes on an IMCs were of weak simulation.