Semiflows, Home Spaces, and Home States, Applications to the Analysis of Parameterized Petri nets Gerard Memmi Abstract After rapidly recalling basic notations relatively to semiflows and Petri nets, we define ℱ \mathcal{F} , the set of semiflows over ℤ \mathbb{Z} that we associate with a specific class of invariants. We then focus on ℱ + \mathcal{F^{+}} , the set of semiflows with non-negative coordinates which are important to study the behavior of a Petri net. We recall known behavioral properties attached to semiflows in ℱ + \mathcal{F^{+}} that we associate with two sets of bounds regarding boundedness then liveness. We recall the notions of home states and home spaces for which we regrouped old and new properties. We introduce a new result on the decidability of liveness under the existence of a home state. The notions of minimality of semiflows and minimality of supports allow us to define generating sets that are particularly critical to develop an effective analysis of invariants and behavioral properties of Petri nets such as boundedness or even liveness. We also recall three known decomposition theorems considering ℕ \mathbb{N} , ℚ + \mathbb{Q^{+}} , and ℚ \mathbb{Q} respectively where the decomposition over ℕ \mathbb{N} is being improved with a necessary and sufficient condition. We use the notion the notion of generating sets to show that extremums linked to the set of bounds mentioned here above, are indeed computable by providing their values. Two related Petri net modeling arithmetic operations (one of which represents an Euclidean division) illustrate how results on semiflows and home spaces can be methodically used in efficiently analyzing the liveness of the parameterized model and underlining the efficiency brought by the combination of these results. 1 Introduction 1.1 Motivations Parallel programs, distributed digital systems, telecommunication networks, or cyber-physical systems are entities that are complex to design, model, and verify. Using formal verification at different stages of the system development life cycle is a strong motivation and provides us with the rationale for revisiting the notions of semiflows and home spaces and illustrate through examples how they can be combined to analyze behavioral properties of Petri nets. In this regard, invariants are of paramount importance as they are almost systematically used in system specifications to describe specific behavioral properties. One can argue that properties such as liveness, deadlock freeness, or boundedness are in some way invariants since they must hold regardless of the evolution of the digital system under study. Often, engineers and researchers will try to prove that a formula belonging to a system specification is an invariant, meaning that the formula holds during any possible evolution of their model. But, can we find a way by which invariants or at least a meaningful subset of invariants can be organized and concisely described, and some of them can be discovered by computation? Such invariants that do not belong in the system specification, can just express a sub-property of a more complex known one; however, they also can reveal an under-specified model or an unsuspected function of the system under study (which in turn, could constitute a component of a security breach). In this paper, we provide some elements to answer this question and show how basic arithmetic, linear algebra, or algebraic geometry can efficiently support invariant calculus. One of our motivations is to go beyond regrouping in a kind of survey, a number of known algebraic results dispersed throughout the Petri nets literature, but also to introduce improved and new results. We illustrate how engineers can methodically proceed in their analysis through two parameterized Petri nets. This paper can be considered as a continuation of the work started in [ 44 ] and an extensive rewriting of [ 43 ] , providing in particular a better positioning between semiflows and and its associated set of invariants through theorem ( 3.1 ). A conjecture proposed in [ 43 ] is solved for state machines, a subclass of Petri nets although negatively negatively for the general case through a counterexample. We want to show how linear algebra or algebraic geometry can efficiently be applied and utilized to prove a large variety of behavioral properties, sometimes with simple arithmetic reasoning even when Petri net or colored Petri nets ( [ 28 ] ) are parameterized. This type of methodical reasoning can be useful to engineers in order to determine in which domain of these parameters, behavioral properties can be satisfied. 1.2 Outline and contributions After providing basic notations in Section 2 , we regroup a first set of classic properties for semiflows (over \mathbb{Z} then \mathbb{N} ) and introduce the definitions of its associated family of invariants (theorem 3.1 ) as well as two first extremums in Section 3 . The notions of home space and home state are described in Section 4 together with a set of old and new results linked to the topology of the underlying reachability graph. Later, in Section 4.2 , their key relation with liveness is described highlighting their usefulness. In particular, a new decidability result is provided for Petri nets with home states linked to Karp and Miller’s coverability tree finite construction [ 32 ] through theorem 4.2 and corollary 3 . In Section 4.3 a third extremum is defined. The notions of generating sets and minimality are briefly recalled from [ 44 ] in Section 5 . The three decomposition theorems of Section 5.2 have been first published in [ 41 ] then improved in [ 44 ] . Here, the first theorem is extended once more to fully characterize minimal semiflows and generating sets over \mathbb{N} . The other two theorems are just recalled for completeness. Subsequently, Section 5.3 , illustrating the usefulness of decomposition theorems, theorem 5.4 shows how to compute the three extremums previously defined when equipped with a generating set. It is worth noticing that the results do not depend on the chosen generating set. These important details were never stressed out before despite their importance from a computational point of view, and their impact in supporting the analysis of parameterized models. These results are used in the analysis of two examples presented in Section 6 where two parameterized examples are given to illustrate how invariants and home spaces can be associated together with basic arithmetic reasoning to methodically prove behavioral properties of a Petri net (described section 6.1 ). This section ends with a last result on home states directly drawn from the analysis of the last example. Section 7 concludes and provides a possible avenue for future research. 2 Petri nets, basic notations In this section, after describing basic mathematical notations that will be used in this paper, we briefly recall Petri nets basic definitions, including the notion of potential state space that is more usual in Transition Systems. 2.1 Notations \mathbb{S} denotes an element of \{\mathbb{N},\mathbb{Q^{+}},\mathbb{Q}\} where \mathbb{Q^{+}} is denoting the set of non-negative rational numbers. Given an ordered set A=\{a1,...an\} , a vector v=(x1,...xn)^{\top} with its coordinates in \mathbb{S} can also be seen as a function from A to \mathbb{S} with v(ai)=xi sometimes also denoted by v_{i} . The support of a vector v=(x1,...xn)^{\top} is denoted by \left\|v\right\| and is defined by: \left\|v\right\|=\{ai\in A|\ v(ai)\neq 0\}. We will abusively use the same symbol ‘0’ to denote (0,...,0)^{\top} of \mathbb{N}{{}^{n}} , for all n in \mathbb{N} . We will use the usual component-wise partial orders ( \leq\text{or}< ) between vectors in which (x_{1},x_{2},\dots,x_{d})^{\top}\leq(y_{1},y_{2},\dots,y_{d})^{\top} if and only if x_{i}\leq y_{i} , for all i\in\{1,\dots,d\} . These notations and conventions will be useful to handle the notion of semiflow in section 3 . 2.2 Petri nets A Petri net is a tuple PN=\langle P,T,Pre,Post\rangle , where P is a finite set of places and T a finite set of transitions such that P\cap T=\text{\O} . A transition t of T is defined by its \mathit{Pre(\cdot,t)} and Post(\cdot,t) conditions 1 1 1 We use here the usual notation: Pre(\cdot,t)(p)=Pre(p,t) and Post(\cdot,t)(p)=Post(p,t) . : Pre:P\times T\rightarrow\mathbb{N} is a function providing a weight for pairs ordered from places to transitions, while Post:P\times T\rightarrow\mathbb{N} is a function providing a weight for pairs ordered from transitions to places. Here, d will denote the number of places: d=|P| . A Petri net is said ordinary [ 47 ] when Pre and Post are functions from P\times T to \{0,1\} . The structure of a Petri net as a bipartite graph, is often studied in using the notion of siphons and traps (see for instance, [ 12 ] ) which are useful to analyze behavioral properties. A siphon D is a subset of places such that \forall t\in T,\ \forall p\in D, if Post(p,t)\neq 0 then \exists p^{\prime}\in D such that Pre(p^{\prime},t)\neq 0 . Similarly, a trap D is a subset of places such that \forall t\in T,\ \forall p\in D, if Pre(p,t)\neq 0 then \exists p^{\prime}\in D such that Post(p^{\prime},t)\neq 0 . The structure of a Petri net can also be constrained to characterize subclasses of Petri nets. As an example, States Machines are a particularly well-known subclass of Petri nets usually used to model sequential processes. A state machine PN=\langle P,T,Pre,Post\rangle is an ordinary Petri net such that: \forall t\in T,\ \sum_{p\in P}Pre(p,t)=\sum_{p\in P}Post(p,t)=1 A marking (or state in Transition Systems) q:\ P\to\mathbb{N} allows representing the evolution of the system along the execution (or firing ) of a transition t or of a sequence of transitions \sigma (i.e., a word in T^{*} ). Given a marking q , a place p is said to contain k tokens as q(p)=k . We say that t is enabled at marking q if and only if q\geq Pre(\cdot,t), and only an enabled transition t at q (we write that q\in\texttt{Dom}(t) ) can be executed, reaching a marking q^{\prime} computable from q such that: q^{\prime}=q+Post(\cdot,t)-Pre(\cdot,t) This is also denoted as q^{\prime}=t(q) or more traditionally q\overset{t}{\rightarrow}q^{\prime} (we also write q^{\prime}\in\texttt{Im}(t) ). Similarly, for a sequence of transitions \sigma allowing to reach a marking q^{\prime} from a marking q , we write q\overset{\sigma}{\rightarrow}q^{\prime} . If \sigma can be written \sigma=t_{1}t_{2}...t_{n} then we can compute q^{\prime}=t_{n}(...t_{1}(q)...) as the composition of the successive transitions of \sigma with the so-called state equation : q^{\prime}=q+\sum_{i=1}^{i=n}\bar{\sigma_{i}}(Post(\cdot,t_{i})-Pre(\cdot,t_{i}))=q+(Post-Pre)\bar{\sigma} (1) where Post and Pre are to be considered as matrices (often, Post-Pre is defined as the incidence matrix of PN ), \bar{\sigma}_{i} is the number of occurrences of t_{i} in \sigma , and \bar{\sigma} is the Parikh vector of \sigma that is the vector of \mathbb{N}^{|T|} such that \bar{\sigma}_{i} is the i^{th} coordinate of \sigma . When the sequence of transitions allowing to reach a marking q^{\prime} from a marking q is unknown, we may write q\overset{*}{\rightarrow}q^{\prime} . In some papers, \overset{*}{\rightarrow} denotes the reachability relation between markings. We also define Q , the set of all potential markings also known as potential state space or state space in Transition Systems. Without additional information on the domain in which marking of places may vary, we will assume Q=\mathbb{N}^{d} . Sometimes, information about the system under study allows to reduce Q ; in that case, we will assume to have at least \forall t\in T,Pre(\cdot,t)\in Q\ \text{and}\ Post(\cdot,t)\in Q hold. RS(PN,Init) denotes the set of reachability of a Petri net PN from a subset Init of Q : RS(PN,Init)=\{q\in Q\ |\ \exists\ a\in Init,\ a\overset{*}{\rightarrow}q\} . RG(PN,Init) , and LRG(PN,Init) denote the reachability graph without labels (as in Figure 3 ) and with labels in T respectively; while LCT(PN,q_{0}) denote the labeled coverability tree given a single initial marking q_{0} . 3 Semiflow and Invariants, basic properties The concept of semiflows over non negative integers were first described by Y.E. Lien [ 36 ] and independently by K. Lautenbach and H. A. Schmid [ 34 ] . The algebraic calculus underneath can be find in [ 40 ] . Then, M. Silva [ 38 ] extended the definition to semiflows over integers. After recalling the definition of semiflows, we gather four properties illustrating their their link with behavioral properties. In this section, we consider \langle PN,q_{0}\rangle , a Petri net PN with its initial marking q_{0} and the set of reachable markings from q_{0} through all sequences of transitions denoted by RS(PN,q_{0}) . We first give a classic definition of a semiflow, then show how they characterize a class of invariants that we call f-q-invariant . Then, we analyze how semiflows relate to boundedness as well as liveness. 3.1 Semiflows and associated invariants Definition 1 (Semiflow) A Semiflow f is a solution of the following homogeneous system of |T| diophantine equations: f^{\top}Post(\cdot,t)=f^{\top}Pre(\cdot,t),\ \ \forall t\in T, (2) where x^{\top}y denotes the scalar product of the two vectors x and y , since f,Pre(\cdot,t) and Post(\cdot,t) can be considered as vectors once the places of P have been ordered. \mathcal{F} and \mathcal{F}^{+} denote the sets of solutions of the system of equations ( 2 ) that have their coefficients in \mathbb{Z} and in \mathbb{N} , respectively. The following known property ( [ 41 ] , [ 7 ] , or [ 47 ] ) can easily be proven true in \mathbb{N}^{d} and not true in \mathcal{F} : Property 1 If f and g are two vectors with non-negative coefficients, then we have: \left\|f+g\right\|=\left\|f\right\|\cup\left\|g\right\| . If \alpha is a non-null integer then \left\|\alpha f\right\|=\left\|f\right\| . If f\in\mathcal{F}^{+} , then \left\|f\right\| is both a siphon and a trap which is not the case when f\in\mathcal{F}\setminus\mathcal{F}^{+} . Even when focusing on Petri net literature, we can find many different definitions of the notion of invariant. For instance, an invariant is a set of markings in [ 46 , 35 , 26 ] . Often, this notion is not even informally defined. In this paper, an invariant I is a logic formula that is true for all markings q^{\prime} reached from \langle PN,q\rangle . We write \forall q^{\prime}\in RS(PN,q),q\models I and say that q satisfies I . Here, we are interested in a specific class of invariant that are directly attached to the notion of semiflow. Definition 2 (f-q-invariant) Given f\in\mathbb{Z}^{d},I_{f,q}:Q\to\mathbb{F}_{2} denotes the following unary logic formula: I_{f,q}(q^{\prime}):f^{\top}q=f^{\top}q^{\prime} I_{f,q} is an f-q-invariant if and only if \forall\ q^{\prime}\ \in RS(PN,q):f^{\top}q=f^{\top}q^{\prime}. (3) The support of a logic formula I_{f,q} sometimes also called the characteristic set of I_{f,q} is the subset of Q for which I_{f,q} is true 2 2 2 In a more general manner, we sometimes say that the support H(f,q) of I_{f,q} is the subset of Q that satisfies I_{f,q} and write H(f,q)=\{q^{\prime}\in Q\ |\ q^{\prime}\models I_{f,q}\} . and is denoted by: H(f,q)=\{q^{\prime}\in Q\ |\ f^{\top}q=f^{\top}q^{\prime}\}. Indeed, we have \forall q\in Q,(H(0,q)=Q and \forall f\in\mathbb{Z}^{d},q\in H(f,q) ). The first argument of the support H(f,q) of an f-q-invariant does not have a linear property; instead, we have: Property 2 If f\in\mathbb{Z}^{d} , then, for all \alpha\in\mathbb{Q}\setminus\{0\},H(\alpha f,q_{0})=H(f,q_{0}) . Also, for all f and g\in\mathcal{F} and for all \alpha and \beta\in\mathbb{Q},H(f,q_{0})\cap H(g,q_{0})\subseteq H(\alpha f+\beta g,q_{0}) . If q\in H(f,q_{0})\cap H(g,q_{0}) , then \alpha(f^{\top}q)=\alpha(f^{\top}q_{0}) and \beta(g^{\top}q)=\beta(g^{\top}q_{0}) , so (\alpha f+\beta g)^{\top}q=(\alpha f+\beta g)^{\top}q_{0} , and, therefore, q\in H(\alpha f+\beta g,q_{0}) \square Of course, I_{f,q} is an f-q-invariant if and only if RS(PN,q)\subseteq H(f,q) . f-q invariants and semiflows are indeed related to each other thanks to the fact that a solution of equation ( 2 ) necessarily satisfies equation 3 . Then, the two following results make this interrelation more precise. Lemma 1 Given a marking qi , if f is a semiflow then I_{f,qi} is an f-q-invariant. If f is a semiflow, it satisfies the system of equations ( 2 ), therefore, we can easily deduce from equation ( 1 ) that equations ( 3 ) \square Let us point out that the reverse is not true: if I_{f,qi} is an f-q-invariant then f is not necessarily a semiflow as easily shown Figure ( 1 ). Figure 1: Considering the initial marking qi^{\top}=(1,0,0) , and f^{\top}=(1,1,0) , we can easily verify that I_{f,qi} is an f-q-invariant since RS(PN,qi)=\{qi,(0,1,0)^{\top}\} . However, f is not a semiflow, since it does satisfy the equation associated to t1 of the system of equations ( 2 ) since we have: f^{\top}Pre(\cdot,t1)=1 and f^{\top}Post(\cdot,t1)=0 . Actually, a semiflow can be characterized by the following theorem: Theorem 3.1 f is a semiflow if and only if \forall q\in Q,I_{f,q} is an f-q-invariant Given transition t by choosing Pre(\cdot,t) as initial marking 3 3 3 we assume section 2 that \forall t\in T,Pre(\cdot,t)\in Q . , we can execute t and reach the marking Post(\cdot,t) . If \forall q\in Q,I_{f,q} is an f-q-invariant then by equation ( 3 ), we have: f^{\top}Post(\cdot,t)=f^{\top}Pre(\cdot,t) . We can iterate this operation for all transition of T , therefore, f satisfies the system ( 2 ) and is a semiflow. The reverse is obtained by applying lemma 1 \square 3.2 Semiflows, boundedness, and liveness The most interesting set of semiflows, from a behavioral analysis standpoint, is \mathcal{F}^{+} , defined over natural numbers. This can be seen through the following three properties. First, we define the positive and negative supports of a semiflow f\in\mathcal{F} as: \left\|f\right\|_{+}=\left\{p\in P\ |\ f(p)>0\right\} and \left\|f\right\|_{-}=\left\{p\in P\ |\ f(p)<0\right\}, with \left\|f\right\|=\left\|f\right\|_{-}\cup\ \left\|f\right\|_{+} (by property 1 ). We can then rewrite Equation ( 3 ) as: \forall q\in RS(PN,q_{0}):\ \ f^{\top}q=\left|\sum_{p\in\left\|f\right\|_{+}}f(p)q(p)\right|-\left|\sum_{p\in\left\|f\right\|_{-}}f(p)q(p)\right|=f^{\top}q_{0}. (4) As we can see, the formulation of Equation ( 4 ) is a subtraction between the weighted number of tokens in the places belonging to the positive support and the weighted number of tokens in the places belonging to the negative support of f . Let us recall that a subset of places A is said “bounded" in \langle PN,q_{0}\rangle if and only if \forall p\in A,\ \exists k\in\mathbb{N} such that \forall q\in RS(PN,q_{0}),\ q(p)\leq k . A first general property can be immediately deduced by recalling that any marking q belongs to \mathbb{N}^{d} . Property 3 For any semiflow f\in\mathcal{F} , \left\|f\right\|_{+} is bounded if and only if \ \left\|f\right\|_{-} is bounded. Furthermore, equation ( 4 ) provides a convenient framework for characterizing the concept of “implicit place" as introduced by Silva in [ 48 ] for ordinary Petri nets (see definition section 2.2 ). Definition 3 In an ordinary Petri net \langle PN,q_{0}\rangle a place pi is said to be implicit if and only if there exists a semiflow f\in\mathcal{F} such that \left\|f\right\|_{-}=\{pi\},\ f(pi)=-1,\ \left\|f\right\|_{+}\neq\text{\O}\ \textit{and}\ f^{\top}q_{0}=0. It is important to point out that in order to satisfy equation ( 2 ), we necessary have: \forall t\in T such that Pre(pi,t)=1,\exists p^{\prime}\in\left\|f\right\|_{+} such that Pre(p^{\prime},t)=1 . If \exists q\in RS(PN,q_{0}) such that q(pi)=0 then by equation ( 4 ) and the fact that PN is “ordinary" \forall p\in\left\|f\right\|_{+},q(p)=0 , in particular, q(p^{\prime})=0 . This is making the place pi redundant from a behavioral point of view and pi can be removed from PN without changing LRG(PN,q_{0}) . On another hand, let us notice that the marking of pi is fully determined by the markings of the places of \left\|f\right\|_{+} . A more general algebraic definition can be found in [ 3 ] with more general Pre and Post functions. A behavioral definition can be found in [ 24 , 49 , 22 ] or in [ 52 ] , where a place pi is implicit if and only if removing pi from PN does not change its associated labeled reachability graph; which is the actual motivation for defining the concept of implicit place. Of course, if \left\|f\right\|_{-}=\ Ø, then f\in\mathcal{F}^{+} and \left\|f\right\| is necessarily structurally bounded (i.e., bounded from any initial marking) and is sometime called conservative component as in [ 37 ] . More generally, considering a weighting function f over P being defined over non-negative integers and verifying the following system of inequalities: f^{\top}Post(\cdot,t)\leq f^{\top}Pre(\cdot,t),\ \ \forall t\in T (5) Property 4 If f\geq 0 is such that it verifies the system of inequalities ( 5 ), then the set of places of \left\|f\right\| is structurally bounded. Moreover, if f\neq 0 then \left\|f\right\| is a siphon. Furthermore, the marking of any given place p of \left\|f\right\| has an upper bound: q(p)\leq\left\lfloor\frac{f^{T}q_{0}}{f(p)}\right\rfloor,\ \ \forall q\in RS(PN,q_{0}). The first and last items of this property can be easily proven (see for example [ 41 ] ). If for a given place p\in\left\|f\right\| , we have a transition t such that Post(p,t)>0 then since f\geq 0 f^{\top}Post(p,t)>0 . By the system of inequalities ( 5 ), we have f^{\top}Pre(p,t)>0 ; therefore, \exists p^{\prime}\in\left\|f\right\|, such that pre(p^{\prime},t)>0 . Hence \left\|f\right\| is a siphon as defined section 2.2 \square The reverse is not true in general; it is easy to build a Petri net containing a siphon for which there is no non-null solution f of the system of inequalities ( 5 ) such that f\geq 0 . If f>0 , then \left\|f\right\|_{+}=\left\|f\right\|=P , and we say that the Petri net is also structurally bounded. The reverse is also true: if the Petri net is structurally bounded, then there exists a strictly positive solution for the system of inequalities above (see [ 45 ] or [ 7 ] ). This property is obviously false for a semiflow that satisfies Equation ( 2 ) but would have at least one negative coordinate, and constitutes a first reason for particularly considering weight functions f over P being defined over non-negative integers including \mathcal{F}^{+} . We can then define \Lambda relatively to a given place p and an initial marking q_{0} , the set of all possible bounds generated by semiflows in \mathcal{F}^{+} : \Lambda(p,q_{0})=\{x\in\mathbb{N}\ |\ \exists f\in\mathcal{F}^{+},x=\left\lfloor\frac{f^{T}q_{0}}{f(p)}\right\rfloor\} and its extremum (and more useful element): \lambda(p,q_{0})=\min_{\{f\in\mathcal{F}^{+}\ |\ f(p)\neq 0\}}\left\lfloor\frac{f^{\top}q_{0}}{f(p)}\right\rfloor The following corollary can be directly deduced from the fact that any semiflow in \mathcal{F}^{+} satisfies the system of inequalities ( 5 ); therefore, Property 4 can apply: Corollary 1 For any place p belonging to at least one support of a semiflow of \mathcal{F}^{+} , an upper bound \lambda can be defined for the marking of p relatively to an initial marking q_{0} such that: \forall q\in RS(PN,q_{0}),\ \ q(p)\leq\lambda(p,q_{0})=\min_{\{f\in\mathcal{F}^{+}\ |\ f(p)\neq 0\}}\left\lfloor\frac{f^{\top}q_{0}}{f(p)}\right\rfloor. We will see with Theorem 5.4 that this bound is computable as a consequence of Theorems 5.1 and 5.3 . Definition 4 Given a transition t and a semiflow f in \mathcal{F}^{+} , the scalar product f^{T}Pre(\cdot,t) is called the f-enabling threshold of t . Sometimes, when there is no ambiguity, f^{T}Pre(\cdot,t) is more simply called the enabling threshold of t as in [ 7 ] . This gives us a second reason for particularly considering a semiflow f as being defined over non-negative integers is that the system of inequalities f^{T}q_{0}\geq f^{T}Pre(\cdot,t),\ \ \ \ \forall t\in T, (6) becomes a necessary condition for any transition t to stand a chance to be enabled from a reachable marking from q_{0} , therefore to be live. Indeed, the system of inequalities ( 6 ) motivates the definition 4 . Property 5 If t is a transition and f\in\mathcal{F}^{+}\setminus\{0\} such that f^{T}q_{0}|\ \left\|g\right\|=I\right\} . In other words, \{f\} is a unique generating set over \mathbb{N} for \mathcal{F}_{I}^{+}=\{g\in\mathcal{F^{+}}\;|\left\|g\right\|=I\} . Indeed, this uniqueness property is lost in \mathbb{Q^{+}} or in \mathbb{Q} , since any element of \mathcal{F}_{I}^{+} is a generating set of \mathcal{F}_{I}^{+} over \mathbb{Q^{+}} or \mathbb{Q} . Theorem 5.3 ( Decomposition over \mathbb{Q}^{+} ) Any support I of semiflows is covered by the finite subset \{I_{1},I_{2},\dots,I_{N}\} of minimal supports of semiflows included in I : I=\bigcup_{i=1}^{i=N}I_{i} . Moreover, for all f\in\mathcal{F^{+}} such that \left\|f\right\|\subseteq I , one has f=\sum_{i=1}^{i=N}\alpha_{i}g_{i} , where, for all i\in\{1,2,...N\},\ \alpha_{i}\in\mathbb{Q^{+}} and the semiflows g_{i} are such that \left\|g_{i}\right\|=I_{i} . A sketch of the proof of Theorem 5.3 using Property 1 can be found in [ 39 ] , and a complete proof, in [ 41 ] . This last theorem says that one cannot have a generating set with less than n semiflows where n is the number of minimal supports included in P . 5.3 Three extremums computability Knowledge of any finite generating set allows a practical computation of the three extremums ( \lambda , \theta , and \omega ) defined in the previous sections. We know that a finite generating set does exist by Gordan’s lemma ( 3 ) and we know how to compute a generating set (see [ 38 ] for instance). Subsequently, we can state the following theorem which expresses the fact that three extremums ( \lambda , \theta , and \omega ) are computable as soon as any finite generating set is available. Theorem 5.4 Let \mathcal{E}=\{e_{1},...e_{N}\} be any finite generating set of \mathcal{F}^{+} , and q_{0}\in Q , an initial marking. (i) If \mathcal{E} is over \mathbb{S} , then we have: \omega(q_{0})=\bigcap_{f\in\mathcal{F^{+}}}H(f,q_{0})=\bigcap_{e_{i}\in\mathcal{E}}H(e_{i},q_{0}) ; (ii) If \mathcal{E} is over \mathbb{Q}^{+} or \mathbb{N} , then, for any place p belonging to at least one support of a semiflow of \mathcal{F}^{+} , for all q\in RS(PN,q_{0}) , we have : q(p)\leq\lambda(p,q_{0})=\min_{\{f\in\mathcal{F}^{+}\ |\ f(p)\neq 0\}}\frac{f^{\top}q_{0}}{f(p)}=\min_{\{e_{i}\in\mathcal{E}\ |\ e_{i}(p)\neq 0\}}\frac{{e_{i}}^{\top}q_{0}}{e_{i}(p)}; (iii) If \mathcal{E} is over \mathbb{Q}^{+} or \mathbb{N} , then, for any transition t belonging to at least one support of a semiflow of \mathcal{F}^{+} , for all q\in RS(PN,q_{0}) , we have : \theta(t,q_{0})=\min_{\{f\in\mathcal{F}^{+}\ |\ f^{\top}Pre(\cdot,t)\neq 0\}\}}\frac{f^{\top}q_{0}}{f^{\top}Pre(\cdot,t)}=\min_{\{e_{i}\in\mathcal{E}\ |\ e_{i}^{\top}Pre(\cdot,t)\neq 0\}\}}\frac{f^{\top}q_{0}}{f^{\top}Pre(\cdot,t)} . Regarding item (i), let’s consider f\in\mathcal{F^{+}} with f=\sum_{i=1}^{i=N}\alpha_{i}e_{i} and q\in\bigcap_{e_{i}\in\mathcal{E}}H(e_{i},q_{0}) . Then, \alpha_{i}(e_{i}^{\top}q)=\alpha_{i}(e_{i}^{\top}q_{0}) , for all i\in\{1,...N\} , and, hence \sum_{i=1}^{i=N}\alpha_{i}(e_{i}^{\top}q)=\sum_{i=1}^{i=N}\alpha_{i}(e_{i}^{\top}q_{0}) . Then, for all f\in\mathcal{F^{+}} , f^{\top}q=f^{\top}q_{0} , and q\in H(f,q_{0}) . Therefore, since \mathcal{E}\subset\mathcal{F^{+}} directly implies (\bigcap_{f\in\mathcal{F^{+}}}H(f,q_{0}))\subseteq\bigcap_{e_{i}\in\mathcal{E}}H(e_{i},q_{0}) , we have: \bigcap_{e_{i}\in\mathcal{E}}H(e_{i},q_{0})=\bigcap_{f\in\mathcal{F^{+}}}H(f,q_{0})=\omega(q_{0}) . For the item (ii), let’s consider a marking q_{0} , a place p , and a semiflow f of \mathcal{F}^{+} such that f(p)>0 and f=\sum_{i=1}^{i=N}\alpha_{i}e_{i} , where \alpha_{i}\geq 0 , for all i\in\{1,...N\} . Let’s define \lambda_{\mathcal{E}} such that \lambda_{\mathcal{E}}=\min_{\{e_{i}\in\mathcal{E}\ |\ e_{i}(p)\neq 0\}}\frac{{e_{i}}^{\top}q_{0}}{e_{i}(p)} . Then, there exists j such that 1\leq j\leq N and \lambda_{\mathcal{E}}=\frac{{e_{j}}^{\top}q_{0}}{e_{j}(p)} . Therefore, for all i\leq N such that e_{i}(p)\neq 0 , there exists \delta_{i}\in\mathbb{Q}^{+} such that: \frac{{e_{j}}^{\top}q_{0}}{e_{j}(p)}=\frac{{e_{i}}^{\top}q_{0}-\delta_{i}}{e_{i}(p)} . It can then be deduced, for all i such that \alpha_{i}e_{i}(p)\neq 0 : \lambda_{\mathcal{E}}=\frac{\alpha_{i}({e_{i}}^{\top}q_{0}-\delta_{i})}{\alpha_{i}e_{i}(p)}, and, therefore: \lambda_{\mathcal{E}}=\frac{\sum_{\{i\ |\ \alpha_{i}e_{i}(p)>0\}}\alpha_{i}({e_{i}}^{\top}q_{0}-\delta_{i})}{\sum_{\{i\ |\ \alpha_{i}e_{i}(p)>0\}}\alpha_{i}e_{i}(p)} Since \sum_{\{i\ |\ \alpha_{i}e_{i}(p)>0\}}\alpha_{i}({e_{i}}^{\top}q_{0})=f^{\top}q_{0}-\sum_{\{i\ |\ \alpha_{i}e_{i}(p)=0\}}\alpha_{i}({e_{i}}^{\top}q_{0}) and \sum_{\{i\ |\ \alpha_{i}e_{i}(p)>0\}}\alpha_{i}e_{i}(p)=f(p) \lambda_{\mathcal{E}}=\frac{f^{\top}q_{0}-\sum_{\{i|e_{i}(p)>0\}}\alpha_{i}\delta_{i}-\sum_{\{i\ |\ e_{i}(p)=0\}}\alpha_{i}{e_{i}}^{\top}q_{0}}{f(p)} Then, since \delta_{i}\geq 0 and \alpha_{i}\geq 0 for all i such that 1\leq i\leq N , \lambda_{\mathcal{E}}\leq\frac{f^{\top}q_{0}}{f(p)} This being verified for any semiflow of \mathcal{F}^{+} , we have \lambda(p,q_{0})=\lambda_{\mathcal{E}} . The item (iii) of the theorem can be proven by a similar demonstration \square Item (i) is similar to a result that can be found in [ 29 ] . The complexity of computing item (ii) or (iii) depends on N the number of elements of \mathcal{E} . We know from theorem 5.3 that N cannot be less than the number of minimal supports. 6 Reasoning with invariants, semiflows, and home spaces Invariants, semiflows, and home spaces can be used in combination to ease the proof of a rich array of behavioral properties of Petri nets, in particular when using parameters. 6.1 Methodically analyzing behavioral properties The results presented in this paper provide verification engineers with a few steps to methodically analyze and prove behavioral properties, in particular, that a subset of transitions are live: - reduce the model using reduction rules such as in [ 4 , 47 ] , paying attention at preserving the support of properties that we seek to prove, - run existing algorithms to compute Generating sets, [ 38 , 1 ] , even with parameters as in [ 13 ] ; (comparisons and benchmarks can be found in [ 11 ] and more recently in [ 50 ] ), - from a generating set, using property 2 , infer a first home space that concisely describes how tokens are distributed over places, - use theorem 5.4 to prune away impossible situations, - step by step proceed by refinement of home states, by finding which transitions or which arithmetic transformation can be enabled and constrain current home spaces until reaching a possible home state, - Use algorithms as in [ 32 , 19 ] to construct the labeled coverability tree (LCT), and then deduce which transitions are live from the ones that appears in LCT (theorem 4.2 ), - ultimately, decide whether the Petri net is live or not. Here, through two related parameterized examples, we proceed by using basic arithmetic and some particularity of the structure of the model to determine a home space and a home state in the second case. Then, it becomes easy to determine for which values of the parameters the Petri net possesses the required liveness property. First, we propose to look at an example with a parameter i to define its \mathit{Pre} and \mathit{Post} functions. This example allows one to detect whether a natural number n is a multiple of i . The second example is an extension of the first one with a coloration of the tokens allowing one to detect the remainder of the Euclidean division of n by i . 6.2 A first example The Petri net TN(i)=\langle\{A,B\},\{t_{1},t_{2}\},Pre,Post\rangle in Figure 4 is defined by: Pre(\cdot,t_{1})^{\top}=(i,0);Pre(\cdot,t_{2})^{\top}=(1,1) ; Post(\cdot,t_{1})^{\top}=(0,1);Post(\cdot,t_{2})^{\top}=(i+1,0). The initial marking q_{0} is such that q_{0}(A)=n and q_{0}(B)=x , where n and x\in\mathbb{N} . Figure 4: Semiflows must verify the system of equations ( 2 ) which is reduced to the following equation: i\times a=b , for which g^{\top}=(1,i) is an obvious solution. TN(i) is live if and only if g^{\top}q_{0}>i and is not a multiple of i , regardless of the initial marking of B . For i=1 , TN(1) has no live transition, regardless of the initial marking. A first version of this example can be found for i=2 in [ 7 ] or in [ 42 ] , without proof. Here, the Petri net TN(i) is enriched by introducing a parameter i such that i>1 in order to define its Pre and Post functions. g^{\top}=(1,i) is the minimal semiflow of minimal support, and we can prove that \left\langle TN(i),q_{0}\right\rangle is not live if and only if g^{\top}q_{0}\leq i or g^{\top}q_{0}=n\times i , independently of q_{0}(B) . In other words, TN(i) recognizes whether a given number n is a multiple of i . First, if g^{\top}q_{0}i , then after executing t_{1} n-q(B) times, we reach a marking with r tokens in A and at least one token in B . Therefore, H=\{q\in RS(TN(i),q_{0})\ |\ q(A)\neq 0\ \land\ q(B)\neq 0\} is a home space such that H\subseteq\texttt{Dom($t_{2}$)} so we can apply property 8 proving that t_{2} is live. It is easy to conclude that the Petri net TN(i) is live if and only if g^{\top}q_{0}>i and is not a multiple of i , regardless of the initial marking of B \square We can point out that it was not necessary to develop a symbolic reachability graph in order to decide whether or not the Petri net is live or bounded. We could analyze the Petri net even partially ignoring the initial marking (i.e., the analysis could be conducted independently of the values taken by q_{0}(B) ). 6.3 Euclidean division From the properties of TN(i) , it is natural to progress by one more step and propose to design a Petri net with the ability not only to recognize whether a natural number n is a multiple of a given natural number i , but more generally to recognize the remainder of the Euclidean division of n such that n>0 by i such that i>1 . To this effect, we first consider the Colored Petri net TNCED(i) of Figure 5 (a), and the parameter i\geq 2 . Second, to simplify the reasoning, we unfold TNCED(i) into the classic Petri net TNED(i) , where each place A_{j} represents the place A with the color j of TNCED(i) (as shown Figures 5 (a) and 5 (b)). TNED(i)=\langle P,T,Pre,Post\rangle is such that: P=\{\{A_{j}|\ j\in\left[0,i-1\right]\},B\} and T=\{t_{j,1},t_{j,2}|\ j\in\left[0,i-1\right]\} , where \mathit{Pre} and \mathit{Post} are defined for j\in\left[0,i-1\right]\ by : Pre(A_{j},t_{j,1})=i,\ Pre(B,t_{j,1})=\ Pre(A_{j},t_{j,2})=1,Pre(p,t)=0 otherwise, Post(A_{j},t_{j,2})=i+1,Post(B,t_{j,1})=1,Post(p,t)=0, otherwise. The initial marking is such that q_{0}(A_{j})=n+j , where j\in\left[0,i-1\right] , and q_{0}(B)=x , where n>0 and x are natural numbers. Figure 5: TNCED(i) of Figure (a) , is a Colored Petri net with a set C of colors to distinguish values between 0 and i-1 plus \tau as an undefined color of token; \ C=([0,...i-1]\cap\mathbb{N})\cup\{\tau\} . We have a system of i equations: i\times a_{j}=b with j\in\left[0,i-1\right]\cap\mathbb{N} , for which g such that g(A(j))=1 for j\in\left[0,i-1\right]\cap\mathbb{N} and g(B(\tau))=i is the same minimal semiflow of minimal support in \mathbb{N} . TNED(i) of Figure (b) is the unfolded version of TNCED(i) . To compute semiflows, we have the same system of i equations: i\times a_{j}=b with j\in\left[0,i-1\right] , for which g such that g(A_{j})=1 for j\in\left[0,i-1\right] and g(B)=i is as expected, the same minimal semiflow of minimal support in \mathbb{N} as for TNCED(i) . This parameterized Petri net (colored or unfolded) allows knowing the remainder of the Euclidean division of a natural number n by i . g^{T}=(1,\cdots 1,i) , such that g(A_{j})=1 for j\in\left[0,i-1\right] , and g(B)=i is the sole minimal semiflow of minimal support in \mathbb{N} . We have a first associated invariant I_{g,q_{0}} , since: \forall q\in RS(TNED(i),q_{0}):g^{\top}q_{0}=g^{\top}q=\sum_{j=0}^{j=i-1}q_{0}(A_{j})+iq_{0}(B)=i\times(x+n+\frac{i-1}{2}). Then, we need to notice that any place A_{j} is connected to exactly two transitions, t_{j,1} and t_{j,2} , such that: Post(A_{j},t_{j,1})-Pre(A_{j},t_{j,1})=-i , Post(A_{j},t_{j,2})-Pre(A_{j},t_{j,2})=i . Hence, for all q\in RS(TNED(i),q_{0}) and j\in\left[0,i-1\right] , q(A_{j}) can only vary by \pm i . We then deduce a family of i invariants I(j) for j\in\left[0,i-1\right] : I(j):\forall q\in RS(TNED(i),q_{0}),\ q(A_{j})\equiv q_{0}(A_{j})\mod i. By performing the Euclidean division of q_{0}(A_{j}) by i , we have: q_{0}(A_{j})=n+j=a_{j}\times i+\alpha_{j},where\ \alpha_{j}0 ) and that q_{0} is unreachable from q_{h} ). From Property 9 , we deduce that, since any transition t_{j,2} where j\neq k is executable ( n>0 hence, q_{h}(B)>1 and q_{h}(A_{j})=\alpha_{j}>0 ), then t_{j,2} is live, and, therefore, the corresponding transitions t_{j,1} are also live. From (b), q_{h}(A_{k})=0 from, which we deduce that t_{k,1} and t_{k,2} are not live 6 6 6 Actually, it suffices to notice that A_{k} is an empty siphon (as defined section 2.2 ) that once empty remains empty. . Finally, we have n+k=a_{k}\times i , and the remainder of the Euclidean division of n by i is i-k . TNED(i) provides the ability to recognize this remainder by the remarkable fact that (t_{k,1},t_{k,2}) is the only couple of transitions not live \square Figure 6: The initial state q_{0} is such that: q_{0}(A)=q_{0}(B)=q_{0}^{\prime}F)=1,q_{0}(p)=0 otherwise. This Petri net is live and for instance, q_{c} such that: q_{c}(C)=q_{c}(D)=q_{(}E)=q_{c}(F)=1,q_{c}(p)=0 otherwise, is a home state. Most of the time, in real-life use cases, when a model accepts a set of home states, the initial marking belongs to it. This is not the case in our example, where the initial marking q_{0} is not a home state, and q_{h} is a home state. This could suggest (as conjectured in [ 43 ] ) that if the initial marking q_{0} of a Petri net PN is not a home state and there exists a home state q_{h} in RS(PN,q_{0}) , then there exists at least one non-live transition in a sequence of transitions from q_{0} to q_{h} . This statement holds for state machines, however, it does not hold in the general case, as shown by the Petri net Figure 6 . 7 Conclusion It has been recalled how semiflows allow inferring strong constraints over not only all reachable markings but all possible markings of a given Petri net, which greatly help analysis of behavioral properties such as not only boundedness but also liveness. This allows pursuing the same analysis on a set of initial markings (defined by a parameter). Moreover, analysis can be performed with incomplete information, particularly when markings and even structures are described with parameters as in our two examples. The set of semiflows can be characterized with the notion of minimal generating set, and we hope that our three decomposition theorems reached their final version. They were useful to make properties on boundedness or liveness computable. Theorem 5.4 consolidates our thesis saying that the information deduced from a generating set brings most of if not all the information that semiflows in \mathcal{F}^{+} can provide for analyzing behavioral properties. Most of the time, especially with real-life system models, it will be possible to avoid a painstaking symbolic model checking or a parameterized and complex development of a reachability graph [ 15 , 8 ] . We introduced new results about home spaces; in particular, theorem 4.2 is new to the best of our knowledge (for instance, it does not appear in the recent survey on decidability issues for Petri nets [ 18 ] ). This theorem is interesting for at least two different reasons. First, from a theoretical point of view, it characterizes a class containing unbounded Petri nets (the existence of a home state does not involve that the Petri net is bounded). Second, from a practical point of view, it shed a new light on the usage of coverability graphs, since real-life systems often have a home state by design. It increases the importance one can grant to the construction and the optimization of coverability trees, which is used mostly to determine which places are bounded (see important works by Finkel and al [ 19 ] about accelerating this construction) by supporting the analysis of liveness. At last, we presented most of these results in the framework of Petri nets, we believe that part of these results apply to Transition Systems, especially, section 4 on home spaces . This, indeed, constitutes a starting point for future work.