Mobile agent technology has received a large amount of attention throughout recent years because of its salient merits and promising future. But it also brings significant new security problems. Little work has been done to solve these problems through intuitive formal methods. In this paper, we proposed a new formal model of a secure mobile agent system based on an extended elementary object system (EEOS) which combines object oriented technology with Petri nets. This model has three hierarchical levels: mobile agent platform level, mobile agent level and security mechanism level. We also proposed a security mechanism - synchronous firing security mechanism to detect malicious host attacks on mobile agent code or execution flow. This paper also discusses how to translate our EEOS model to a coloured Petri Net model supported by Design/CPN and presents the simulation-based analysis of our EEOS model.

We present a new net-reduction methodology to facilitate the analysis of real-time systems using Delay Time Petri Nets (DTPNs). Net reduction is one of the most important techniques for reducing the state-explosion problem of Petri nets. However, the application of net reduction to current timed-extensions of Petri nets (such as Merlin's Time PNs) is very limited due to the difficulty faced in the preservation of timing constraints. To overcome this problem, we introduce DTPNs which are inspired by Merlin's (1976) Time PNs, Senac's (1994) Hierarchical Time Stream PNs, and Little's (1991) Timed PNs. We show that DTPNs are much more suitable for net reduction. Then, we present a new set of DTPN reduction rules for the analysis of schedule and deadlock analysis. Our work is distinct from the others since our goal is to analyze real-time systems and the reduction methods we propose preserve both timing properties (schedule) and deadlock. To evaluate our framework, we have implemented an automated analysis tool whose main functions include net reduction and class-graph generation. The experimental results show that our net-reduction methodology leads to a significant contribution to the efficient analysis of real-time systems.

Despite their attractive properties, networked virtual environments (net-VEs) are notoriously difficult to design, implement, and test due to the concurrency, real-time and networking features in these systems. Net-VEs demand high quality-of-service (QoS) requirements on the network to maintain natural and real-time interactions among users. The current practice for net-VE design is basically trial and error, empirical, and totally lacks formal methods. This paper proposes to apply a Petri net formal modeling technique to a net-VE-NICE (narrative immersive constructionist/collaborative environment), predict the net-VE performance based on simulation, and improve the net-VE performance. NICE is essentially a network of collaborative virtual reality systems called the CAVE-(CAVE automatic virtual environment). First, we introduce extended fuzzy-timing Petri net (EFTN) modeling and analysis techniques. Then, we present EFTN models of the CAVE, NICE, and transport layer protocol used in NICE: transmission control protocol (TCP). We show the possibility analysis based on the EFTN model for the CAVE. Then, by using these models and design/CPN as the simulation tool, we conducted various simulations to study real-time behavior, network effects and performance (latencies and jitters) of NICE. Our simulation results are consistent with experimental data.

This paper is concerned with a Petri net model having fuzzy timing and fuzzy real-time temporal logic. In an earlier paper, we introduced a Petri net model with four fuzzy set theoretic functions of time but no algorithms were given for computing the two important operators called, earliest and latest. In this paper, we first present algorithms for performing these two operations on fuzzy functions of time. Then we extend the existing concept of (real-time) metric temporal logic to fuzzy metric temporal logic by expressing the metrics for state and time constraints in terms of fuzzy possibility distributions. Finally we combine the two concepts of fuzzy-timing Petri net and fuzzy metric temporal logic to introduce a new Petri net model called the temporal-logic fuzzy-timing Petri net (TLFTN). The paper concludes with an algorithm and illustrative example for model checking using TLFTNs. © 1999 John Wiley & Sons, Inc.

This paper presents a method for modeling of communication protocols using G-Nets — an object-based Petri net formalism. Our approach focuses on specification of one entity in one node at one time, with the analysis that allows consideration of other layers and nodes in addition to module analysis. We extend G-Nets by the notion of timers, which aids the construction of protocol software models. Our method prevents some types of potential deadlocks and livelocks from being introduced into the produced net models. We present certain net synthesis rules to prevent some potential design errors by including error cases in the model. Thus, our node (site) interplay modeling includes cases in which a message may arrive corrupted or can be lost entirely before it would get to its destination node. Also, since our models have deadlock-preserving skeletons, the verification of global deadlock non-existence can be performed on the less complex skeleton rather than on the full G-Net model. Our analysis method discovers some deadlocks plus other unacceptable markings, which do not allow restoration of the initial state. Finding potential livelocks or overspecification is also a part of the analysis.

This paper presents a new fine-grained temporal Petri net model for distributed multimedia synchronization that can handle fuzzy temporal requirements and facilitate to verify the possibility of satisfying QoS requirements. We present a procedure for constructing the fine-grained model, starting from a set of relative temporal relations among multimedia objects. And we give an approach to infer unknown durations. Finally, we discuss how to model intra-stream and inter-stream synchronizations so as to guarantee the QoS.

The state-explosion problem of formal verification has obstructed its application to large-scale software systems. In this article, we introduce a set of new condensation theories: IOT-failure equivalence, IOT-state equivalence, and firing-dependence theory to cope with this problem. Our condensation theories are much weaker than current theories used for the compositional verification of Petri nets. More significantly, our new condensation theories can eliminate the interleaved behaviors caused by asynchronously sending actions. Therefore, our technique provides a much more powerful means for the compositional verification of asynchronous processes. Our technique can efficiently analyze several state-based properties: boundedness, reachable markings, reachable submarkings, and deadlock states. Based on the notion of our new theories, we develop a set of condensation rules for efficient verification of large-scale software systems. The experimental results show a significant improvement in the analysis large-scale concurrent systems.

A new high level Petri net (HLPN) model is introduced as a graphical syntax for Horn clause logic (HCL) programs. We call these nets: Horn clause logic goal directed nets (HCLGNs). It is shown that there is a bijection between the queried definite programs and the class of HCLGNs. In addition, a visualization of SLD resolution is realized through the enabling and firing rules and net markings. The correctness of these rules with respect to SLD resolution is also proven. We model SLD refutations and failing computations. It is shown how HCLGNs can be used to model built in atoms and provide a new AND/OR parallel execution model. Recently, several software packages (graphical editors) have become available for editing and executing HLPNs. The simulation capabilities of the HLPN software offer opportunities to perform automated, interactive code walk throughs and also have potential for providing a framework for visual debugging environments. However, HCLGNs differ from the major classes of HLPNs for which software tools have been developed in primarily two ways: the tokens in the markings can have variables; and the firing of a transition may not only update the marking of the adjacent places, but may instantiate variables in tokens in the markings of places that are non adjacent to the fired transition. Thus, the existing packages can only provide graphical syntax editing and are not appropriate for graphical simulation of HCLGNs. We provide an algebraic characterization of HCLGNs that can serve as a design guideline for implementing HCLGNs.

As part of our continuing research on using Petri nets to support automated analysis of Ada tasking behavior, we have investigated the application of Petri net reduction for deadlock analysis. Although reachability analysis is an important method to detect deadlocks, it is in general inefficient or even intractable. Net reduction can aid the analysis by reducing the size of the net while preserving relevant properties. We introduce a number of reduction rules and show how they can be applied to Ada nets, which are automatically generated Petri net models of Ada tasking. We define a reduction process and a method by which a useful description of a detected deadlock state can be obtained from the reduced net's information. A reduction tool and experimental results from applying the reduction process are discussed.

In many real-time control systems, inputs to a controller are signals from sensors and outputs of a controller are stimulators of devices. The controller must respond to the signals and function as fast as possible. Predicate-logic rule-based (expert) systems are too slow for use in real-time control applications. In this paper, the authors investigate Petri-net methods for reasoning in propositional logic, as a special case of predicate-logic Petri-net methods. The authors' algorithm based on the Petri net fixpoint can deduce all logically implied propositions (or control signals) with the time complexity O(n/sup 2/*m), where n is de number of rules and m is the number of propositions in the system.

This paper presents an application of the concepts of siphons (deadlocks) and inhibitor arcs in Petri net theory to logic programs with negations. More specifically, an extended Petri net is used to model function-free normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary applications of firing rule may cause a contradictory situation. We suggest two directions to avoid contradictions: greedy and secure applications of firing rule. We choose the secure application and show that this is a direct translation of the well-founded semantics in the net model. Furthermore, we show that the greatest unfounded set corresponds to the greatest siphon in Petri net theory when we delete the transitions disabled by the secure application of firing rule, and that the property of siphon simplifies the computation of well-founded semantics for logic programs. We also propose the reduced-Petri-net method by which we can reduce an extended Petri net to a Petri net without inhibitor arcs and compute the well-founded model by iterative applications of this transformation using conventional application of firing rule.>

Petri nets have been proposed as a promising tool for modeling and analyzing concurrent-software systems such as Ada programs and communication protocol software. Among analysis techniques available for Petri nets, the most general approach is to generate all possible states (markings) of the system in a form of a so-called reachability graph. However, this conventional reachability graph approach is inefficient or intractable, even for a bounded Petri net, due to state explosion in many practical applications. To cope with this problem, this paper proposes a method for constructing a hierarchically organized state space called the hierarchical reachability graph (HRG). Using the HRG, we obtain necessary and sufficient conditions for reachability and deadlock, as well as algorithms to test whether a given state or marking is reachable from the initial state and whether there is a deadlock state (a state with no successor states).>

An extended Petri net is used to model function-free logic programs with negation, i.e. normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary application of firing rules may cause a contradictory situation. The authors suggest two directions to avoid contradictions, greedy and secure application of firing rules. Secure application is a direct translation of the well-founded semantics in the net model. Furthermore, the authors show that an unfounded set corresponds to a siphon in Petri net theory when one deletes the transitions disabled by the secure application of firing rules, and that the property of siphons simplifies the computation of well-founded semantics for logic programs.>

Petri nets provide a promising framework for executing queries to logic programs. Petri net models for query processing in logic programming were initially developed by T. Murata and D. Zhang (IEEE Trans. Software Eng., vol.14, no.4, p.481-97, 1988). It is shown how this framework can be extended to be applicable to reasoning in the presence of inconsistency. This yields a Petri net model of programs that be inconsistent in classical logic. This is interesting because large expert systems may often contain inconsistent information. The Petri net method proposed suggests a robust way of preventing inconsistency from infecting a system and rendering it useless.>

The application of Petri net reduction to Ada-tasking deadlock detection is investigated. Net reduction can ease reachability analysis by reducing the size of the net while preserving relevant properties. By combining Petri net theory and knowledge of Ada-tasking semantics some specific efficient reduction rules are derived for Petri net models of Ada-tasking. A method by which a useful description of a detected deadlock state can be easily obtained from the reduced net's information is suggested.>

A model for analyzing a FCS (fault-tolerant clock synchronization) system of the type supported by a statistical self-diagnosis is described. Once a self-diagnosis scheme is integrated into an FCS design, the problem of controlling and measuring the system's self-stability arises. A stochastic Petri net (SPN) model is constructed to derive the self-stability measures of such FCS systems. An example is given to demonstrate the entire modeling and analyzing procedure. The mapping from SPN model to Markov model shown in an example can be automated by using an SPN software package. The results show that the SPN model is an excellent tool for obtaining self-stability measures and that several important system features, such as synchronization and parallelism, can be modeled using the SPN method in a much clearer manner than they can be modeled using other available tools.>

An approach for automated modeling and verification of communication protocols is presented. A language that specifies the input/output behavior of protocol entities is introduced as the starting point of the approach, and verification of the linguistic specifications is discussed. Rules for conversion of the specifications into a Petri net model (based on a timed Petri net) are presented and illustrated by examples. This leads to a second level of verification on the net model. The approach is illustrated by its application to a part of the LAPD protocol.>

An approach for automated modeling and verification of communication protocols is presented. A language that specifies input/output behavior of protocol entities is introduced as the starting point, and some verification of the specifications is discussed. Further verification is aided by translation of the specifications to a timed Petri net model.>

Starts with a brief review of the history and the application areas considered in the literature. The author then proceeds with introductory modeling examples, behavioral and structural properties, three methods of analysis, subclasses of Petri nets and their analysis. In particular, one section is devoted to marked graphs, the concurrent system model most amenable to analysis. Introductory discussions on stochastic nets with their application to performance modeling, and on high-level nets with their application to logic programming, are provided. Also included are recent results on reachability criteria. Suggestions are provided for further reading on many subject areas of Petri nets.>

A method is presented for detecting deadlocks in Ada tasking programs using structural; and dynamic analysis of Petri nets. Algorithmic translation of the Ada programs into Petri nets which preserve control-flow and message-flow properties is described. Properties of these Petri nets are discussed, and algorithms are given to analyze the nets to obtain information about static deadlocks that can occur in the original programs. Petri net invariants are used by the algorithms to reduce the time and space complexities associated with dynamic Petri net analysis (i.e. reachability graph generation).>

A proof procedure and answer extraction in a high-level Petri net model of logic programs is discussed. The logic programs are restricted to the Horn clause subset of first-order predicate logic and finite problems. The logic program is modeled by a high-level Petri net and the execution of the logic program or the answer extraction process in predicate calculus corresponds to a firing sequence which fires the goal transition in the net. For the class of the programs described above, the goal transition is potentially firable if an only if there exists a nonnegative T-invariant which includes the goal transition in its support. This is the main result proved. Three examples are given to illustrate in detail the above results.>

A predicate/transition net model for a subset of Horn clause logic programs is presented. The syntax, transformation procedure, semantics, and deduction process for the net model are discussed. A possible parallel implementation for the net model is described, which is based on the concepts of communicating processes and relations. The proposed net model offers a syntactical variant of Horn clause logic and has two distinctions from other existing schemes for the logic programs: representation formalism and the deduction method. The net model provides an approach towards the solutions of the separation of logic from control and the improvement of the execution efficiency through parallel processing for the logic programs. The abstract nature of the net model also lends itself to different implementation strategies.>

This paper presents a new data flow computer architecture using two types of memory: program memory and token memory. The program memory (PM) stores a data flow program or graph indicating data dependencies among instructions. The PM need not be changed during execution of one program and is duplicated for each processing or functional unit. The token memory (TM) stores mainly currently needed data values and plays a role similar to accumulators or registers in conventional computers. The size of the TM is expected to be relatively small because the data values occupy space in the TM for a very short time. The small scale TM in our architecture makes it possible to reduce the complexity of the switch mechanism between functional units and memories, and the size of the control circuit.

This paper presents a method for synthesizing or growing live and safe marked graph models of decision-free concurrent comutations. The approach is modular in the sense that subsystems r represented by arcs (and nodes) are added one by one without the need of redesigning the entire system. The foliowing properties of marked graph models can be prescribed in the synthesis: liveness (absence of deadlocks), safeness (absence of overflows), the number of reachability classes, the maximum resource (temporary storage) requirement, computation rate (performance), as well as the numbers of arcs and states.

This paper presents a method for synthesizing marked graph models of decision-free concurrent computations. The approach is modular in the sense that subsystems represented by arcs (and nodes) are added one by one without the need of redesigning the entire system. The following properties of marked graph models can be prescribed in the synthesis: liveness (absence of deadlocks), safeness (absence of overflows), the number of reachability classes, the maximum resource (temporary storage) requirement, computation rate (performance), as well as the numbers of arcs and states.