# Minimal Generating Sets for Semiflows

Gerard Memmi

► To cite this version:

Gerard Memmi. Minimal Generating Sets for Semiflows. 43th International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE), Jun 2023, Lisbon, Portugal. pp.189-205, 10.1007/978-3-031-35355-0_12. hal-04731934

HAL Id: hal-04731934

https://inria.hal.science/hal-04731934v1

Submitted on 11 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Minimal Generating Sets for Semiflows

Gerard Memmi(✉)

LTCI, Telecom-Paris, Institut polytechnique de Paris, Palaiseau, France

gerard.memmi@telecom-paris.fr

**Abstract.** We discuss important characteristics of finite generating sets for $\mathcal{F}^+$, the set of all semiflows with non-negative coordinates of a Petri Net. We endeavor to regroup a number of algebraic results dispersed throughout the Petri Nets literature and also to better position the results while considering semirings such as $\mathbb{N}$ or $\mathbb{Q}^+$ then fields such as $\mathbb{Q}$. As accurately as possible, we provide a range of new algebraic results on minimal semiflows, minimal supports, and finite minimal generating sets for a given family of semiflows. Minimality of semiflows and of support are critical to develop effective analysis of invariants and behavioral properties of Petri Nets. Main results are concisely presented in a table and our contribution is highlighted. We conclude with the analysis of an example drawn from the telecommunication industry underlining the efficiency brought by using minimal semiflows of minimal supports.

**Keywords:** Formal verification · Petri Nets · invariant · linear algebra · semiflow · generating set

## 1 Introduction and Motivations

The notion of generating sets for semiflows is well known and efficiently supports the handling of an important class of invariants sometimes unduly called linear invariants in the literature. Several results have been published starting from the initial definition and structure of semiflows [18] to a large array of applications used especially to analyze Petri Nets [9, 10, 12, 27]. Several algorithms were independently developed to compute a generating set of semiflows [26] or later in [1, 17]. All of them can be considered as variations of Farkas or Fourier algorithms related to integer linear programming and convex geometry (see [7] for a comparative study or [23] for the underlying mathematical theory).

Semiflows are intimately associated with home spaces and invariants to prove fundamental properties of Petri Nets (even including parameters as in [4]) such as safeness, boundedness, or more complex behavioral properties such as liveness.

Minimality of semiflows and minimality of their supports are critical for accelerating analysis compared to using other semiflows. Invariants deduced from minimal semiflows relate to smaller quantities of resources. Furthermore, the smaller the support of semiflows, the more local their footprint. In the end, these two notions of minimality will foster analysis optimization.

Our main motivation was to go beyond regrouping a number of algebraic results dispersed throughout the Petri Nets literature and to compare and better
position these results in considering semirings such as $\mathbb{N}$ or $\mathbb{Q}^+$ then over a field such as $\mathbb{Q}$. In this regard, we were able to complete the current state of the art as accurately as possible with a range of new results on minimal semiflows, minimal supports, and finite minimal generating sets for a given family of semiflows.

## 1.1 Outline

In Sect. 2, after a brief description of Petri Nets, semiflows, and the set $\mathcal{F}^+$ of all semiflows with non-negative coordinates of a Petri Net, the notions of generating sets, minimal semiflows, and minimal supports are then defined in Sect. 3. Moreover, in this section, it's important to relate semiflow theory to mathematical concepts from linear algebra, convex geometry, or discrete mathematics such as Sperner's theorem to provide with a bound for the number of minimal supports or Gordan's lemma about the existence of finite generating sets. This last connection has never before been attempted.

The three decomposition theorems of Sect. 4 were first published in [19]. Here, two of them are extended to better characterize minimal semiflows and generating sets over $\mathbb{N}$ and better covering $\mathbb{N}$, $\mathbb{Q}^+$, and $\mathbb{Q}$. They are at the core of this paper, since they have made it possible to consolidate results scattered in the literature in a meaningful way and are at the source of the new results presented in the following sections.

Succinct examples and counterexamples are provided to illustrate various results throughout Sects. 4 to 6. Differences between minimal and canonical semiflows are made precise in the Lemma 2 in Sect. 5, which is dedicated to this notion; the section ends with a theorem which states under which condition the number of canonical semiflows is infinite (Sect. 5.2).

The notion of minimal generating sets for semiflows described in Sect. 6 can already be found in [18], then by Colom, Silva, and Teruel in [24] p. 319 and later by the same authors in [8], p. 68 or more recently, in [6]. However, Theorem 5 is new, to the best of our knowledge, and proves the coincidence between a least generating set and a minimal generating set which is not always true in order theory. Uniqueness of particular generating sets is presented in Sect. 6.3.

In Sect. 7, a table is summarizing main results, in particular showing differences<fnref n="1" /> when considering $\mathbb{N}$, $\mathbb{Q}^+$, or $\mathbb{Q}$ and highlighting our contribution.

A concrete example is drawn from the telecommunication industry Sect. 8; it illustrates how the choice of minimal semiflows of minimal support is an important factor in simplifying the proof of safeness and liveness for a given Petri Net. Section 9 concludes and provides possible avenues of future research.

# 2 Petri Nets and Semiflows

A Petri Net is a tuple $PN = \langle P, T, Pre, Post \rangle$, where $P$ is a finite set of *places*, $T$ a finite set of *transitions* such that $P \cap T = \emptyset$. A transition $t$ of $T$ is defined by

<footnote n="1">¹ A few inaccuracies found in the literature (e.g. in [6, 7]) stem from these differences.</footnote>
its $Pre(\cdot, t)$ and $Post(\cdot, t)$ conditions<fnref n="2" />: $Pre: P \times T \to \mathbb{N}$ is a function providing a weight for pairs ordered from places to transitions, $Post: P \times T \to \mathbb{N}$ is a function providing a weight for pairs ordered from transitions to places. $d$ will denote the number of places: $d = |P|$.

The dynamic behavior of Petri Nets is modeled via markings. A marking $M$: $P \to \mathbb{N}$ is a function that evolves with the execution (or firing) of transitions. When $M(p) = k$, it is often said that the place $p$ contains $k$ tokens.

Extensive definitions, properties, and case studies can be found in particular in [5, 11].

Semiflows can be defined as solutions of the following homogeneous system of $|T|$ diophantine equations:

$$f^{\top}Post(\cdot, t) = f^{\top}Pre(\cdot, t), \quad \forall t \in T, \qquad (1)$$

where $x^\top y$ denotes the scalar product of the two vectors $x$ and $y$ since $f, Pre$ and $Post$ can be considered as vectors once the places of $P$ have been ordered.

Considering an initial marking $M_0$ and the set of reachable markings from $M_0$, any non-null solution $f$ of the system of Eq. (1) allows to directly deduce the following invariant of the Petri Net defined by its $Pre$ and $Post$ functions (used in the system of equations that $f$ satisfies):

$$\forall M \text{ reachable from } M_0: f^{\top}M = f^{\top}M_0. \qquad (2)$$

In the rest of the paper, we will only consider the set $\mathcal{F}^+$ of semiflows with non-negative coordinates<fnref n="3" />. $\mathcal{F}^+$ can be defined by:

$$\mathcal{F}^+ = \{f \in \mathbb{N}^d \mid \forall t \in T, f^{\top}Post(\cdot, t) = f^{\top}Pre(\cdot, t)\}.$$

We abusively use the same symbol '0' to denote $(0, ..., 0)^\top$ of $\mathbb{N}^n$, $\forall n \in \mathbb{N}$. The support of a semiflow $f$ is denoted by $\|f\|$ and is defined by:

$$\|f\| = \{x \in P \mid f(x) \neq 0\}.$$

We will use the usual componentwise partial order in which $(x_1, x_2, ..., x_d)^\top \leq (y_1, y_2, ..., y_d)^\top$ if and only if $x_i \leq y_i \forall i \in \{1, ..., d\}$.

# 3 Generating Sets and Minimality

## 3.1 Basic Definitions and Results

A subset $\mathcal{G}$ of $\mathcal{F}^+$ is a generating set over a set $\mathbb{S}$ if and only if $\forall f \in \mathcal{F}^+$ we have $f = \sum_{g_i \in \mathcal{G}} \alpha_i g_i$ where $\alpha_i \in \mathbb{S}$ and $\mathbb{S} \in \{\mathbb{N}, \mathbb{Q}^+, \mathbb{Q}\}$, where $\mathbb{Q}^+$ denotes the set of non-negative rational numbers.

Since $\mathbb{N} \subset \mathbb{Q}^+ \subset \mathbb{Q}^4$, a generating set over $\mathbb{N}$ is also a generating set over $\mathbb{Q}^+$, and a generating set over $\mathbb{Q}^+$ is also a generating set over $\mathbb{Q}$. However, the

<footnote n="2">² We use here the usual notation: $Pre(\cdot, t)(p) = Pre(p, t)$ and $Post(\cdot, t)(p) = Post(p, t)$.</footnote>

<footnote n="3">³ Semiflows with negative coordinates can also be defined, for instance [7]; however, they are not the object of this paper.</footnote>

<footnote n="4">⁴ Where $\subset$ denotes the strict inclusion between sets.</footnote>
reverse is not true and, in our opinion, one source of some of the inaccuracies
found in the literature.

The notion of the generating set is strongly related to algebraic concepts especially when it is finite. Let's consider $\mathcal{G}$ a finite generating set of $\mathcal{F}^+$ such that $\mathcal{G} = \{g_1, \dots, g_k\}$, the following definitions can be recalled.

- If $\mathcal{G}$ is a generating set over $\mathbb{N}$ then
  $\mathcal{S}(\mathcal{G}) = \{f \in \mathbb{N}^d \mid f = \sum_{i=1}^{i=k} \alpha_i g_i \text{ and } \alpha_i \in \mathbb{N}\}$ is a semigroup and $\mathcal{F}^+ = \mathcal{S}(\mathcal{G})$.

- If $\mathcal{G}$ is a generating set over $\mathbb{Q}^+$ then
  $\mathcal{C}(\mathcal{G}) = \{f \in (\mathbb{Q}^+)^d \mid f = \sum_{i=1}^{i=k} \alpha_i g_i \text{ and } \alpha_i \in \mathbb{Q}^+\}$ is a convex polyhedral cone and $\mathcal{F}^+ = \mathcal{C}(\mathcal{G}) \cap \mathbb{N}^d$. It is interesting to recall a result from [15] stating that $\mathcal{F}^+ \neq \{0\}$ if and only if $\mathcal{C}(\mathcal{G}) \neq \{0\}$.

- If $\mathcal{G}$ is a generating set over $\mathbb{Q}$ then
  $\mathcal{V}(\mathcal{G}) = \{f \in \mathbb{Q}^d \mid f = \sum_{i=1}^{i=k} \alpha_i g_i \text{ and } \alpha_i \in \mathbb{Q}\}$ is a vector space and $\mathcal{F}^+ = \mathcal{V}(\mathcal{G}) \cap \mathbb{N}^d$. We can extract from $\mathcal{G}$ a basis of $\mathcal{V}(\mathcal{G})$ (see, for instance, [14] p. 85) which also is a generating set of $\mathcal{F}^+$ over $\mathbb{Q}$ since the elements of this basis are in $\mathcal{F}^+$.

The fact that there exists a finite generating set over $\mathbb{N}$ is non trivial. This
result was proven by Gordan circa 1885 then Dickson circa 1913. Here, we
directly rewrite Gordan's lemma [2] by adapting it to our notations.

**Lemma 1 (Gordan circa 1885).** Let $\mathcal{F}^+$ be the set of non-negative integer solutions of the system of Eq. (1). Then, there exists a finite generating set of vectors in $\mathcal{F}^+$ such that every element of $\mathcal{F}^+$ is a linear combination of these vectors with non-negative integer coefficients.

In the next sections, we will not come back on the question of the existence
of a finite generating set. Being shown for $\mathbb{N}$, it is necessarily true for $\mathbb{Q}^+$ and $\mathbb{Q}$.

**3.2 Minimal Supports and Minimal Semiflows**

Several definitions of the notion of minimal semiflow were introduced in [24] p. 319, in [8] p. 68, [6,13], or in [19,20]. It can be confusing to look into these in details. In light of this, we propose to consider only two basic notions in order theory: minimality of support with respect to set inclusion and minimality of semiflow with respect to the componentwise partial order on $\mathbb{N}^d$ since the various definitions we found in the literature as well as the results of this paper can be described in terms of these sole two classic notions.

A non-empty support $\|f\|$ of a semiflow $f$ is minimal with respect to set inclusion if and only if $\nexists g \in \mathcal{F}^+ \setminus \{0\}$ such that $\|g\| \subset \|f\|$.

Since $P$ is finite, the set $\mathcal{MS}$ of minimal supports in $P$ is a Sperner family (i.e., a family of subsets such that none of them contains another one) and we can apply Sperner's theorem [25] over $m = |\mathcal{MS}|$ which states that:

$$
m \le \binom{d}{\lfloor d/2 \rfloor}. \qquad (3)
$$
This result, which was already mentioned in [20,24], provides us with a general upper bound for the number of minimal supports in a given Petri Net. To the best of our knowledge, this bound can be reached only by three families of degenerate Petri Nets containing isolated elements: only one, two, or three places and as many isolated transitions as desired. We conjecture that this bound cannot be reached for Petri Nets with more than three places and should be refined on a case-by-case basis by exploiting connectivity between places and transitions as hinted in the example Sect. 8.

A non-null semiflow $f$ is minimal with respect to $\le$ if and only if $\nexists g \in \mathcal{F}^+ \setminus \{0, f\}$ such that $g \le f$.

In other words, a minimal semiflow cannot be decomposed as the sum of another semiflow and a non-null non-negative vector. This remark yields initial insight into the foundational role of minimality regarding the decomposition of semiflows. We are looking for characterizing generating sets such that they allow analyzing various behavioral properties as efficiently as possible. First, if we consider a generating set over $\mathbb{N}$, then we may have to explore every minimal semiflow. Although finite, the number of minimal semiflows can be quite large. Second, considering a basis over $\mathbb{Q}$ may not capture behavioral constraints quite easily (see the example of Sect. 8).

# 4 Three Decomposition Theorems

Generating sets can be characterized thanks to a set of three decomposition theorems that can be found in [19] with their proofs. Here, Theorem 1 is extended to better characterize minimal semiflows and generating sets over $\mathbb{N}$, and is provided with a new proof using Gordan's Lemma 1. Theorem 2 was only valid over $\mathbb{N}$ and is now extended to include $\mathbb{Q}^+$ and $\mathbb{Q}$. Theorem 3 is only valid over $\mathbb{Q}^+$ and is unchanged.

## 4.1 Decomposition over Non-negative Integers

**Theorem 1.** If a semiflow is minimal then it belongs to any generating set over $\mathbb{N}$.

The set of minimal semiflows of $\mathcal{F}^+$ is a finite generating set over $\mathbb{N}$.

Let's consider a semiflow $f \in \mathcal{F}^+ \setminus \{0\}$ such that $\exists f_1, ..., f_k \in \mathcal{F}^+ \setminus \{0, f\}$ and $a_1, ..., a_k \in \mathbb{N}$ such that $f = \sum_{i=1}^{i=k} a_i f_i$. Since $f \neq 0$ and all coefficients $a_i$ are in $\mathbb{N}$, $\exists j \le k$ such that $a_j > 0$. Therefore, $a_j f_j \le f$, since $f_j \neq f$, we have $f_j < f$ so $f$ is not minimal. Hence, if a semiflow is minimal then it has to belong to every generating set over $\mathbb{N}$.

Applying Gordan's lemma, there exists $\mathcal{G}$, a finite generating set. Since any minimal semiflow is in $\mathcal{G}$, the subset of all minimal semiflows is included in $\mathcal{G}$ and therefore finite. Let $\mathcal{E} = \{e_1, ... e_n\}$ be this subset.

For any semiflow $f \in \mathcal{F}^+$, we can always define $r \in \mathcal{F}^+$ and a set of $n$ non-negative integers $\{k_1, ..., k_n\}$ such that:
i) $r = f - \sum_{j=1}^{j=n} k_j e_j$, where $k_i$ are defined by:

ii) $\forall i \le n, (f - \sum_{j=1}^{j=i} k_j e_j) \in \mathcal{F}^+$ and $(f - \sum_{j=1}^{j=i} k_j e_j - e_i) \notin \mathcal{F}^+$

By construction of the non-negative integers $k_i$, we have $r \in \mathcal{F}^+ \setminus \{0\}$ and $\mathfrak{h}e_i \in \mathcal{E}$ such that $e_i \le r$. This means that $r$ is minimal or null. $\mathcal{E}$ includes all minimal semiflows, therefore, if $r$ were minimal, then $\exists i \le n$ such that $e_i = r$. Again, this would contradict the way the coefficients $k_i$ were defined. Therefore, $r = 0$, any semiflow can be decomposed as a linear combinations of minimal semiflows, and $\mathcal{E}$ is a generating set.<fnref n="5" /> □

Let's point out that since $\mathcal{E}$ is not necessarily a basis, the exhibited decomposition may not be unique and depends on the order in which the minimal semiflows are considered as shown in Fig. 1 where the semiflow $h^\top = (9, 9, 6, 0, 3)$ can be decomposed in three different ways: $h = f_2 + g_1 + f_1 = 3f_1 = 2g_1 + g_3$ just by changing the order in which the 5 minimal semiflows are considered.

<figure><img src="image_3.png" /></figure>

**Fig. 1.** $f_1^\top = (3, 3, 2, 0, 1)$, $f_2^\top = (4, 4, 1, 0, 2)$, $g_1^\top = (2, 2, 3, 0, 0)$, $g_2^\top = (1, 1, 0, 1, 0)$, $g_3^\top = (5, 5, 0, 0, 3)$ are five canonical and minimal semiflows. $\|f_1\|$ or $\|f_2\|$ are not minimal. $f_1$ and $f_2$ are linear combinations of $g_1, g_2, g_3$ over $\mathbb{Q}^+$: $f_1 = \frac{1}{3}(2g_1 + g_3)$ and $f_2 = \frac{1}{3}(g_1 + 2g_3)$. Therefore, the decomposition of a semiflow on $\{f_1, f_2, g_1, g_2, g_3\}$ is not unique. Moreover, $G_1 = \{g_1, g_2, g_3\}$ is a generating set over $\mathbb{Q}^+$ or over $\mathbb{Q}$.

However, a minimal semiflow does not necessarily belong to a generating set over $\mathbb{Q}^+$ or $\mathbb{Q}$. In Fig. 1, $G_1$ does not include $f_1$, which is minimal or in Fig. 2 where $G_3$ does not include $g_4$ which is of minimal support.

<figure><img src="image_4.png" /></figure>

**Fig. 2.** $f^\top = (1, 1, 1, 1)$, $g_1^\top = (0, 1, 1, 0)$, $g_2^\top = (0, 1, 0, 1)$, $g_3^\top = (1, 0, 1, 0)$, $g_4^\top = (1, 0, 0, 1)$ are five canonical semiflows. $f$ is not minimal and $\|f\|$ is not minimal. $G_2 = \{g_1, g_2, g_3, g_4\}$ is the unique generating set over $\mathbb{N}$ and $f = g_1 + g_4 = g_2 + g_3$ has exactly two different decompositions in $G_2$. $G_3 = \{g_1, g_2, g_3\}$ is a generating set over $\mathbb{Q}$.

<footnote n="5">⁵ If $\mathcal{E}$ were infinite, the construction could still be used since the decreasing sequence is bounded by 0 and $\mathbb{N}$ is nowhere dense, and we would have:</footnote>

<footnote>$$ \lim_{n \to \infty} f - \sum_{j=1}^{j=n} k_j e_j = 0 \text{ with the same definition of the coefficients } k_j \text{ as in ii).} $$</footnote>
## 4.2 Decomposition over Semiflows of Minimal Support

**Theorem 2.** If $I$ is a minimal support then

i) there exists a unique minimal semiflow $f$ such that $I = \|f\|$ and $\forall g \in \mathcal{F}^+$ such that $\|g\| = I, \exists k \in \mathbb{N}$ such that $g = kf$,

ii) any non-null semiflow $g$ such that $\|g\| = I$ constitutes a generating set over $\mathbb{Q}^+$ or $\mathbb{Q}$ for $\mathcal{F}_I^+ = \{g \in \mathcal{F}^+ | \|g\| = I\}$.

In other words, $\{f\}$ is a unique generating set over $\mathbb{N}$ for $\mathcal{F}_I^+ = \{g \in \mathcal{F}^+ | \|g\| = I\}$. However, this uniqueness property is indeed 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}$.

From Sperner's theorem, any support $I$ of a semiflow contains a finite number $m$ of minimal supports of semiflows. The following theorem states that these $m$ supports cover $I$, and provide a generating set deduced from these $m$ supports.

**Theorem 3.** (decomposition) Any support $I$ of semiflows is covered by the finite subset $\{I_1, I_2, \dots, I_m\}$ of minimal supports of semiflows included in $I$:

$$I = \bigcup_{i=1}^{i=m} I_i.$$

Moreover, $\forall f \in \mathcal{F}^+$ such that $\|f\| = I$, one has $f = \sum_{i=1}^{i=m} \alpha_i g_i$ where $\alpha_i \in \mathbb{Q}^+$ and the semiflows $g_i$ are such that $\|g_i\| = I_i$.

A sketch of proof of Theorem 3 can be found in [5], a complete proof in [19].

# 5 Canonical Semiflows

A semiflow is *canonical* ([7,8] p. 68) if and only if the gcd of its non-null coordinates is equal to one. In [6], such a semiflow is said to be *scaled back*.

## 5.1 Canonical and Minimal Semiflows

Minimal semiflows and canonical semiflows are two different notions. The following lemma and theorem help to compare them.

**Lemma 2.** If a semiflow is minimal then it is canonical.

*If a semiflow is canonical and its support is minimal then it is minimal.*

The first point is quite evident: if $f$ is not canonical its gcd $k$ is such that $k > 1$ so $\exists g \in \mathcal{F}^+$ such that $f = kg$ and $f$ would not be minimal.

The second point is a direct application of Theorem 2. $\square$

However, canonical semiflows are not necessarily minimal semiflows; minimal semiflows do not necessarily have a minimal support. For example, Fig. 1, $f_1$ and $f_2$ are canonical and minimal, but their support is not minimal. Any semiflow $f = a g_1 + b g_2$ where $a, b \in \mathbb{N}$ and $a + b > 0$ is canonical and clearly not minimal. As $a$ and $b$ can be arbitrarily large, this shows that the number of canonical semiflows can be infinite.
## 5.2 About the Number of Canonical Semiflows

We can observe in the previous example that the infinite sequence of canonical semiflows is constituted of semiflows with non-minimal support. This is hinted on the following theorem.

**Theorem 4.** Given a support $I$, $c_I = |\{f \text{ canonical semiflow } | \|f\| = I\}|$, If $I$ is a minimal support, then $c_I = 1$, else $c_I$ is infinite. If $c_I = 1$, then $I$ is minimal.

From Theorem 2, there is a unique minimal semiflow having a given minimal support. From Lemma 2, a minimal semiflow is canonical. Hence, if $I$ is minimal, then $c_I = 1$.

If $I$ is not minimal, then $\exists e, f \in \mathcal{F}^+$ such that $\|e\| \subset \|f\| = I$. We can build an infinite sequence of semiflows $f_i, i \in \mathbb{N}$, such that $f_i = \alpha_i(f + k_i e)$, where $k_i \in \mathbb{N}$ and $1/\alpha_i$ is the gcd of the non-null coordinates of $f + k_i e$. $\forall i \in \mathbb{N}, f_i$ is canonical by construction. Let's consider $i, j$ such that $f_i = f_j$; then $\alpha_i(f + k_i e) = \alpha_j(f + k_j e)$. This leads to: $(\alpha_i - \alpha_j)f = (k_i - k_j)e$. However, since $\|e\| \subset \|f\|$, we must have $\alpha_i = \alpha_j$ and $k_i = k_j$. Hence, we built an infinite sequence of canonical semiflows based upon an infinite sequence of non-negative integers.

If $c_I = 1$ then let $f$ be the unique canonical semiflow of support $I$. Let's consider $g \in \mathcal{F}^+$ such that $\|g\| \le I$. With the same construction as before, we can build a canonical semiflow $h = \alpha(f + kg)$ where $1/\alpha$ is the gcd of the non-null coordinates of $f + kg$, and $k \in \mathbb{N}$. We have $\|h\| = I$ and $c_I = 1$; therefore, $h = \alpha(f + kg) = f$. Then, $g = ((1-\alpha)/k\alpha)f$ which means that any semiflow of support included in $I$ is a multiple of $f$. Hence, $I$ is minimal. $\square$

The fact that the number of canonical semiflows can be infinite was already pointed out in [6,7,13]. The fact that this number is infinite only when the considered support is non minimal as described in Theorem 4 is new to the best of our knowledge.

# 6 Minimal Generating Sets, Least Generating Sets, and Fundamental Sets

Minimal generating sets have been defined over $\mathbb{N}$ in [19] and over $\mathbb{Q}^+$ in [19,20], and least generating sets over $\mathbb{Q}$ in [7,11]. Similarly to the notion of generating set defined in Sect. 3.1, we slightly extend their definition to hold over a set $S \in \{\mathbb{N}, \mathbb{Q}^+, \mathbb{Q}\}$.

From [20] p. 39, a *minimal generating set* over $S$ is a generating set that does not strictly include any generating set.

From [7] p. 82, or [8] p. 68, a *least generating set of semiflows* "is made up of the least number of elements to generate any semiflow" over $S^6$ In other words, $\mathcal{G}$ is a least generating set if and only if it does not exist a generating set $\mathcal{H}$ such that $|\mathcal{H}| \le |\mathcal{G}|$.

<footnote n="6">⁶ More precisely, the least generating set is defined over $\mathbb{Q}$ in [7,8] and over $\mathbb{N}$ in [6].</footnote>
## 6.1 Coincidence Between Minimal and Least Generating Sets

A minimal generating set is defined with respect to set inclusion while a least generating set is defined with respect to its cardinality. In the case of generating sets of semiflows, Theorem 5 hereunder is a new result stating that these two different notions are in fact equivalent over $\mathcal{S}$.

**Lemma 3.** If $\mathcal{G}$ is a generating set over $\mathbb{Q}^+$ or $\mathbb{N}$, I a minimal support, then $\exists g \in \mathcal{G}$ such that $I = \|g\|$.

We consider $e$ a semiflow of minimal support, $\mathcal{G} = \{g_1, \dots, g_k\}$, a generating set over $\mathbb{Q}^+$ or $\mathbb{N}$. Then, $e = \sum_{i=1}^{i=k} \alpha_i g_i$. All the coefficients are non-negative and $e \neq 0$, then $\exists j \leq k$ such that $\alpha_j > 0$ and $e \geq \alpha_j g_j$. Since $\|e\|$ is minimal, $\|e\| = \|g_j\|$. $\square$

This lemma states that any generating set over $\mathbb{Q}^+$ or $\mathbb{N}$ contains at least one semiflow per minimal support. Indeed, this property is not true over $\mathbb{Q}$. In Fig. 2, $\mathcal{G}_2$ is a minimal generating set over $\mathbb{Q}^+$ and $\{g_2, g_3, g_4\} \subset \mathcal{G}_2$ is a generating set over $\mathbb{Q}$ since $g_1 = g_2 + g_3 - g_4$ is of minimal support but generated over $\mathbb{Q}$ (since one coefficient is negative) by the other minimal semiflows of minimal support.

**Theorem 5.** If $\mathcal{G}$ is a generating set over $\mathcal{S}$, where $\mathcal{S} \in \{\mathbb{N}, \mathbb{Q}^+, \mathbb{Q}\}$ then the two following properties are equivalent:

* $\mathcal{G}$ is a minimal generating set,

* $\mathcal{G}$ is a least generating set.

First, the fact that a least generating set is a minimal generating set is straightforward.

Let's consider $\mathcal{G}$, a minimal generating set over $\mathbb{N}$. By applying Theorem 1, we conclude that $\mathcal{G}$ is the set of minimal semiflows and a least generating set.

Next, let's consider $\mathcal{G}$, a minimal generating set over $\mathbb{Q}^+$. Then, Lemma 3 can apply stating that $\mathcal{G}$ includes $\mathcal{G}'$ a family of exactly one semiflow for each minimal support. From Theorem 3, we draw that $\mathcal{G}'$ is a generating set. $\mathcal{G}$ is minimal then $\mathcal{G} = \mathcal{G}'$. This being true for any minimal generating set, $\mathcal{G}$ is also a least generating set.

Finally, let's consider $\mathcal{G}$ a generating set over $\mathcal{Q}$. From $\mathcal{G}$ we can extract a subset $\mathcal{B}$ of linearly independent semiflows (see [14] p. 85 for basic results on vector spaces). Then, $\mathcal{B}$ is a least and minimal generating set over $\mathcal{Q}$. $\square$

## 6.2 About Fundamental Sets

Theorem 4 states that there is exactly one canonical semiflow for each minimal support. This particularity characterizes the notion of a fundamental set.

In [24] p. 319, the set of all canonical semiflows of minimal support is called a *fundamental set*.

**Corollary 1.** (*fundamental set*) A *fundamental set* is a generating set over $\mathbb{Q}^+$ or $\mathbb{Q}$ but not necessarily over $\mathbb{N}$. A *fundamental set* over $\mathbb{Q}^+$ is a minimal generating set but not necessarily over $\mathbb{Q}$.
The first point of this corollary is a direct consequence of Theorem 3 and Lemma 2: we conclude that a fundamental set is one possible generating set over $Q^+$ and therefore over $Q$.

The second point is directly deduced from the first point and Lemma 3.

The last parts of the two points of the corollary are illustrated by the two
following counterexamples.

In Fig. 1, $\mathcal{G}_1 = \{g_1, g_2, g_3\}$ is a fundamental set that is not a generating set over $\mathbb{N}$ since $f_1$ or $f_2$ are minimal and cannot be decomposed as a linear combination of elements of $\mathcal{G}_1$ over $\mathbb{N}^7$.

A fundamental set over $\mathbb{Q}$ is not necessarily a minimal generating set; in Fig. 2, $\mathcal{G}_2$ is the fundamental set and is not a minimal generating set. $\square$

Belonging to a least generating set, hereunder denoted by *lgs*, does not equip
a semiflow *f* with specific properties<fnref n="8" />:

- if $f \in \text{lgs}$ over $\mathbb{N}$, then $f$ is minimal but not necessarily canonical or of minimal support;

- if $f \in \text{lgs}$ over $Q^+$, then $f$ has a minimal support but is not necessarily canonical or minimal;

- if $f \in \text{lgs}$ over $\mathbb{Q}$, then $f$ is not necessarily minimal and not necessarily canonical or of minimal support.

6.3 About Uniqueness

**Corollary 2.** (uniqueness) The set of minimal semiflows is the unique minimal generating set over $\mathbb{N}$.

If $\mathcal{G}$ is a least generating set over $Q^+$ then for any minimal support $I$ of semiflows, $\exists g \in \mathcal{G}$ unique such that $I = \|g\|$.

The fundamental set is the unique minimal generating set of minimal semi-flows over $Q^+$.

The first point can be directly deduced from Theorem 1, the second and third
are directly deduced from Theorems 2 and 3 and Lemma 2. $\square$

The third point of this corollary can be considered as a variation of a statement in [24].

However, a minimal generating set over $Q^+$ or $\mathbb{Q}$ is not unique even among
minimal semiflows of minimal support. In the example of Fig. 2,

$\{k_1g_1, k_2g_2, k_3g_3, k_4g_4\}$ where $k_i \in \mathbb{N}$ constitutes a family of minimal generating sets over $Q^+$. Moreover, $\mathcal{G}_3 = \{g_1, g_2, g_3\}$ and $\{g_2, g_3, g_4\}$ are two minimal generating sets over $\mathbb{Q}$.

<footnote n="7">⁷ In this regard, the statement p. 143–147 of [6] should be rewritten.</footnote>

<footnote n="8">⁸ The properties 2.2 p. 82 of [7] and 5.2.5 p. 68 of [9] should be rewritten by taking the following statements into account.</footnote>
# 7 Results Summary

We have seen through several counterexamples that no result must be taken for granted and that any proposition must be carefully addressed. Figure 3 summarizes the main results presented in this paper.

<table><caption>**Fig. 3.** gs, fs, mgs, lgs denote the generating set, the fundamental set, the minimal generating set, and the least generating set respectively.</caption><thead><tr><th></th><th>N</th><th>Q<sup>+</sup></th><th>Q</th></tr></thead><tbody><tr><td>Theorem application domain</td><td>Theorems 1, 2, 4, 5</td><td>Theorems 2, 3, 4, 5</td><td>Theorems 2, 4, 5</td></tr><tr><td>Minimality and uniqueness</td><td>{minimal semiflows} = unique mgs</td><td>mgs={one semiflow per minimal support} fs = unique mgs of minimal semiflows</td><td>An mgs is a basis<br>No uniqueness</td></tr><tr><td>Theorem 2<br>I minimal support |{minimal semiflow of support I}|=1</td><td>{f minimal semiflow} = unique mgs = fs</td><td>Any semiflow of support I is a mgs for {semiflow f | I = ||f||}</td><td>Any semiflow of support I is an mgs for {semiflow f | I = ||f||}</td></tr><tr><td>Corollary 1<br>fs= {canonical semiflows of minimal support}</td><td>fs not always a gs</td><td>fs is a mgs among others</td><td>fs is not necessarily an mgs</td></tr><tr><td>Theorem 5</td><td>mgs = lgs</td><td>mgs = lgs</td><td>mgs = lgs</td></tr></tbody></table>

Our contribution in terms of new results consists of the following:

- the first three theorems in Sect. 4, which have been slightly extended with a new proof for Theorem 1 and could be used for infinite Petri Nets [22];

- Lemma 2 and Theorem 4 of Sect. 5 about comparing minimal and canonical semiflows;

- Lemma 3 and Theorem 5 about the equivalence between minimal and least generating sets;

- Corollaries 1 and 2 about fundamental sets and uniqueness.

# 8 Reasoning with Invariants, an Example

The example described in Fig. 4 is a reduced<fnref n="9" /> version of a Petri Net published in [16] representing two subscribers, “a caller” and a “callee”, having a conversation

<footnote n="9">⁹ See [5, 11] for Petri Nets reduction rules.</footnote>
(places CLA and CA respectively). Initially, they are in an idle state with places LA and A marked with one token. Signals PU, R are sent from the caller to the callee and signals S, F from the callee to the caller. The overall desired behavior is that caller and callee cannot go back to their idle state as long they have not received all the signals sent to them despite the fact that they both can hang up at any time making the order in which signals F and R are sent and received undetermined.

From their idle state (place LA), the caller can pick up their phone (transitions $t_1$) sending the signal PU to the callee. From their idle state (place A), the callee, upon receiving the signal PU, can pick up their phone (transition $t_7$), send the signal S and go to conversation (place CA) from where they can hang up (transition $t_8$) at any time sending the signal F to the caller. Receiving the signal S, the caller can go (transition $t_2$) to the conversation (place CLA). They can also hang up at any time (transitions $t_3, t_4, t_5$) sending the signal R to the callee. After hanging up via $t_4$ or $t_5$, the caller will have to wait (place W) until they receive the signal F from the callee before going back (transition $t_6$) to their initial idle state LA. The callee can go back to their idle state A only upon receiving the signal R (transition $t_9$).

The initial marking $M_0$ is such that $M_0(LA) = M_0(A) = 1$, $M_0(p) = 0$ for any other place: the modeled system is in its idle state.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** This Petri Net has exactly three minimal semiflows of minimal support constituting a minimal generating set over $Q^+$: $GB_1 = \{f_1, f_2, f_3\}$ such that: $f_1(LA) = f_1(CLA) = f_1(W) = f_1(PU) = f_1(S) = 1$, $f_1(p) = 0$ for any other place, $f_2(LA) = f_2(PU) = f_2(F) = f_2(CA) = 1$, $f_2(p) = 0$ for any other place, $f_3(CLA) = f_3(S) = f_3(R) = f_3(A) = 1$, $f_3(p) = 0$ for any other place.</figcaption></figure>
## 8.1 Optimizing Sperner's Bound

First, let us notice that inequality (3) gives us the following bound for $m$, the number of minimal supports: $m \le \binom{9}{\lfloor 9/2 \rfloor} = 126$. However, it is easy to notice that transitions $t_1, t_2, t_8$, and $t_9$ have only one input and one output, which means that any support including such an input also includes the corresponding output to satisfy the equations associated to $t_1, t_2, t_8$, and $t_9$. The bound can be optimized to: $m \le \binom{5}{\lfloor 5/2 \rfloor} = 10$. It can further be improved by reasoning on transitions $t_5$ and $t_6$ and reach $m \le 3$.

## 8.2 A Proof Scheme Using Minimal Semiflows of Minimal Support

We want to verify the following property (known as safeness [11] p. 489):

$$ \mathcal{P} = \forall M \text{ reachable from } M_0, \forall p \in P, M(p) \le 1. $$

We also want to prove that the initial marking $M_0$ is a home state (i.e., a marking such that whatever the evolution of the Petri Net, it is always possible to reach it back) from which it is easy to deduce that the Petri Net is live.

These two important properties are proven hereunder, starting from $\mathcal{GB}_1 = \{f_1, f_2, f_3\}$ the set of minimal semiflows of minimal support defined Fig. 4 without considering every reachable marking.

Similarly as in Eq. (2), three invariants can directly be drawn from $\mathcal{GB}_1$: for any reachable marking $M$ from $M_0$, $f_1^\top M = f_1^\top M_0 = 1$, $f_2^\top M = f_2^\top M_0 = 1$, $f_3^\top M = f_3^\top M_0 = 1$.<fnref n="10" />

In other words, there is exactly one token in the support of any semiflow of $\mathcal{GB}_1$. Hence, $\mathcal{P}$ is true since $P = \bigcup_{i=1}^{i=3} \|f_i\|$.

To prove that $M_0$ is a home state, we start to prove that $\mathcal{HS} = \{M \mid M(LA) = 1\}$ is a home space (i.e., a set of markings such that whatever is the evolution of the Petri Net, it is always possible to reach one element of the set). If we consider the invariant deduced from $f_2$, we know that any reachable marking $M$ is necessarily in one of the 4 following cases.

i) $M(LA) = 1$, then $M \in \mathcal{HS}$,

ii) $M(F) = 1$, since $f_2^\top M = 1$, we have $M(LA) = M(PU) = M(CA) = 0$. $f_1^\top M = f_1(CLA)M(CLA) + f_1(W)M(W) + f_1(S)M(S) = 1$ and it then remains only 3 sub-cases to explore:

ii-1) $M(CLA) = 1$, $t_3$ can occur from $M$ and we can reach $M' \in \mathcal{HS}$

ii-2) $M(W) = 1$, $t_6$ can occur from $M$ and we can reach $M' \in \mathcal{HS}$

ii-3) $M(S) = 1$, $t_2$ can occur from $M$ then we are in the sub-case ii-1).

iii) $M(CA) = 1$, $t_8$ can occur from $M$ then we are in the case ii).

iv) $M(PU) = 1$, then considering the invariants deduced from $f_1$ and $f_2$, we have: $M(LA) = M(CLA) = M(W) = M(F) = M(S) = M(CA) = 0$

From $f_3^\top M = 1$, we have two sub-cases:

iv-1) $M(A) = 1$, $t_7$ can occur from $M$ then we are in the case iii).

iv-2) $M(R) = 1$, $t_9$ can occur then we are in the case iv-1) again.

<footnote n="10">¹⁰ In the following, we will omit the phrase “for any reachable marking $M$ from $M_0$”.</footnote>
From these simple 4 cases and 5 sub-cases, we directly deduce that $\mathcal{HS}$ is a
home space from where it is easy to conclude that $M_0$ is a home state and the
Petri Net is live.

## 8.3 Further Remarks

We let interested readers develop the same proof scheme from $\mathcal{GB}_2 = \{f_1, g = f_2 + f_3, h = f_1 + f_3\}$ or from $\mathcal{GB}_3 = \{g, h, l = f_1 + f_2\}$ which are minimal generating sets over $\mathbb{Q}$ and find out that the analysis becomes more complex even with small additional changes. We conclude that the smaller the support, the more effective the analysis will be since the number of cases and sub cases of the proof scheme depends on the number of elements of each considered support.

The same proof scheme can be used with a colored Petri Net or the same Petri Net enriched with two parameters to model $x$ callers and $y$ callees. In the latter, the initial marking $M_0$ becomes: $M_0(LA) = x$, $M_0(A) = y$, $M_0(p) = 0$ for any other place $p$. $\mathcal{GB}_1$ is unchanged, but its three associated invariants become: $f_1^\top M = f_1^\top M_0 = x$, $f_2^\top M = f_2^\top M_0 = x$, $f_3^\top M = f_3^\top M_0 = y$. To prove that $\mathcal{HS} = \{M \mid M(LA) = x\}$ is a home space, we can start from a marking $M$ that satisfies $f_2^\top M = x$ and build a sequence of transitions $\sigma_1$ that will reach a marking $M'$ such that $M'(PU) < M(PU)$. $\sigma_1$ can then be iterated until a marking of $\mathcal{HS}$ is finally reached. From there, it becomes easy to prove that the Petri Net is live. At last, with the same scheme, it can be proven that $\mathcal{HS}_c = \{M \mid M(CLA) = M(CA) = z \text{ and } z \le \min(x,y)\}$ is a home space meaning that it is always possible to have $z$ subscribers in a conversation.

# 9 Conclusion

By considering $\mathbb{N}$, then $\mathbb{Q}^+$, then $\mathbb{Q}$, the size of a minimal generating set decreases as expected since an increasing amount of possibilities to combine semiflows are provided. More interestingly, if $m$ is the number of minimal supports in a Petri Net then:

* a minimal generating set over $\mathbb{N}$ is finite and has at least $m$ elements,

* a minimal generating set over $\mathbb{Q}^+$ has exactly $m$ elements,

* a minimal generating set over $\mathbb{Q}$ has, at most, $m$ elements.

Moreover, we were able to regroup and clarify some key algebraic results scattered in the literature by considering only the two notions of minimality in terms of semiflow and support respectively.

The example of Sect. 8 showed how loose the Sperner’s bound is, as well as a first pathway to improve upon it by considering the connections imposed by the homogeneous system of Eq. (1). The same example provides reasons to consider non-negative semiflows of minimal support. With that said, a comprehensive complexity analysis of the complete process of computing a generating set along with analyzing a Petri Net properties is required in order to quantitatively evaluate the trade-off between manipulating a generating set over $\mathbb{Q}^+$ or over $\mathbb{Q}$. Let
us also point out that in the literature, there exist additional reasons to consider
minimal supports described, for instance in [9].

We claimed that results in [6] or in [8] p. 68 need to be rephrased in consid-
ering the formulation by the same authors in one of their previous publications
[24].

We believe that these results may be enriched along two different alleys. From
a mathematical point of view, the relation with integer linear programming or
convex geometry has been investigated many times, particularly in [7], however,
we believe it could be fruitful to look at the notion of toric varieties and saturated
semigroups [21]. From a Petri Net and, even more broadly, from a transition
system theory point of view, applying these new results to a variety of models
(for example, colored Petri Nets or any transition system that can be associated
with a system of equations such as (1)) remains to be done. On another note,
supports of semiflows can be considered as a specific structure of places such as
siphons or traps [3, 5, 11]. It would be worth investigating their relationship since
a support of a semiflow is, at the same time, a trap and a siphon.

Finally, we would like to stress the possibility to automate the proof scheme
exhibited throughout the example of Sect. 8. Even though some proof steps can
be shortened, we chose to develop our proofs in a systematic way to provide a
clear road map on how an algorithm could proceed for solving such properties.

**Acknowledgements.** the author is grateful to Claude Girault who helped with the
many comments and the organization of this paper. Many thanks to Pierre Jouvelot,
Bethany Cagnol as well as the anonymous reviewers of this conference the help of whom
was greatly appreciated and led to its improvement.

References

1. Alaiwan, H., Memmi, G.: Algorithmes de recherche des solutions entières positives d'un système linéaire d'équations homogènes. Revue Technique Thomson-CSF 14(1), 125-135 (1982)

2. Alon, N., Berman, K.A.: Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory. J. Comb. Theory A 43, 91–97 (1986)

3. Barkaoui, K., Pradat-Peyre, J.-F.: On liveness and controlled siphons in petri nets. In: Billington, J., Reisig, W. (eds.) ICATPN 1996. LNCS, vol. 1091, pp. 57–72. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61363-3_4

4. Bozga, M., Esparza, J., Iosif, R., Sifakis, J., Welzel, C.: Structural invariants for the verification of systems with parameterized architectures. In: TACAS 2020. LNCS, vol. 12078, pp. 228–246. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45190-5_13

5. Brams, G.W.: Réseaux de Petri: Théorie et Pratique. Masson, Paris, France (1982)

6. Ciardo, G., Mecham, G., Paviot-Adet, E., Wan, M.: P-semiflow computation with decision diagrams. In: Franceschinis, G., Wolf, K. (eds.) PETRI NETS 2009. LNCS, vol. 5606, pp. 143–162. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02424-5_10
7. Colom, J.M., Silva, M.: Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal p-semiflows. In: Rozenberg, G. (ed.) ICATPN 1989. LNCS, vol. 483, pp. 79–112. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-53863-1_22

8. Colom, J.M., Silva, M., Teruel, E.: Properties. In: Girault, C., Valk, R. (eds.) Petri Nets for Systems Engineering, pp. 53–72. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-05324-9_6

9. Colom, J.M., Teruel, E., Silva, M., Haddad, S.: Structural methods. In: Girault, C., Valk, R. (eds.) Petri Nets for Systems Engineering, pp. 277–316. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-05324-9_16

10. Dworzanski, L.W., Lomazova, I.A.: Structural place invariants for analyzing the behavioral properties of nested petri nets. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 325–344. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39086-4_19

11. Girault, C., Valk, R.: Petri Nets for Systems Engineering, A guide to Modeling, Verification, and Applications. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-05324-9_9

12. Johnston, M.D., Anderson, D.F., Craciun, G., Brijder, R.: Conditions for extinction events in chemical reaction networks with discrete state spaces. J. Math. Biol. 76(6), 1535–1558 (2018)

13. Krückeberg, F., Jaxy, M.: Mathematical methods for calculating invariants in petri nets. In: Rozenberg, G. (ed.) APN 1986. LNCS, vol. 266, pp. 104–131. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-18086-9_22

14. Lang, S.: Algebra. GTM, 3rd edn. Springer, New York (2002). https://doi.org/10.1007/978-1-4613-0041-0

15. Lasserre, J.B., Mahey, P.: Using linear programming in petri net analysis. RAIRO RO 23(1), 43–50 (1989)

16. Martin, R., Memmi, G.: Specification and validation of sequential processes communicating by FIFO channels. In: 4th International Conference on Software Engineering for Telecommunication Switching Systems, Warwick U. Conventry, U.K., pp. 54–57. SIEE (1981)

17. Martinez, J., Silva, M.: A simple and fast algorithm to obtain all invariants of a generalised petri net. In: Girault, C., Reisig, W. (eds.) Application and Theory of Petri Nets, pp. 301–310. Springer, Heidelberg (1982). https://doi.org/10.1007/978-3-642-68353-4_47

18. Memmi, G.: Semiflows and invariants. Application in petri nets theory. In: Journées d'Etudes sur les Réseaux de Petri AFCET-Institut de Programmation), pp. 145–150 (1977)

19. Memmi, G.: Fuites et Semi-flots dans les Réseaux de Petri. Thèse de Docteur-Ingénieur, U. P. et M. Curie, Paris, France (1978)

20. Memmi, G.: Methodes d'analyse de Réseaux de Petri, Réseaux a Files, Applications au temps reel. Thèse d'Etat, U. P. et M. Curie, Paris, France (1983)

21. Oda, T.: Convex Bodies and Algebraic Geometry (An Introduction to the Theory of Toric Varieties). Springer, Heidelberg (2012)

22. Petri, C.A.: Nets, time, and space. TCS 153(1), 3–48 (1996)

23. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1987)

24. Silva, M., Teruel, E., Colom, J.M.: Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 309–373. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_19
25. Sperner, E.: Ein satz über untermengen einer endlichen menge. Mathematische
Zietschrift **27**, 544–548 (1928)

26. Toudic, J.M.: Algorithmes d'Analyse structurelle des Réseaux de Petri. Thèse de 3ème cycle, U. P. et M. Curie, Paris, France (1981)

27. Wolf, K.: How petri net theory serves petri net model checking: a survey. In: Koutny, M., Pomello, L., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency XIV. LNCS, vol. 11790, pp. 36–63. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-60651-3_2