3 - S-systems and T-systems

Summary

This chapter presents the main results of the theory of S-systems and T-systems. It is divided into two sections of similar structure, one for each of these two classes. The main results of each section are a Liveness Theorem, which characterizes liveness, a Boundedness Theorem, which characterizes b-boundedness of live systems, and a Reachability Theorem, which characterizes the set of reachable markings of live systems. Additionally, both sections contain a Shortest Sequence Theorem, which states that every reachable marking can be reached by an occurrence sequence whose length is bounded by a small polynomial in the number of transitions of the net (linear in the case of S-systems and quadratic for T-systems).

S-systems

Recall from the Introduction that S-systems are systems whose transitions have exactly one input place and one output place.

Definition 3.1S-nets, S-systems

A net is an S-net if |^•t| = 1 = |t^•| for every transition t.

A system (N, M₀) is an S-system if N is an S-net.

The fundamental property of S-systems is that all reachable markings contain exactly the same number of tokens. In other words, the total number of tokens of the system remains invariant under the occurrence of transitions.

Proposition 3.2Fundamental property of S-systems

Let (N, M₀) be an S-system. If M is a reachable marking, then M₀(S) = M(S), where S is the set of places of N.