Petri nets have been proposed as a simple and convenient formalism for modeling systems that exhibit parallel and concurrent activities [Ag79, Pe81, Re85, Mu89]. In Petri nets, these activities are represented by the so called tokens which can move within a (static) graph-like structure of the net. More formally, a marked (place/transition) Petri net M contains two basic components, ... the structure N, which is a bipartite directed graph (i.e., a graph with two types of nodes, called places and transitions), and an initial marking function m0, which assigns nonnegative numbers of tokens to places of the net, M = (N, m0), N = (P, T, A), m0 : P -> {0,1,...}. The directed arcs connect places with transitions and transitions with places. Place/transition Petri net models are also known as `condition/event' systems as places usually represent conditions (in the most general sense), while transitions -- events.
If a nonzero number of tokens is assigned to a place, the place is `marked', which means that the condition represented by it is satisfied. If all places connected by directed arcs to a transition are marked, the transition is `enabled' and can fire (or the event represented by this transition can occur). Firing a transition is an instantaneous event which removes (simultaneously) a single token from each of the input places of the transition and adds a single token to each of the transition's output places. This creates a new marking function of a net, a new set of enabled transitions, and so on. The set of all possible marking functions which can be derived in such a way is called the set of reachable markings (or the forward marking class) of a net. This set can be finite or infinite; if it is finite, the net is bounded.
An important extension of the basic net model is addition of inhibitor arcs [AF73, Va82]. Inhibitor arcs (which connect places with transitions) provide a `test if zero' condition which is nonexistent in the basic Petri net. Nets with inhibitor arcs are usually called inhibitor nets. In inhibitor nets, a transition is enabled only if all places connected to it by directed arcs are marked and all places connected by inhibitor arcs are empty (i.e., not marked). Formally, the set of inhibitor arcs B is an additional element of the net structure, N = (P, T, A, B), and usually the same place cannot be connected by a directed and inhibitor arc with the same transition.
Another popular extension of the basic model is to allow multiple arcs between places and transitions. A transition is enabled in such nets only if the number of tokens is at least equal to the number of directed arcs between a place and a transition. Formally this extension can be described by a `weight function' w which maps the set of directed arcs A into the set of positive numbers, N = (P, T, A, B, w), w : A -> {1,2,...}. It should be observed that inhibitor arcs could be included in the same description as arcs with the weight equal to zero, but it appears that separating the set of inhibitor arcs from the set of directed arcs is a more convenient approach.
In (ordinary) nets the tokens are indistinguishable, so their distribution can conveniently be described by a marking function which maps the set of places into the set on nonnegative integer numbers. In colored Petri nets [Je87], tokens have attributes called colors. Token colors can be quite complex, for example, they can describe the values of (simple or structured) variables or the contents of message packets. Token colors can be modified by (firing) transitions and also a transition can have several different occurrences (or variants) of firing. The basic idea of colored nets is to `fold' an ordinary Petri net. The original set of places is partitioned into a set of disjoint classes, and each class is replaced by a single place with token colors indicating which of the original places the tokens belong to. Similarly, the original set of transitions is partitioned into a set of disjoint classes, and each class is replaced by a single transition with occurrences indicating which of the original transitions the firing corresponds to. Any partition of places and transitions will result in a colored net. One of the extreme partitions will combine all original places into one place, and all original transitions into one transition; this will create a very simple net (one place and one transition only) but with quite complicated rules describing the use of colors. The other extreme partition will create one--element classes of places and transitions, so the colored net will be isomorphic to the original net, with only one color. To be useful in practice, colored nets must constitute a reasonable balance between these two extreme cases.
In order to study performance aspects of Petri net models, the duration of activities must also be taken into account and included into model specifications. Several types of Petri nets `with time' have been proposed by assigning `firing times' to the transitions or places of a net. In timed nets, firing times are associates with transitions, and transition firings are `real-time' events, i.e., tokens are removed from input places at the beginning of the firing period, and they are deposited to the output places at the end of this period (sometimes this is also called a `three-phase' firing mechanism as opposed to `one-phase' instantaneous firings of transitions). All firings of enabled transitions are initiated in the same instants of time in which the transitions become enabled (although some enabled transition cannot initiate their firing; for example, all transitions in a free-choice class can be enabled, but only one can fire). If, during the firing period of a transition, the transition becomes enabled again, a new, independent firing can be initiated, which will `overlap' with the other firing(s). There is no limit on the number of simultaneous firings of the same transition (sometimes this is called `infinite firing semantics'). Similarly, if a transition is enabled `several times' (i.e., it remains enabled after initiating a firing), it may start several independent firings in the same time instant.
In timed nets, the firing times of some transitions may be equal to zero, which means that the firings are instantaneous; all such transitions are called immediate (while the other are called timed). Since the immediate transitions have no tangible effects on the (timed) behavior of the model, it is convenient to `split' the set of transitions into two parts, the set of immediate and the set of timed transitions, and to fire first the (enabled) immediate transitions, and then (still in the same time instant), when no more immediate transitions are enabled, to start the firings of (enabled) timed transitions. It should be noted that such a convention effectively introduces the priority of immediate transitions over the timed ones, so the conflicts of immediate and timed transitions should be avoided. The firing times of transitions can be either deterministic or stochastic (i.e., described by some probability distribution function); in the first case, the corresponding timed nets are referred to as D-nets, in the second, for the (negative) exponential distribution of firing times, the nets are referred to as M-nets (Markovian nets). In both cases, the concepts of state and state transitions have been formally defined and used in the derivation of different performance characteristics of the model [Zu91]. Analysis of net models can be based on their behavior (i.e., the set of reachable states) or on the structure of the net; the former is called reachability analysis while the latter -- structural analysis. Invariant analysis seems to be the most popular example of the structural approach. Structural methods eliminate the derivation of the state space, so they avoid the `state explosion' problem of reachability analysis, but they cannot provide as much information as the reachability approach does. Quite often, however, all the detailed results of reachability analysis are not really needed, and more synthetic performance measures, that can be provided by structural methods, are quite satisfactory. Both reachability and structural analyses are based on quite detailed net characterizations. Consequently, only very simple models can be analyzed manually; for more realistic models, software tools for analysis of net models are needed. It is, therefore, not surprising that many different tools have been developed for analysis of a variety of net types [Fe93]. A collection of software tools developed for analysis timed Petri net models, TPN-tools, uses the same internal representation of models and a common `language' for the description of modeling nets. This paper describes the structure of model specifications (i.e., the `input language'), provides several examples of net descriptions, discusses net analyses supported by the tools, and provides some performance results obtained for simple examples.