• Article
  • | |
  • Metrics
  • |
  • Reference [8]
  • |
  • Related [20]
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    Bisimulation is adopted in the π-calculus as the criterion to identify processes. For finite-state processes, bisimulation equivalence is decidable. In this paper, an optimization technique for a bisimulation checking algorithm is presented. It works by instantiating input names only to those free names which are used in subsequent matches. The technique can significantly reduce the required time and space, as illustrated by several benchmark examples. The correctness of the optimization is also proven.

    Reference
    [1] Lin, H. Computing bisimulations for finite-control π-Calculus. Journal of Computer Science and Technology, 2000,15(1):1~9.
    [2] Milner, R., Parrow, J., Walker, D. A calculus of mobile processes, Part Ⅰ, ⅠⅠ. Information and Computation, 1992,100(1):1~77.
    [3] Victor, B. A Verification Tool for the Polyadic π-Calculus [Licentiate Thesis]. Sweden: Department of Computer Systems, Uppsala University, 1994.
    [4] Victor, B., Moller, F. The mobility workbench——a tool of the π-Calculus. In: Dill, D. ed. Proceedings of CAV'94. Lecture Notes in Computer Science, Vol 818. Berlin: Springer-Verlag, 1994. 428~440.
    [5] Sangiorgi, D. A theory of bisimulation for the π-Calculus. Acta Informatica, 1996,33(1):69~97.
    [6] Hennessy, M., Lin, H. Symbolic bisimulations. Theoretical Computer Science, 1995,138(2):353~389.
    [7] Lin, H. “On-the-fly Instantiation” of value-passing processes. In: Formal Description Techniques and Protocol Specification, Testing and Verification. Paris: Kluwer Academic Publishers, 1998. 215~230.
    [8] 方海,许文,林惠民.带赋值符号迁移图的局部优化算法.计算机研究与发展,2000,37(1):95~101.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

许文,方海,林惠民.π-演算互模拟判定算法的优化和实现.软件学报,2001,12(2):159-166

Copy
Share
Article Metrics
  • Abstract:3883
  • PDF: 4552
  • HTML: 0
  • Cited by: 0
History
  • Received:May 11,2000
  • Revised:November 27,2000
You are the first2035322Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063