System modelling with high-level Petri nets

The paper presents a high-level Petri net model of concurrent systems called predicate /transition-nets (PrT-nets). Its places represent variable properties of, or relations between, individuals; they are ‘predicates’ with variable extension. The transitions represent classes of elementary changes of those extensions. The model is introduced on the basis of a simple example from resource management. The central part of the paper is devoted to linear-algebraic techniques for verifying invariant assertions, yielding a calculus of S-invariants for PrT-nets. Finally, these modelling and analysis techniques are applied to a scheme for organizing a distributed data base taken from literature.     

Parallel program design using high-level Petri nets

Petri nets are proposed as a general-purpose design and modelling tool for parallel programs. The advantages of Petri nets for this purpose are discussed, and a solution to the Dining Philosophers problem is developed using simple Place-Transition nets. The limitations of Place-Transition nets are described, and the Dining Philosophers problem is used to illustrate how Coloured Petri nets can overcome these limitations. A more complex example of a Coloured Petri net is then given, and it is shown how a collection of processes in the Occam programming language can be developed directly from the properties of the net. Another Petri net model of a simple process farm is given, and a solution is developed in Parallel C: this further highlights the suitability of Petri nets as a design tool for parallel programs.     

Reinforcement learning for high-level fuzzy Petri nets

The author has developed a reinforcement learning algorithm for the high-level fuzzy Petri net (HLFPN) models in order to perform structure and parameter learning simultaneously. In addition to the HLFPN itself, the difference and similarity among a variety of subclasses concerning Petri nets are also discussed. As compared with the fuzzy adaptive learning control network (FALCON), the HLFPN model preserves the advantages that: 1) it offers more flexible learning capability because it is able to model both IF-THEN and IF-THEN-ELSE rules; 2) it allows multiple heterogeneous outputs to be drawn if they exist; 3) it offers a more compact data structure for fuzzy production rules so as to save information storage; and 4) it is able to learn faster due to its structural reduction. Finally, main results are presented in the form of seven propositions and supported by some experiments.     

A methodology of testing high-level Petri nets

Petri nets have been extensively used in the modelling and analysis of concurrent and distributed systems. The verification and validation of Petri nets are of particular importance in the development of concurrent and distributed systems. As a complement to formal analysis techniques, testing has been proven to be effective in detecting system errors and is easy to apply. An open problem is how to test Petri nets systematically, effectively and efficiently. An approach to solve this problem is to develop test criteria so that test adequacy can be measured objectively and test cases can be generated efficiently, even automatically. In this paper, we present a methodology of testing high-level Petri nets based on our general theory of testing concurrent software systems. Four types of testing strategies are investigated, which include state-oriented testing, transition-oriented testing, flow-oriented testing and specification-oriented testing. For each strategy, a set of schemes to observe and record testing results and a set of coverage criteria to measure test adequacy are defined. The subsumption relationships and extraction relationships among the proposed testing methods are systematically investigated and formally proved.     

A reasoning algorithm for high-level fuzzy Petri nets

We introduce an automated procedure for extracting information from knowledge bases that contain fuzzy production rules. The knowledge bases considered here are modeled using the high-level fuzzy Petri nets proposed by the authors in the past. Extensions to the high-level fuzzy Petri net model are given to include the representation of partial sources of information. The case of rules with more than one variable in the consequent is also discussed. A reasoning algorithm based on the high-level fuzzy Petri net model is presented. The algorithm consists of the extraction of a subnet and an evaluation process. In the evaluation process, several fuzzy inference methods can be applied. The proposed algorithm is similar to another procedure suggested by Yager (1983), with advantages concerning the knowledge-base searching when gathering the relevant information to answer a particular kind of query     

Fuzzy rule base systems verification using high-level Petri nets

In this paper, we propose a Petri nets formalism for the verification of rule-based systems. Typical structural errors in a rule-based system are redundancy, inconsistency, incompleteness, and circularity. Since our verification is based on Petri nets and their incidence matrix, we need to transform rules into a Petri nets first, then derive an incidence matrix from the net. In order to let fuzzy rule-based systems detect above the structural errors, we are presenting a Petri-nets-based mechanism. This mechanism consists of three phases: rule normalization, rules transformation, and rule verification. Rules will be first normalized into Horn clauses, then transform the normalized rules into a high-level Petri net, and finally we verify these normalized rules. In addition, we are presenting our approach to simulate the truth conditions which still hold after a transition firing and negation in Petri nets for rule base modeling. In this paper, we refer to fuzzy rules as the rules with certainty factors, the degree of truth is computed in an algebraic form based on state equation which can be implemented in matrix computation in Petri nets. Therefore, the fuzzy reasoning problems can be transformed as the liner equation problems that can be solved in parallel. We have implemented a Petri nets tool to realize the mechanism presented fuzzy rules in this paper.     

进路建立过程的时间有色petri网建模与仿真

计算机联锁软件作为计算机联锁系统的核心主控软件,可靠性和安全性需建立在好的安全模型之上,提出了采用时间有色Petri网对进路建立的具体过程进行形式化建模,时间戳可以得知联锁设备的精确动作时刻以及操作持续时间,通过CPN Tools进行编辑和仿真,以VC++6.0为开发环境完成代码编写进行验证,体现时间有色Petri网描述联锁系统逻辑和性能特性的特点,以便在软件开发初期尽早发现系统的设计错误或缺陷,突出采用时间有色Petri网建模的可靠性和安全性。     

Application of high-level fuzzy Petri nets to educational grading system

For the purpose of understanding the students’ learning achievement, the most direct way is to implement a test. Due to the rapid development of information technology, all kinds of combination of information technology with the adaptive test have been incessantly noted by many scholars. In general, the computerized adaptive test includes the item response theory that tests the students’ learning ability of subjects. However, the results based only on the dichotomy of correct answers and wrong answers are not so comprehensive judgments. Situations of correct answers and wrong answers should be different in their degrees; for example, completely correct, partially correct, completely wrong, and partially wrong. But the partially correct or partially wrong is vague and difficult to define. Thus it is appropriate to use fuzzy theory to solve the vagueness problem. Therefore, this study presents a novel learning evaluation model which applies high-level fuzzy Petri net (HLFPN) and infers via a fuzzy reasoning method the different answering performances generated by different examinee’s abilities corresponding to the test items in different degrees of difficulty. Finally, we synthesize the answering performance of every test item and make a reasonable evaluation.     

Timed petri nets in modeling and analysis of simple schedules for manufacturing cells

It is shown that a large class of flexible manufacturing cells can be modeled using timed Petri nets. Net models of simple schedules (i.e., schedules in which exactly one part enters and one leaves the cell during each cycle) are conflict-free nets. Two complementary approaches to analysis of such models are presented: invariant analysis and throughput analysis. Invariant analysis provides analytic (or symbolic) solutions for the cycle time of a cell analyzing (invariant) subnets of the original net. Throughput analysis performs a series of performance-preserving net reductions to simplify the original model. Several directions for further research are indicated.     

Modeling and verification of the SDL-specified communication protocols using high-level Petri nets

To simplify modeling and verification of communication protocols presented in the SDL language, the so-called hierarchical typed timed Petri nets (HTT nets), which are substantial modifications of colored Petri nets, are introduced. A method of translation of the SDL language into HTT nets is described. A program complex SPV (SDL Protocol Verifier), which includes a translator from SDL into HTT nets and means for editing, simulation, visualization, and verification of these net models, is presented. For the verification, a model checking method for properties presented by μ-calculus formulas is used. Experiments on application of the SPV complex for modeling and verifying two ring protocols (RE and ATMR protocols), an optimized version of the sliding window protocol (i-protocol), and a dynamic version of the InRes protocol are described     

Giving semantics to SA/RT by means of high-level timed Petri nets

In the IPTES project a dual language approach is proposed for overcoming both the problems derived from the use of a user-friendly, high-level, but not-formally-defined language and from a lower-level, formal, but difficult-to-use language. The approach uses a user-friendly, high-level language as user interface and a lower-level, formal language asmachine language. In this way the users can both access the IPTES environment through a nice interface and can profit from non-ambiguity-checks and proofs algorithms based on the formal kernel machine language. The correspondence between the two languages is built-in in the IPTES environment that provides a transparent mapping mechanism that relates the users specifications expressed by means of the high-level interface-language with the formal definitions expressed in the formal machine language.This paper presents the mapping mechanism that relates the current IPTES user interface (SA/RT (Ward and Mellor 1985)) with the IPTES machine language (high-level timed Petri nets (Ghezzi, Mandrioli, Morasca and Pezzé 1991)). As a side effect, it also presents the formal semantics of SA/RT defined by means of high-level timed Petri nets.This material is based upon work supported by the CEC under the ESPRIT program project no. EP5570 IPTES, by the Piano Finalizzato Sistemi Informatici e Calcolo Parallelo (CNR) and by The Technical Development Centre of Finland (TEKES).     

Distributed dynamic programming using concurrent object-orientedness with actors visualized by high-level Petri nets

This paper deals with application of concurrent object-oriented programming with Actors to solve dynamic programming problems in a distributed computing environment. This area of research is often called distributed artificial intelligence. Using a dynamic programming example of chained matrix multiplication, a method of managing dynamic programming searches in a distributed programming environment with Actors is presented. Distributed computations with Actors are visualized by means of Time-Varying Automata (for cases with no intra-actor concurrency) or using a class of high-level nets called Hierarchical Colored Petri Nets (for cases with intra-actor concurrency). Design and implementation features of the specific Actor-based programming environment, using a concurrent extension of C++, are also discussed.     

A model of fuzzy spatio-temporal knowledge representation and reasoning based on high-level Petri nets

In many application areas there is a need to represent human-like knowledge related to spatio-temporal relations among multiple moving objects. This type of knowledge is usually imprecise, vague and fuzzy, while the reasoning about spatio-temporal relations is intuitive. In this paper we present a model of fuzzy spatio-temporal knowledge representation and reasoning based on high-level Petri nets. The model should be suitable for the design of a knowledge base for real-time, multi-agent-based intelligent systems that include expert or user human-like knowledge. The central part of the model is the knowledge representation scheme called FuSpaT, which supports the representation and reasoning for domains that include imprecise and fuzzy spatial, temporal and spatio-temporal relationships. The scheme is based on the high-level Petri nets called Petri nets with fuzzy spatio-temporal tokens (PeNeFuST). The FuSpaT scheme integrates the theory of the PeNeFuST and 117 spatio-temporal relations.The reasoning in the proposed model is a spatio-temporal data-driven process based on the dynamical properties of the scheme, i.e., the execution of the Petri nets with fuzzy spatio-temporal tokens. An illustrative example of the spatio-temporal reasoning for two agents in a simplified robot-soccer scene is given.     

Enhanced high-level Petri nets with multiple colors for knowledgeverification/validation of rule-based expert systems

Exploring the properties of rule-based expert systems through Petri net models has received a lot of attention. Traditional Petri nets provide a straightforward but inadequate method for knowledge verification/validation of rule-based expert systems. We propose an enhanced high-level Petri net model in which variables and negative information can be represented and processed properly. Rule inference is modeled exactly and some important aspects in rule-based systems (RBSs), such as conservation of facts, refraction, and closed-world assumption, are considered in this model. With the coloring scheme proposed in this paper, the tasks involved in checking the logic structure and output correctness of an RES are formally investigated. We focus on the detection of redundancy, conflicts, cycles, unnecessary conditions, dead ends, and unreachable goals in an RES. These knowledge verification/validation (KVV) tasks are formulated as the reachability problem and improper knowledge can be detected by solving a set of equations with respect to multiple colors. The complexity of our method is discussed and a comparison of our model with other Petri net models is presented.     

Modeling, scheduling and simulation of product development process by extended stochastic high-level evaluation Petri nets

This paper presents a methodology for modeling and simulating product development process-based on the extended stochastic high-level evaluation Petri nets (ESHLEP-N). A product development process is composed of many design activities and the ESHLEP-N model can describe some special features of design activity in detail, such as randomness of its duration, uncertainty of its interruption and complexity of design iteration. Therefore, the ESHLEP-N model is employed to simulate a product development process. The initial product development plan obtained by a mathematical method beforehand is taken as the input of the simulation. Then the simulation procedure is proposed, along with four types of rules, i.e. activity-sequencing rules, resource-assigning rules, state-changing rules and the simulation-terminating rule, for scheduling the design activities. An example of the development process of an automobile drive system in concurrent engineering environment is presented to illustrate the method of the ESHLEP-N-based modeling, simulation procedure and scheduling rules. The simulation results show that the simulation procedure and the scheduling rules are effective.     

Timed CSP = Closed Timed Automata

We study the expressive power of an augmented version of Timed CSP and show that it is precisely equal to that of closed timed automatatimed automata with closed invariant and enabling clock constraints. We also show that this new version of Timed CSP is expressive enough to capture the most widely used specifications on timed systems as refinements between processes, and moreover that refinement checking is amenable to digitisation analysis. As a result, we are able to verify some of the most important timed specifications, including branching-time liveness properties such as timestop-freedom and constant availability, using the model checker FDR (a commercial product of Formal Systems (Europe) Ltd.).     

时间符号迁移图及其互模拟判定

引入时间符号迁移图的概念，作为既涉及通讯又具有实时性的并发系统的模型，该文给出了这种迁移图时间互模拟的算法，并证明了该算法的正确性。     

M-nets: An algebra of high-level Petri nets, with an application to the semantics of concurrent programming languages

This paper describes a high-level Petri net model called M-nets (for modular multilabelled nets). A distinctive feature of this model is that it allows both: unfolding, as do most other high-level net models; and composition – in particular, synchronisation – in a process algebraic style, turning the set of M-nets into an algebraic domain. It turns out that the composition operations of this domain have various algebraic properties. Moreover, the model is such that composition operations are coherent with unfolding, in the sense that the unfolding of a composite high-level net is the composition of the unfoldings of its components. One of the motivations for M-nets is that they be a vehicle for giving semantics of concurrent programming languages. To illustrate their capability for that, the compositional semantics of – a simple, expressive concurrent programming language – is given. An associated low-level net semantics is described, and the coherence of these high-level and low-level semantics is proved. Received: 20 November 1996 / 13 January 1998     

Timed Semantics of Message Sequence Charts Based on Timed Automata

Message Sequence Charts (MSCs) provide a way for quick and easily understandable modelling of concurrent systems. Apart from their intuitive semantics easily deduced from their visual syntax, there is a formally defined semantics—Unfortunately, the semantics intuitively assigned to them is sometimes at odds with the formal semantics. In this paper, we will show an alternative approach to the semantics of MSCs, which will enable us to formally model their timed behaviour. Furthermore, we show how some generalizations of ordering events can lead to a language better suited to model real-world requirements. To ease the task of analyzing (High-Level) MSCs, we identify a subclass of those which can be translated into finite (timed of untimed) automata and specify the translation, thus laying the foundation for model checking.