交互式马尔科夫链上弱模拟关系的计算

对交互式马尔可夫链模型(IMCs)上的弱模拟前序关系的计算算法进行讨论.在IMCs上判断弱模拟关系时,重点对概率转移关系进行弱模拟前序关系的判断,同时考虑内部动作对系统的影响.通过引入适当的变量,将IMCs上弱模拟定义中的马尔可夫转移条件转化为求解一个线性规划问题的解.利用该线性规划问题的数值求解方法,可在多项式时间内求得该线性规划问题的解.从而得到判定IMC上两个进程是否弱模拟的多项式时间算法.

Determination of weak simulative relationships on interactive Markov chains

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.