交互式Petri网及其兼容性研究

项目名称： 交互式Petri网及其兼容性研究

项目编号： No.61202016

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 刘关俊

作者单位： 同济大学

项目金额： 25万元

中文摘要： Web服务组合与跨组织工作流在学术界与工业界得到广泛研究与应用，它们在逻辑层可以抽象为一组子系统通过消息的发送与接收进行交互协同。提出交互式Petri网（IPN）以模拟这些系统。基于IPN可达性，定义0、1、2、3级兼容性以刻画子系统间不同的协同能力。给出IPN的平凡拓展网，证明IPN的3级兼容性等价于其平凡拓展网的活和有界性,但其判定是co-NP-难的。从子系统执行逻辑、消息库所的输出以及事件的外部使能条件等三个维度，将IPN分为16个具有不同结构特征的子类，其目的是针对不同类别研究其基于网结构的兼容性判定与控制。对其中一些子类已给出判定其兼容性、活性的充要条件。在已有工作基础上继续研究：IPN的0、1、2级兼容性问题的复杂度，以及与平凡拓展网的性质（如活性、可重复性等）之间的关系；基于网结构判定其他子类兼容性的充要条件；兼容性的控制问题；基于理论成果开发IPN分析软件。

中文关键词： Petri网；交互式系统；兼容性；复杂度；行为模型

英文摘要： Web service and inter-organizational workflow are widely studied and applied in academic and industrial systems. These systems can be viewed as a collection of subsystems that interact with each other via a set of message channels. We define a subclass of Petri nets called Interactive Petri Nets (IPN) to model these systems, and classify compatiblity into four levels (i.e., L0-, L1-, L2-, L3-compatibility) to reflect different cooperating ability among subsystems. We have proven that the L3-compatibility is equavilent to the liveness and boundedness, but is co-NP-hard. From three aspects (i.e., execution logics, output of message channels, and external enabled condition of events) we present 16 subclasses of IPNs which have different structural characteristics. The purpose of this classification is to explore the conditions of deciding and controlling compatibility for each subclass based on its own structure. We have proposed sufficient and necessary conditions for the compatibility and liveness of some subclasses. Therefore, this project will continue to research IPNs and their compatibility mainly including: 1) the relationships between compatibility and other properties such as liveness and repetitiveness; 2) the net-structure-based conditions for the compatibility of other subclasses; 3) the control problem

英文关键词： Petri net；interactive systems；compatibility；complexity；behavior model