A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rule...A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).展开更多
基金the National Natural Science Foundation of China(Nos.61261130589 and 61033002)the Fund of the Science and Technology Commission of Shanghai Municipality(No.11XD1402800)
文摘A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).
