共查询到20条相似文献,搜索用时 15 毫秒
1.
Logic Petri nets (LPNs) are suitable to describe and analyze batch processing functions and passing value indeterminacy in cooperative systems. To investigate the dynamic properties of LPNs directly, a new method for analyzing LPNs is proposed based on marking reachability graphs in this paper. Enabled conditions of transitions are obtained and a marking reachability graph is constructed. All reachable markings can be obtained based on the graph; the fairness and reversibility of LPNs are analyzed. Moreover, the computing complexity of the enabled conditions and reachable markings can be reduced by this method. The advantages of the proposed method are illustrated by examples and analysis. 相似文献
2.
《IEEE transactions on pattern analysis and machine intelligence》1995,21(1):32-49
We present timing constraint Petri nets (or TCPN's for short) and describe how to use them to model a real-time system specification and determine whether the specification is schedulable with respect to imposed timing constraints. The strength of TCPN's over other time-related Petri nets is in the modeling and analysis of conflict structures. Schedulability analysis is conducted in three steps: specification modeling, reachability simulation, and timing analysis. First, we model a real-time system by transforming its system specification along with its imposed timing constraints into a TCPN; we call this net Ns. Then we simulate the reachability of Ns to verify whether a marking, Mn, is reachable from an initial marking, Mo. It is important to note that a reachable marking in Petri nets is not necessarily reachable in TCPN's due to the imposed timing constraints, Therefore, in the timing analysis step, a reachable marking Mn, found in the reachability simulation step is analyzed to verify whether Mn, is reachable with the timing constraints. Mn is said to be reachable in the TCPN's if and only if we can find at least one firing sequence σ so that all transitions in σ are strongly schedulable with respect to Mo under the timing constraints. If such Mn can be found, then we can assert that the specification is schedulable under the imposed timing constraints, otherwise the system specification needs to be modified or the timing constraints need to be relaxed. We also present a synthesis method for determining the best approximation of the earliest fire beginning time (EFBT) and the latest fire ending time (LFET) of each strongly schedulable transition 相似文献
3.
4.
T-组合Petri网的活性和公平性分析 总被引:1,自引:0,他引:1
同步合成是研究复杂Petri网系统性质的有效途径.文中通过引入可引发变迁序偶的概念,研究了T-组合(同步合成)Petri网对子网的活性和公平性继承关系,给出了一组T-组合Petri网活或公平的充要条件和充分条件.这些结果对网组合同步设计具有重要的指导意义 相似文献
5.
6.
7.
Fu-Shiung Hsieh 《International journal of control》2013,86(5):928-939
Non-ordinary controlled Petri nets (NCPNs) have the advantages to model flexible assembly systems in which multiple identical resources may be required to perform an operation. However, existing studies on NCPNs are still limited. For example, the robustness properties of NCPNs have not been studied. This motivates us to develop an analysis method for NCPNs. Robustness analysis concerns the ability for a system to maintain operation in the presence of uncertainties. It provides an alternative way to analyse a perturbed system without reanalysis. In our previous research, we have analysed the robustness properties of several subclasses of ordinary controlled Petri nets. To study the robustness properties of NCPNs, we augment NCPNs with an uncertainty model, which specifies an upper bound on the uncertainties for each reachable marking. The resulting PN models are called non-ordinary controlled Petri nets with uncertainties (NCPNU). Based on NCPNU, the problem is to characterise the maximal tolerable uncertainties for each reachable marking. The computational complexities to characterise maximal tolerable uncertainties for each reachable marking grow exponentially with the size of the nets. Instead of considering general NCPNU, we limit our scope to a subclass of PN models called non-ordinary controlled flexible assembly Petri net with uncertainties (NCFAPNU) for assembly systems and study its robustness. We will extend the robustness analysis to NCFAPNU. We identify two types of uncertainties under which the liveness of NCFAPNU can be maintained. 相似文献
8.
分布式锁管理DLM细化了锁模式的粒度,使得分布式系统具有更高的并发性,但死锁检测等锁的管理过程却更加复杂了,Petri网的应用能很好地解决该问题。为分布式锁建立Petri网模型,通过化简和合成建立系统的Petri网模型,借助Petri网的可达标识图实时检测出分布式系统的死锁状态,并查找死锁进程。 相似文献
9.
将AOE 网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE 网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。 相似文献
10.
This paper presents a generalization of forbidden state control synthesis methods for a broad class of controlled Petri nets (CtlPN). An algebra is defined for characterizing the interaction of paths in the Petri net. Given a specification of a forbidden marking set, the net structure is analyzed to determine an algebraic expression to represent the specification. For any net marking (state), evaluation of the expression will indicate whether forbidden markings are reachable and whether control is necessary. The expression is then used for determining the maximally permissive feedback control law 相似文献
11.
《Journal of Computer and System Sciences》2003,66(3):515-548
In a live and bounded free choice Petri net, pick a non-conflicting transition. Then there exists a unique reachable marking in which no transition is enabled except the selected one. For a routed live and bounded free choice net, this property is true for any transition of the net. Consider now a live and bounded stochastic routed free choice net, and assume that the routings and the firing times are independent and identically distributed. Using the above results, we prove the existence of asymptotic firing throughputs for all transitions in the net. Furthermore, the vector of the throughputs at the different transitions is explicitly computable up to a multiplicative constant. 相似文献
12.
RAMAVARAPU S. SREENIVAS 《Automatica》1998,34(12):1613-1615
The class of Independent, Increasing, Free-Choice Petri nets (II-FCPNs) was introduced in (Sreenivas, 1997c), where it is shown that any II-FCPN can be made live via supervision using a readily available policy. In a live Petri net (PN). Petri Net Theory and Modeling of systems. Prentice-Hall, Englewood Cliffs, NJ, Reisig (1985). Petri Nets. Springer, Berlin), it is possible to fire any transition from every reachable marking, although not necessarily immediately. In this paper we identify a class of PNs, where every transition is controllable, that are not necessarily II-FCPNs, that can be made live via supervision using a readily available policy constructed from the policy that enforces liveness in an II-FCPN. 相似文献
13.
Petri网分解的保性条件分析 总被引:3,自引:2,他引:3
Petri网的分解技术是用于复杂网系统分析的一种有效手段 .基于库所指标的 Petri网分解方法 ,将一个复杂的网系统分解成结构满足 |· t|≤且 |t· |≤ 1的简单子网 ,通过分解得到的子网与原系统的状态和行为之间存在着一种投影关系 .但是 ,子网本身也增加了一些不必要的状态和行为 (原网系统在子网上的投影只是子网状态和行为的一个子集 ) .本文提出分解过程中的状态保性和行为保性的概念 ,证明了分解过程中行为和状态保性的充要条件 ,基于标识可达图给出了相应的判定算法 ,对复杂系统的 Petri网分析方法提供了更为有效的理论和可行的技术 相似文献
14.
This paper addresses the problem of diagnosability for dynamic discrete event systems modeled with bounded or unbounded Petri nets that are deadlock-free and monitored with sensor configurations with marking and event measurements. The proposed method gives necessary and sufficient conditions for diagnosability. It is based on the transformation of the coverability graph into an observation graph that encodes all observation sequences of measured markings and events with respect to the sensor configuration. This graph also encodes all sequences of transitions that may fire from any reachable marking of the Petri net. Diagnosability is determined by analyzing the paths and circuits in the observation graph. The method is illustrated with several examples of bounded or unbounded Petri nets. 相似文献
15.
有界Petri网的可达图到网图的转换算法 总被引:4,自引:0,他引:4
本文给出了有界Petri网的可达标识图到网图的转换算法,对算法的正确性与复杂性分别进行了证明和估计,结果表明该算法是一个多项式算法,因而是有效的。 相似文献
16.
并发事务无死锁的可串行化调度的形式化方法 总被引:1,自引:0,他引:1
并发控制是多用户数据库管理系统(DBMS)的重要内容之一。该文对其形式化方法进行了研究,建立了符合两段锁协议的扩展有色Petri网模型。利用该模型的可达标识图,给出了判断满足两段锁协议的调度是否死锁的充分必要条件,并由此构造出并发事务的无死锁的可串行化调度。 相似文献
17.
1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞 相似文献
18.
陈黎静 《小型微型计算机系统》2012,33(7):1596-1598
弱持续Petri网是Petri网的一个子类,与系统的持续性密切相关.本文刻画了活的弱持续Petri网的一个行为特征,即,如果在一个标识M下两个不同的变迁t1与t2均是使能的,则存在两个变迁序列σ’与σ″满足:(1)t1σ’t2与t2σ″t1在M下是使能的,(2)t1不出现在σ″中,(3)t2不出现在σ’,并且(4)σ’与σ″的发生数向量相同.同时,本文揭示了弱持续网的两个结构特征,并证明了持续Petri网的同步合成网仍然保持持续性.这些结论丰富了Petri网的基本理论. 相似文献
19.
Xiaoguang Han Zengqiang Chen Kuize Zhang Zhongxin Liu Qing Zhang 《Asian journal of control》2020,22(1):500-510
In this paper, we present a comprehensive modeling technique for bounded Petri net systems (BPNSs) in the framework of the semi‐tensor product (STP) of matrices. The two dynamic properties of BPNSs, namely, reachability and controllability, are investigated systematacially. First, the dynamics of a bounded Petri net system (BPNS), by resorting to the STP of matrices, are expressed in the form of a discrete‐time bilinear equation, which is called the marking evolution equation (MEE) of BPNSs. Second, controllability and transition‐marking adjacency matrix (TMAM) of BPNSs are defined, respectively. Further, several necessary and sufficient conditions for reachability and controllability of BPNSs are given in terms of the MEE and TMAM. Third, an efficient algorithm to verify reachability property of BPNSs, in this paper, is provided, as well as its computational complexity. Finally, an example is presented to illustrate the theoretical results in this paper. The main contribution of this paper is the presentation of a precise mathematical model for BPNSs. The main advantage of the proposed approach is that not only it can be applied to verify whether or not any given marking is reachable from the other in state space, but also it is very convenient to find all firing sequences between any two reachable markings. 相似文献
20.
Petri nets are fundamental to the analysis of distributed systems especially infinite-state systems. Finding a particular marking corresponding to a property violation in Petri nets can be reduced to exploring a state space induced by the set of reachable markings. Typical exploration(reachability analysis) approaches are undirected and do not take into account any knowledge about the structure of the Petri net. This paper proposes heuristic search for enhanced exploration to accelerate the search. For different needs in the system development process, we distinguish between different sorts of estimates.Treating the firing of a transition as an action applied to a set of predicates induced by the Petri net structure and markings, the reachability analysis can be reduced to finding a plan to an AI planning problem. Having such a reduction broadens the horizons for the application of AI heuristic search planning technology. In this paper we discuss the transformations schemes to encode Petri nets into PDDL. We show a concise encoding of general place-transition nets in Level 2 PDDL2.2, and a specification for bounded place-transition nets in ADL/STRIPS. Initial experiments with an existing planner are presented. 相似文献