吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (01): 142-148.doi: 10.13229/j.cnki.jdxbgxb201401025

• 论文 • 上一篇    下一篇

一种递归π演算向Petri网的转换方法

康辉1, 张双双1,2, 梅芳1   

  1. 1. 吉林大学, 计算机科学与技术学院, 长春 130012;
    2. 吉林信息安全测评中心, 长春 130062
  • 收稿日期:2012-12-28 出版日期:2014-01-01 发布日期:2014-01-01
  • 通讯作者: 梅芳(1977-),女,讲师,博士.研究方向:自主通信,策略网管.E-mail:meifang@jlu.edu.cn E-mail:meifang@jlu.edu.cn
  • 作者简介:康辉(1968-),女,副教授.研究方向:Web服务与服务组合技术.E-mail:kanghui@jlu.edu.cn
  • 基金资助:

    国家自然科学基金项目(61073164).

Petri net translation of recursion π-calculus

KANG Hui1, ZHANG Shuang-shuang1,2, MEI Fang1   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2. Jilin Information Technology Security Evaluation Center, Changchun 130062, China
  • Received:2012-12-28 Online:2014-01-01 Published:2014-01-01

摘要:

针对π演算中的递归结构,本文给出了一种递归π演算向Petri网的转换方法。该转换遵循基本进程转换规则以及组合规则,采用层次化方法,针对递归次数较多时产生的Petri网结点过多的情况,本文给出了一种更简洁的Petri网表示,它保留了系统的语义,且编码完全相同的轨迹集合,对于在规模较大的复杂系统中应用Petri网模型有着积极的意义。本文还分别证明了递归π演算与转换的Petri网的互模拟等价性以及Petri网与其简洁表示的等价性。

关键词: 计算机软件, 递归&pi, 演算转换, 层次化方法, Petri网简洁表示, 互模拟等价

Abstract:

In view of the recursive structure in π-calculus, a kind of Petri net translation of recursion π-calculus is presented. Following the basic process translation rules and combination rules, the translation uses the hierarchical method. When the recursive structure executes many times, excessive more Petri net nodes will be generated. To solve this problem, a more compact representation for this Petri net is defined, which preserves the semantics of the system in that it encodes exactly the same set of traces. The bisimulation of recursion π-calculus and the Petri net transition is proved, as well as the equivalence between Petri net and its more compact representation.

Key words: computer application, recursion π-calculus translation, hierarchical method, more compact representation of Petri net, bisimulation equivalence

中图分类号: 

  • TP31

[1] Thomas E. Service-Oriented Architecture(SOA): Concepts, Technology, and Design[M]. New Jersey: PrenticeHall, 2005.

[2] Leymann F, Roller D, Schmidt M T. Web services and business process management[J]. IBM Systems Journal, 2002, 41(2): 198-211.

[3] Milner R, Parrow J, Walker D. A calculus of mobile processes part Ⅰ/Ⅱ[J]. Journal of Information and Computation, 1992, 100(1): 1-77.

[4] Milner R. Communication and Concurrent[M]. New Jersey: PreticeHall, 1989.

[5] Roland Meyer. A theory of structural stationarity in the π-Calculus[J]. Acta Informatica, 2009, 46:87-137.

[6] Michele B, Davide S. A fully abstract semantics for causality in the Pi calculus[C]//Proceedings of STACS'95, LNCS, Springer, 1995, 900: 243-254.

[7] Baeten J C M, Bergstra J A, Klop J W. An operational semantics for process algebra[J]. Mathematical Problems in Computation Theory, 1988, 21: 47-81.

[8] Eile B, Raymond D, Maciei K. Petri Net Algebra[M]. Bolin: Springer, 2001.

[9] Ulrich B, Daniel M. Object-oriented concepts for coloured Petri nets[C]//IEEE International Conference on Systems, Man and Cybernetics, 1993, 3: 279-286.

[10] Peschanski F, Klaudel H, Devillers R. A Petri Net Interpretation of Open Reconfigurable Systems[C]//PETRI NETS 2011, LNCS 6709, 2011:208-227.

[11] Christensen S, Hansen N D. Coloured Petri nets extended with place capacities, test arcs and inhibitor arcs[J]. Application and Theory of Petri Nets, 1993, 691: 186-205.

[12] Raymond D, Hanna K, Maciej K. A compositional Petri net translation of general Pi calculus terms[J]. Formal Aspects of Computing, 2008, 20: 429-450.

[13] Peschanski F, Klaudel H, Devillers R. A decidable characterization of a graphical pi-calculus with iterators[C]//In: Infinity. EPTCS, 2010, 39:47-61.

[1] 马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2] 罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[3] 应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[4] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[5] 王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[6] 特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[7] 康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[8] 陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[9] 刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[10] 冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[11] 李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[12] 王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[13] 黄宏涛,王静,叶海智,黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
[14] 范大娟1, 2, 黄志球1, 肖芳雄1, 祝义1, 王进1. 面向多服务交互的相容性分析与适配器生成[J]. 吉林大学学报(工学版), 2014, 44(4): 1094-1103.
[15] 贺秦禄1, 李战怀1, 王乐晓1, 王瑞2. 云存储系统聚合带宽测试技术[J]. 吉林大学学报(工学版), 2014, 44(4): 1104-1111.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!