Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2013, Vol. 28 Issue (1) :203-216    DOI: 10.1007/s11390-013-1323-7
Software Engineering << Previous Articles | >>
非确定概率Petri网-一种研究系统定性和定量行为的新方法
Yang Liu1,2,3 (刘阳), Huai-Kou Miao1 (缪淮扣), Senior Member, CCF, Hong-Wei Zeng1 (曾红卫), Yan Ma2 (马艳), and Pan Liu1 (刘攀)
Nondeterministic Probabilistic Petri Net — A New Method to Study Qualitative and Quantitative Behaviors of System
Yang Liu1,2,3 (刘阳), Huai-Kou Miao1 (缪淮扣), Senior Member, CCF, Hong-Wei Zeng1 (曾红卫), Yan Ma2 (马艳), and Pan Liu1 (刘攀)
1. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China;
2. School of Information Science and Technology, Taishan University, Taian 271021, China;
3. State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210093, China

摘要
参考文献
相关文章
Download: [PDF 1201KB]  
摘要 目前已有多种Petri网模型可以用来对系统功能和性能方面同时建模,例如随机Petri网、广义随机Petri网、概率Petri网等.本文以概率Petri网为参考,扩展经典的Petri网模型用于建模系统的概率和非确定性等方面的特征.首先,在通用网论理论的指导下,以保证非确定性为前提,将概率度量理论引入到经典的Petri网模型,提出了一种非确定概率Petri网模型,给出了其相应的变迁触发规则和结构特征.然后,给出了其进程代数式的语义描述,并研究了基于该语义的非确定概率Petri网的组合运算法则;给出了其时态逻辑层面的语义描述,用action命题扩展PCTL(Probabilistic Computation Tree Logic),定义了一种基于action的PCTL(aPCTL),并给出了aPCTL概率模型检验算法验证非确定概率Petri网系统.基于开源软件PIPE,开发了非确定概率Petri网建模和验证工具NPNMV,并以一个工作流程的实例演示了其概率模型检验过程.
关键词非确定性   概率Petri网   模型检验   aPCTL     
Abstract: There are many variants of Petri net at present, and some of them can be used to model system with both function and performance specification, such as stochastic Petri net, generalized stochastic Petri net and probabilistic Petri net. In this paper, we utilize extended Petri net to address the issue of modeling and verifying system with probability and nondeterminism besides function aspects. Using probabilistic Petri net as reference, we propose a new mixed model NPPN (Nondeterministic Probabilistic Petri Net) system, which can model and verify systems with qualitative and quantitative behaviours. Then we develop a kind of process algebra for NPPN system to interpret its algebraic semantics, and an actionbased PCTL (Probabilistic Computation Tree Logic) to interpret its logical semantics. Afterwards we present the rules for compositional operation of NPPN system based on NPPN system process algebra, and the model checking algorithm based on the action-based PCTL. In order to put the NPPN system into practice, we develop a friendly and visual tool for modeling, analyzing, simulating, and verifying NPPN system using action-based PCTL. The usefulness and effectiveness of the NPPN system are illustrated by modeling and model checking an elaborate model of travel arrangements workflow.
Keywordsnondeterminism   probabilistic Petri net   model checking   action-based probabilistic computation tree logic     
Received 2011-12-14;
本文基金:

This work was supported by the National Natural Science Foundation of China under Grant Nos. 60970007, 61073050 and 61170044, the National Basic Research 973 Program of China under Grant No. 2007CB310800, the Shanghai Leading Academic Discipline Project of China under Grant No. J50103, and the Natural Science Foundation of Shandong Province of China under Grant No. ZR2012FQ013.

引用本文:   
Yang Liu, Huai-Kou Miao, Hong-Wei Zeng, Yan Ma, Pan Liu.非确定概率Petri网-一种研究系统定性和定量行为的新方法[J]  Journal of Computer Science and Technology , 2013,V28(1): 203-216
Yang Liu, Huai-Kou Miao, Hong-Wei Zeng, Yan Ma, and Pan Liu.Nondeterministic Probabilistic Petri Net — A New Method to Study Qualitative and Quantitative Behaviors of System[J]  Journal of Computer Science and Technology, 2013,V28(1): 203-216
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-013-1323-7
Copyright 2010 by Journal of Computer Science and Technology