Symbolic Model Checking using Intervals of Vectors Damien Morard Computer Science Department, Faculty of Science, University of Geneva, Switzerland damien@morard.me, Lucas Donati Computer Science Department, Faculty of Science, University of Geneva, Switzerland lucas.donati@etu.unige.ch, Didier Buchs Computer Science Department, Faculty of Science, University of Geneva, Switzerland didier.buchs@unige.ch Abstract Model checking is a powerful technique for software verification. However, the approach notably suffers from the infamous state space explosion problem. To tackle this, in this paper, we introduce a novel symbolic method for encoding Petri net markings. It is based on the use of generalised intervals on vectors, as opposed to existing methods based on vectors of intervals such as Interval Decision Diagrams. We develop a formalisation of these intervals, show that they possess homomorphic operations for model checking CTL on Petri nets, and define a canonical form that provides good performance characteristics. Our structure facilitates the symbolic evaluation of CTL formulas in the realm of global model checking, which aims to identify every state that satisfies a formula. Tests on examples of the model checking contest (MCC 2022) show that our approach yields promising results. To achieve this, we implement efficient computations based on saturation and clustering principles derived from other symbolic model checking techniques. Symbolic Model Checking using Intervals of Vectors 1 Introduction In the ever-evolving landscape of computer science and software engineering, the correctness and reliability of software systems remain paramount concerns. In response to these challenges, the discipline of model checking has emerged as a powerful tool in the arsenal of software verification and validation. Model checking [ 11 ] is a formal verification technique used to ensure that a system adheres to its specifications and requirements. However, although model checking is a trustworthy and robust method, it is confronted with a variety of challenges. One of the most significant ones is the state space explosion problem [ 10 , 18 ] . This problem arises when dealing with complex software or hardware systems, where the number of possible states and transitions within a model grows exponentially with its size. The task becomes more challenging when the objective is to identify all states that adhere to a given property, as opposed to merely determining the validity of the property within a specific configuration. Moreover, our objective is to address the issue of global model checking , namely, to identify all states that fulfill a CTL (Computation Tree Logic) [ 8 ] formula. While various techniques have been developed to mitigate the state space explosion problem, such as Decision diagrams [ 1 , 13 , 14 ] , abstractions [ 9 ] , partial order reduction [ 21 ] , and many others, it has become evident that this challenge will persist as models become more sophisticated. Therefore, the quest for innovative methods to address this issue remains a compelling area of research. As always, each new approach inevitably brings its own set of advantages and disadvantages compared to existing techniques. This paper focusses on a symbolic method inspired by [ 22 ] that proposes to encode sets of markings in Petri net models with vectors that act as boundaries on the markings, similar to intervals. As markings are essentially vectors of values, and fireability of transitions are lower constraints and their negation are upper constraints, intervals seem to be a suitable choice for representing the satisfiable states of a CTL formula. However, expressing intervals on vectors is complicated, since vectors are not always comparable. We introduce such notions and demonstrate that, for non-total orders, we require additional information such as a set of lower and upper bounds, rather than a single bound as in intervals of natural numbers. Merely efficiently representing sets of markings is insufficient; we therefore also define homomorphic operations (w.r.t. union) on the symbolic structure to directly perform model checking on it. Thanks to this encoded structure and operations, we can efficiently maintain the same structure and remain in the symbolic domain, without the need to decode it to perform computation over the encoded values. Furthermore, we introduce a canonical form incorporating optimisations to make it efficient to use in the context of CTL model checking. We tested our approach on examples from the model checking contest [ 16 ] , yielding very promising results. The paper is organised as follows: firstly, in Section 2 , we provide an overview of our project. Next, in Section 3 , we present the complete formalism of our symbolic structure. In Section 4 , we demonstrate the connection between this symbolic structure and Petri nets to apply CTL model checking. Finally, Section 5 presents our results using this technique. This paper is an extended version of the paper published in Petri Nets 2024 [ 19 ] . 2 Informal presentation In the context of Petri nets, as illustrated in Figure 1 , the states of a model are represented using markings . A marking can be viewed as a vector where each place is associated with a natural number that indicates the number of resources. In our example, (3,1) is the current marking of the Petri net. Model checking Petri nets consists in being able to answer queries such as ”How many resources are required at each place to make t_{0} fireable ?”. Two perspectives on the problem are possible from this question. The first seeks all states that satisfy the query, namely global model checking [ 23 ] . The second checks whether a specific state satisfies the query, corresponding to local model checking . Obviously, because it computes the entire state space for a query, global model checking also provides an answer for any given state, making it more general than the local approach. In particular, such a space is often infinite, meaning that a simple explicit enumeration of all states is impossible, as would be the case for the property of making t_{0} fireable. Our approach uses a new structure called symbolic vector , described by a couple (a,b) , where a and b represent sets of markings. To belong to (a,b) , a given marking must include (given a partial order relation on vectors) all the markings in a and none of the markings in b . This is a generalisation of the interval concept to vectors. Indeed, membership in a natural number interval [a,b] can be expressed as \forall x\in\mathbb{N},a\leq x\leq b , which can equivalently be formulated as \forall x\in\mathbb{N},a\leq x\land b\not1 and sv,sv^{\prime}\in\mathbb{SV} . The difference between two symbolic vector sets, noted \setminus_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\times\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined inductively as: \displaystyle svs\setminus_{svs}\varnothing_{svs} \displaystyle=svs,~\varnothing_{svs}\setminus_{svs}svs=\varnothing_{svs} \displaystyle\{sv\}\setminus_{svs}\{sv^{\prime}\} \displaystyle=sv\setminus_{sv}sv^{\prime} \displaystyle\{sv\}\setminus_{svs}\{sv_{1},\dots,sv_{n}\} \displaystyle=(sv\setminus_{sv}sv_{1})\setminus_{svs}\{sv_{2},\dots,sv_{n}\} \displaystyle\{sv_{1},\dots,sv_{n}\}\setminus_{svs}svs^{\prime} \displaystyle=\{sv_{1}\}\setminus_{svs}svs^{\prime}\cup_{svs}\{sv_{2},\dots,sv_{n}\}\setminus_{svs}svs^{\prime} The difference is carried out recursively by taking each left symbolic vector and applying the difference with each right symbolic vector. Moreover, since the result of \setminus_{sv} is a new set, we need to invoke \setminus_{svs} . Definition 3.26 (Negation) Let svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) be a symbolic vector set and sv\in\mathbb{SV} be a symbolic vector. The respective negation of both structures, noted \neg_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) and \neg_{sv}:\mathbb{SV}\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , are defined as: \neg_{sv}(sv)=(\{f_{\varepsilon}\},\varnothing)\setminus_{sv}sv~\text{and}~\neg_{svs}(svs)=\{(\{f_{\varepsilon}\},\varnothing)\}\setminus_{svs}svs It must be noted that the negation is defined as a complement to the whole set. Lemma 3.27 Let svs,svs^{\prime}\in\mathcal{P}(\mathbb{\mathbb{SV}}) and \ast\in\{\cup,\cap,\setminus\} be operations. Then, \\ uf_{svs}(svs)\ast uf_{svs}(svs^{\prime})=uf_{svs}(svs\ast_{svs}svs^{\prime}) and uf_{svs}(\neg_{svs}svs)=\neg uf_{svs}(svs) Definition 3.28 (Symbolic vector set relations) Let svs,svs^{\prime}\in\mathcal{P}(\mathbb{\mathbb{SV}}) be symbolic vector sets and q\in Q_{n} be a vector. Each of the relations \subseteq_{svs},\not\subset_{svs},=_{svs},\neq_{svs}\;\subseteq\mathcal{P}(\mathbb{\mathbb{SV}})\times\mathcal{P}(\mathbb{\mathbb{SV}}) and \in_{svs}\;\subseteq\mathbb{SV}\times\mathcal{P}(\mathbb{\mathbb{SV}}) are defined as follows: • svs\subseteq_{svs}svs^{\prime}\Leftrightarrow svs\setminus_{svs}svs^{\prime}\in\varnothing_{svs} • svs\not\subset_{svs}svs^{\prime}\Leftrightarrow svs\setminus_{svs}svs^{\prime}\notin\varnothing_{svs} 4 4 4 For legacy reasons we used the symbol \not\subset for the negation of \subseteq which could be a bit awkward • svs=_{svs}svs^{\prime}\Leftrightarrow(svs\subseteq_{svs}svs^{\prime})\land(svs^{\prime}\subseteq_{svs}svs) • svs\neq_{svs}svs^{\prime}\Leftrightarrow(svs\not\subset_{svs}svs^{\prime})\lor(svs^{\prime}\not\subset_{svs}svs) • q\in_{svs}svs\Leftrightarrow\exists sv\in svs,q\in_{sv}sv The general set relations are expanded to directly work on sets of symbolic vectors. Their constructions are based on the operations described previously. 3.3 Total order, mergeability and shareability of symbolic vector sets Establishing a canonical form for symbolic vector sets requires a deep understanding of the interactions that may occur between symbolic vectors, in much the same way as one must understand the interactions between integer intervals in order to reduce them effectively. Among the conditions involved is the need to prevent overlap between intervals, which corresponds to avoiding the inclusion of the same value in two distinct symbolic vector sets. Additionally, another scenario may arise when two intervals share no values, but can be merged into a single one. For instance, the two intervals [1,4] and [5,7] in natural numbers can be combined into [1,7]. Therefore, symbolic vector sets must take into account these conditions. \displaystyle uf_{svs}(\{(\{(2,4)\},\varnothing),(\{(4,2)\},\{(4,4)\})\}) \displaystyle~~~~~~~~~~~~~~~~~~~~~~~~~~= \displaystyle uf_{svs}(\{(\{(2,4)\},\{(4,4)\}),(\{(4,2)\},\varnothing)\}) Figure 4 : Two symbolic vector sets with the same underlying set of vectors. (2,4) (4,2) (4,4) ... Figure 5 : Visualisation of the two symbolic vector sets. Figure 6 : Illustration of the canonical issue encountered with the non-strict partial order on its vectors, where (\{(4,4)\},\varnothing) is potentially contained in both symbolic vectors. However, addressing the aforementioned cases is insufficient to guarantee future canonicity due to the non-strict partial order of its elements. Figure 6 depicts a scenario in which two symbolic vectors do not share values and cannot be merged. Despite this, two different sets exist, resulting in an equivalent final underlying set of vectors. The issue arises because the value within the symbolic vector (\{(4,4)\},\varnothing) may be included in both symbolic vectors. The visualisation in Figure 5 offers an initial explanation of this phenomenon. The nodes are arranged according to their vectors, with the lowest at the bottom and the largest at the top. Vector (4,4) serves as a join point where the two symbolic vectors share the above values. Moreover, vector (4,4) can be moved over both excluding sets to transfer the constraint, leading to two different representations for the same underlying set. Thus, it is imperative to establish a deterministic rule for selecting the symbolic vector that should encompass the constraint. To address this, we introduce a total order on symbolic vectors. Definition 3.29 (Lexicographic ordering) Let q=(x_{1},\dots,x_{n}),q^{\prime}=(y_{1},\dots,y_{n})\in Q_{n} . The lexicographic ordering, noted \leq_{f}:Q_{n}\times Q_{n}\rightarrow\mathbb{B} , is defined as: \displaystyle()\leq_{f}() \displaystyle=true \displaystyle(x_{1},\dots,x_{n})\leq_{f}(y_{1},\dots,y_{n}) \displaystyle=\begin{cases}true&x_{1}0 be canonical symbolic vector sets. The canonical union of two symbolic vector sets, noted \cup^{c}_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\times\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined as: Given: \displaystyle sv_{1} \displaystyle=(\{q_{a}\},b),~sv_{1}^{\prime}=(\{q_{c}\},d) \displaystyle m \displaystyle\in\mathbb{N},m\geq 0 \displaystyle svs^{\prime\prime} \displaystyle=\{sv_{1}^{\prime},\dots,sv_{m}^{\prime}\}=\{sv^{\prime}\in svs^{\prime}~|~shareable_{sv}(sv_{1},sv^{\prime})=true\} \displaystyle sh \displaystyle=share_{sv}(sv_{1},sv_{1}^{\prime}) \displaystyle\varnothing\cup^{c}_{svs}svs \displaystyle=svs \displaystyle\{sv_{1}\}\cup^{c}_{svs}svs^{\prime} \displaystyle=\begin{cases}\bm{if}&svs^{\prime\prime}\neq\varnothing\\ &\begin{cases}\bm{if}&q_{a}\leq_{f}q_{c}\\ &(merge_{sv}(sv_{1},sh)\cup_{svs}(sv_{1}^{\prime}\setminus^{c}_{sv}sh))\cup^{c}_{svs}(svs^{\prime}\setminus\{sv_{1}^{\prime}\})\\ \bm{if}&q_{c}\leq_{f}q_{a}\\ &(merge_{sv}(sv_{1}^{\prime},sh)\cup_{svs}(sv_{1}\setminus^{c}_{sv}sh))\cup^{c}_{svs}(svs^{\prime}\setminus\{sv_{1}^{\prime}\})\\ \end{cases}\\ \bm{if}&svs^{\prime\prime}=\varnothing\\ &\{sv_{1}\}\cup_{svs}svs^{\prime}\end{cases} \displaystyle\bm{if}~n>1 \displaystyle:\{sv_{1},\dots,sv_{n}\}\cup^{c}_{svs}svs^{\prime}=\{sv_{2},\dots,sv_{n}\}\cup^{c}_{svs}\{sv_{1}\}\cup^{c}_{svs}svs^{\prime} The fundamental concept underlying the union operation involves sequentially isolating each symbolic vector from the left-hand side. Subsequently, all components of the other set are examined to identify those that include a shareable part with the symbolic vector that is isolated from it. The set generated svs^{\prime\prime} contains all of these symbolic vectors. As we explained earlier, if shareability between two symbolic vectors is true, this means that a change is required to conform to canonicity. A symbolic vector is selected in svs^{\prime\prime} regardless of order. The shared part between these two symbolic vectors is extracted and stored in sh , which is then merged with the smaller symbolic vector. Given that the larger symbolic vector already contains this shared segment, a subtraction operation is applied to eliminate it. Thus, this shared part is moved from one symbolic vector to the other with respect to the total order of the functions. The same process is repeated as many times as necessary until there is only one set left. When an element no longer possesses any shared components with the other set, it is included using a conventional set union operation. Remark 3.63 Remark that the difference svs\setminus\{sv_{1}^{\prime}\} is a standard set difference operation. We remove the sv_{1}^{\prime} element that was selected in svs . Lemma 3.64 (Canonical union commutativity) Let svs,svs^{\prime}\in\mathcal{P}(PS) be two symbolic vector sets. Then, \displaystyle svs\cup^{c}_{svs}svs^{\prime}=svs^{\prime}\cup^{c}_{svs}svs Proposition 3.65 If svs,svs^{\prime}\in\mathcal{P}(\mathbb{\mathbb{SV}}) are two canonical symbolic vector sets, then svs\cup^{c}_{svs}svs^{\prime} is canonical. Definition 3.66 (Canonised SPS) Let svs=\{sv_{1},\dots,sv_{n}\}\in\mathcal{P}(\mathbb{\mathbb{SV}}),n>0 be a symbolic vector set. The canonised function that returns the canonical form of a symbolic vector set, noted can_{svs} , is defined as follows: \displaystyle can_{svs}(\varnothing) \displaystyle=\varnothing \displaystyle can_{svs}(\{sv_{1},\dots,sv_{n}\})= \displaystyle~rmEmpty(\{can_{sv}(sv_{1})\}) \displaystyle\cup^{c}_{svs}\dots\cup^{c}_{svs}rmEmpty(\{can_{sv}(sv_{n})\}) This definition breaks down the set to reconstruct it using the canonical union. Proposition 3.67 Let svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) be a symbolic vector set. Then, can_{svs}(svs) is canonical. Thanks to the canonical union, all operators on symbolic vector sets can also be written canonically, which is the subject of the following subsections. We define the canonical intersection of symbolic vector sets as follows. Definition 3.68 (Canonical intersection of symbolic vector sets) Let svs=\{sv_{1},\dots,sv_{n}\},~svs^{\prime}=\{sv_{1}^{\prime},\dots,sv_{m}^{\prime}\}\in\mathcal{P}(\mathbb{\mathbb{SV}}),n,m>0 be canonical symbolic vector sets. The definition of canonical intersection, noted \cap^{c}_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\times\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined as: \displaystyle svs\cap^{c}_{svs}\varnothing \displaystyle=\varnothing \displaystyle\varnothing\cap^{c}_{svs}svs \displaystyle=\varnothing \displaystyle svs\cap^{c}_{svs}svs^{\prime} \displaystyle= \displaystyle\begin{cases}\bm{if}&n=1\\ &rmEmpty(\{sv_{1}\cap^{c}_{sv}sv_{1}^{\prime}\})\cup^{c}_{svs}(\{sv_{1}\}\cap^{c}_{svs}\{sv_{2}^{\prime},\dots,sv_{m}^{\prime}\})\\ \bm{if}&n>1\\ &(\{sv_{1}\}\cap^{c}_{svs}svs)\cup^{c}_{svs}(\{sv_{2},\dots,sv_{n}\}\cap^{c}_{svs}svs)\end{cases} The original intersection in definition 3.20 is almost the same as the new definition. There is a slight difference in dealing with the case of an empty intersection between symbolic vectors, where no function is added to the set. Proposition 3.69 If svs,svs^{\prime}\in\mathcal{P}(\mathbb{\mathbb{SV}}) are two canonical symbolic vector sets, then svs\cap^{c}_{svs}svs^{\prime} is canonical. The canonical difference between two symbolic vectors was defined earlier in definition 3.57 . We now directly introduce the canonical difference operation for symbolic vector sets. Definition 3.70 (Canonical difference of symbolic vector sets) Let svs=(sv_{1},\dots,sv_{n}),svs^{\prime}=(sv_{1}^{\prime},\dots,sv_{m}^{\prime})\in\mathcal{P}(\mathbb{\mathbb{SV}}) be canonical symbolic vector sets. The definition of canonical difference on symbolic vector sets, noted \setminus^{c}_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\times\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined as: \displaystyle svs\setminus^{c}_{svs}\varnothing \displaystyle=svs \displaystyle\varnothing\setminus^{c}_{svs}svs \displaystyle=\varnothing \displaystyle svs\setminus^{c}_{svs}svs^{\prime} \displaystyle= \displaystyle\begin{cases}\bm{if}&n=1\\ &(sv\setminus^{c}_{sv}sv_{1})\setminus^{c}_{svs}\{sv_{2}^{\prime},\dots,sv_{m}^{\prime}\}\\ \bm{if}&n>1\\ &(\{sv_{1}\}\setminus^{c}_{svs}svs)\cup^{c}_{svs}\{sv_{2},\dots,sv_{n}\}\setminus^{c}_{svs}svs\end{cases} The canonical difference is almost the same as the original definition 3.25 . The sole distinction lies in the use of \cup^{c}_{svs} and \setminus^{c}_{sv} instead of their non-respective canonical form. Proposition 3.71 If svs,svs^{\prime}\in\mathcal{P}(\mathbb{\mathbb{SV}}) are two canonical symbolic vector sets, then svs\setminus^{c}_{svs}svs^{\prime} is canonical. The last canonical operation to explore is the negation. Definition 3.72 (Canonical negation of a symbolic vector) Let sv\in SV be a symbolic vector. The canonical negation of a symbolic vector, noted \neg^{c}_{sv}:\mathbb{SV}\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined as: \displaystyle\neg^{c}_{sv}(sv)=(\{f_{\varepsilon}\},\varnothing)\setminus^{c}_{sv}sv Definition 3.73 (Canonical negation of a symbolic vector set) Let svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) be a symbolic vector set. The canonical negation of a symbolic vector set, noted \neg^{c}_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) , is defined as: \displaystyle\neg^{c}_{svs}(svs)=\{(\{f_{\varepsilon}\},\varnothing)\}\setminus^{c}_{svs}svs Both operations remain akin to their original versions, with the exception that we employ the canonical variant of the difference operation. Proposition 3.74 If sv\in SV is a canonical symbolic vector, then \neg^{c}_{sv}(sv) is canonical. Proposition 3.75 If svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) is a canonical symbolic vector set, then \neg^{c}_{svs}(svs) is canonical. To conclude, this section has presented the necessary algebraic framework for symbolic vectors with the required operations that can be used for global model checking of Petri nets. 4 Petri net model checking using symbolic vector sets This section aims to describe the relation and application between CTL model checking and Petri nets using symbolic vector sets. 4.1 Encoding markings using symbolic vector sets Definition 4.1 (Capacity Petri net) A Petri net with capacities is a tuple \Sigma=\langle P,T,in,out,w,k,m_{0}\rangle where P is the set of finite places, T is the set of finite transitions, \text{in}\subseteq(P\times T) and \text{out}\subseteq(T\times P) are the sets of input and output arcs linking places and transitions, w:(\text{in}\cup\text{out})\rightarrow\mathbb{N}^{+} is the function labeling each arc with a weight, k:P\rightarrow\mathbb{N}^{+}\cup\{\infty\} binds each place with a value that cannot be exceeded, and m_{0}\in M represents the initial marking, belonging to the set of all markings M . We assume that w is total, returning 0 when the relations in or out are not defined. Formally, w(p,t)=0 if (p,t)\notin in and w(t,p)=0 if (t,p)\notin out . Furthermore, \mathbb{N}^{+}=\mathbb{N}\setminus\{0\} . Operators and relations on \mathbb{N} are extended to \mathbb{N}^{+}\cup\{\infty\} . A marking is denoted by a vector (n_{1},\dots,n_{m}) where n_{1},\dots,n_{m}\in\mathbb{N},m=|P| , in which each tuple location is connected to a place that indicates the number of resources. Vectors can be seen as functions of finite domain m:P\rightarrow\mathbb{N} . A transition t\in T is enabled for the marking m\in M iff \forall p\in P,w(p,t)\leq m(p)\leq k(p)-w(t,p) , where \infty-n=\infty,n\in\mathbb{N} and l\leq\infty is true for l\in\mathbb{N}\cup\{\infty\} . When a transition is enabled, it may be fired, resulting in: fire(m,t)=m^{\prime}\Leftrightarrow\forall p\in P,m^{\prime}(p)=m(p)-w(p,t)+w(t,p) . We define a function, \lambda_{in}:T\rightarrow M , called input marking, such that \forall p\in P,\lambda_{in}(t)(p)=w(p,t) . \lambda_{in} returns a marking that contains the required number of tokens to enable a transition. In the following, the definition \Sigma=\langle P,T,in,out,w,k,m_{0}\rangle is assumed for a Petri net. To apply CTL model checking on a model, a particular operation called pre is necessary. This operation is used to calculate the execution trace of a model backwards, step by step [ 26 ] . In the context of a Petri net, the pre operation serves as the inverse or opposite of the fire operation. This operation computes the set of predecessor markings for a given transition, representing the state space before the firing of the transition. In our approach, encoding the operation pre is crucial to construct the state space symbolically. The choice of Petri nets with finite capacity is crucial to ensure the decidability of our proof system, which is not the case for general Petri nets. Definition 4.2 (Reversible) Let t\in T be a transition and m\in M be a marking. The reversibility of a transition t for a marking m is defined as rev(t,m)\Leftrightarrow\forall p\in P,m(p)\leq k(p)-w(p,t) . In addition, the operation that computes its application, noted pre_{t}:M\times T\rightarrow M , is defined as: \\ \forall p\in P,pre_{t}(m,t)(p)=\begin{cases}w(p,t)&\bm{if}~m(p)\leq w(t,p)\\ m(p)+w(p,t)-w(t,p)&\bm{else}\\ \end{cases} pre_{t} may be seen as the reverse fire operation for a given transition. However, even if there are not enough tokens in the post-places, the operation is still applied, and the minimum amount of tokens is put in the in -places. Hence, the targeted transition is always fireable the next time allowing to explore all satisfiable states, related to global model checking. Our objective is not to compute the reachable configurations from a given marking, but to capture all the initial configurations satisfying a property. Thus, even if a transition does not influence a place, it should still be considered in the list of all valid initial configurations. To define the general pre operation that operates on a set of markings, it involves applying the pre_{t} operation to each marking with every transition and combining the results using the union operation. Definition 4.3 (Operation pre_{sv} ) Let sv=(a,b)\in\mathbb{SV} be a symbolic vector. The operation pre_{sv}:\mathbb{SV}\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) is defined as: \displaystyle pre_{sv}(a,b) \displaystyle=\begin{cases}\varnothing~\bm{if}~\exists t\in T,\exists q\in(a\cup b),\neg rev(t,m)\\ \bigcup_{t\in T}~(pre_{i}(a,t),pre_{e}(b,t))~\bm{else}\end{cases} \displaystyle pre_{i},pre_{e} \displaystyle:\mathcal{P}(M)\times T\rightarrow\mathcal{P}(M) \displaystyle pre_{i}(\varnothing,t) \displaystyle=\{\lambda_{in}(t)\},~pre_{e}(\varnothing,t)=\varnothing \displaystyle pre_{i}(a,t) \displaystyle=pre_{e}(a,t)=\bigcup_{m~\in~M}\{pre_{t}(m,t)\},~\bm{if}~a\neq\varnothing The operation pre_{sv} is designed to operate on each marking within the symbolic vector individually, computing its corresponding pre_{t} . Note that if one of the markings is not reversible ( \neg rev(t,m) ), the entire operation is not applied and returns \varnothing . Moreover, it preserves the capacity of Petri nets. Definition 4.4 (Operation pre_{svs} ) Let svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) . Operation pre_{svs}:\mathcal{P}(\mathbb{\mathbb{SV}})\times T\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) is defined as: pre_{svs}(svs)=\bigcup_{sv~\in~svs}~pre_{sv}(sv) Lemma 4.5 Let svs\in\mathcal{P}(\mathbb{\mathbb{SV}}) be a symbolic vector set and sv\in\mathbb{SV} be a symbolic vector. Additionally, we assume the decoded version of the pre operation on markings, where pre_{t} is computed directly on each marking for each transition. Then, pre(uf(sv))=uf(pre_{sv}(sv)) and pre(uf_{svs}(svs))=uf_{svs}(pre_{svs}(svs)) . Remark 4.6 Our approach is adaptable to models beyond Petri nets. For models other than Petri nets, encoding ”pre” is necessary to apply model checking for CTL. It remains an open question whether this is always possible with symbolic vector sets. In some cases, it can be necessary to have an infinite number of symbolic vectors, such as a Petri net representing even or odd numbers of tokens. It must be noted that construction of reachability sets in global model checking has no real meaning, as depending on the choice of initial marking any marking can be reached, this is why it is more pertinent to use CTL global model checking, i.e. the states that satisfy a given formula. 4.2 Global model checking of Petri nets with symbolic vector sets In tackling the global model checking problem, our focus has been on addressing CTL formulas. We briefly introduce the corresponding formalism and the satisfaction relation. Definition 4.7 (CTL definition and satisfaction) Let AP be a set of atomic propositions and ap\in AP . The set of CTL formulas over AP, noted \phi\in CTL , is defined as: \phi::=ap~|~\neg\phi~|~\phi\lor\phi~|~\mathbf{EX}~\phi~|~\mathbf{EG}~\phi~|~\mathbf{E}[\phi~\mathbf{U}~\phi] . We assume the usual CTL extended syntax based on formula equivalence: \mathbf{AX}~\phi , \mathbf{EF}~\phi , \mathbf{AF}~\phi , \mathbf{AG}~\phi , and \mathbf{A}[\phi~\mathbf{U}~\phi] . Let \Sigma=\langle P,T,in,out,w,k,m_{0}\rangle be a Petri net, m\in M be a marking and t\in T be a transition. The satisfaction relation is denoted as \models\,\subseteq\Sigma\times M\times CTL and its definition based on the standard literature [ 8 ] ( \Sigma is omitted in the final notation if the context is clear). Furthermore, the set of atomic propositions for our Petri nets is AP=\{isFireable(t)~|~t\in T\} such that: m\models isFireable(t)\Leftrightarrow t is enabled for m\Leftrightarrow\lambda_{in}(t)\subseteq_{f}m . \displaystyle m\models\neg\phi\Leftrightarrow\neg(m\models\phi) \displaystyle m\models true \displaystyle m\models\phi\lor\psi\Leftrightarrow m\models\phi\ or\ m\models\psi \displaystyle m\models isFireable(t)\Leftrightarrow\lambda_{in}(t)\subseteq_{f}m \displaystyle m\models\mathbf{EX}~\phi\Leftrightarrow\exists m^{\prime}\in M,t\in T,m^{\prime}=fire_{t}(m)\ and\ m^{\prime}\models\phi \displaystyle m\models\mathbf{EG}~\phi\Leftrightarrow(\forall i\in\mathbb{N},\exists t_{i}\in T,fire_{t_{i}}(m_{i})=m_{i+1}\ and\ m_{0}=m\ and\ \forall i\in\mathbb{N},m_{i}\models\phi) \displaystyle\ or(\ \exists k\ s.t.\forall i\in[0..k],\exists t_{i}\in T,fire_{t_{i}}(m_{i})=m_{i+1} \displaystyle and\ \not\exists t\in T\ s.t.fire_{t}(m_{k+1})=l\ and\ \forall i\in[0,k],m_{i}\models\phi\ ) \displaystyle m\models\mathbf{E}[\phi~\mathbf{U}~\psi]\Leftrightarrow\forall i\in\mathbb{N},\exists t_{i}\in T,fire_{t_{i}}(m_{i})=m_{i+1}\ \ and\ m_{0}=m \displaystyle and\ \exists k\in\mathbb{N},(\forall i\in[0,k],m_{i}\models\phi\ and\ \forall i>k,\ m_{i}\models\psi) \displaystyle or(\ \exists n\ s.t.\forall i\in[0..n],\exists t_{i}\in T,fire_{t_{i}}(m_{i})=m_{i+1} \displaystyle and\ \not\exists t\in T\ s.t.fire_{t}(m_{n+1})=l \displaystyle and\ \exists k\in\mathbb{N},kk,\ m_{i}\models\psi) The atomic proposition isFireable(t) is intended to observe the firing of transitions in Petri nets. It is obviously related to a particular state of the net i.e. the pre/postcondition of that transition. For \mathbf{E} and \mathbf{EU} operators we have two cases to cover the finite or infinite paths cases reflected by the or operators in the formula. We have assembled all the necessary components to provide the evaluation semantics of CTL formulas as the computation of a symbolic vector set. This semantics has been revisited on the basis of [ 22 ] . Definition 4.8 (Evaluation of a CTL formula) Let \phi,\psi\in CTL , ap\in\{isFireable(t)~|~t\in T\} , and \Sigma=\langle P,T,pre,post,w,k,m_{0}\rangle be a Petri net. The evaluation of a CTL formula as a symbolic vector set is noted \llbracket~\rrbracket:CTL\rightarrow\mathcal{P}(\mathbb{\mathbb{SV}}) . The function is defined as follows: \displaystyle\widetilde{pre}_{svs}(\llbracket\phi\rrbracket) \displaystyle=\neg_{svs}pre_{svs}(\neg_{svs}\llbracket\phi\rrbracket)~~~~~~~~~\llbracket\neg\phi\rrbracket=\neg_{svs}\llbracket\phi\rrbracket \displaystyle\llbracket true\rrbracket \displaystyle=\{(\{f_{\varepsilon}\},\varnothing)\}~~~~~~~~~~~~~~~~\llbracket\phi\lor\psi\rrbracket=\llbracket\phi\rrbracket\cup_{svs}\llbracket\psi\rrbracket \displaystyle\llbracket isFireable(t)\rrbracket \displaystyle=\{(\{pre_{t}(t)\},\varnothing)\}~~~~~~~~~~\llbracket\mathbf{EX}~\phi\rrbracket=pre_{svs}(\llbracket\phi\rrbracket) \displaystyle\llbracket\mathbf{EG}~\phi\rrbracket \displaystyle=\nu Y.\llbracket\phi\rrbracket\cap_{svs}(pre_{svs}(Y)\cup_{svs}\widetilde{pre}_{svs}(Y)) \displaystyle\llbracket\mathbf{E}[\phi~\mathbf{U}~\psi]\rrbracket \displaystyle=\mu Y.\llbracket\psi\rrbracket\cup_{svs}(\llbracket\phi\rrbracket\cap_{svs}pre_{svs}(Y)) Remark 4.9 The semantics of satisfaction and evaluation both closely resemble those of a Kripke structure. However, due to the left-total relation on Kripke structure arcs (i.e., each state has at least one arc starting from it), sink states are nonexistent. The semantics need to be adapted to account for this, expanding its scope, assuming an implicit continuation for sink states. For instance, the evaluation of \mathbf{EG} in a Kripke structure could be simplified as follows: \nu Y.\llbracket\phi\rrbracket\cap pre_{svs}(Y) , which does not require the computation of \widetilde{pre}_{svs}(Y) and the union application. Furthermore, a Petri net without sink states could also benefit from this advantage. Termination is not guaranteed, in the general unbounded case, for the smallest fixpoints ( \mu Y ) or the largest fixpoint ( \nu Y ). Theorem 4.10 Let \phi\in CTL be a CTL formula and m\in M a marking. Then, m\models\phi\Leftrightarrow m\in_{svs}\llbracket\phi\rrbracket . The theorem asserts that the satisfaction of a CTL formula for a given marking can be determined by evaluating the formula and verifying whether the marking belongs to it. This feature enables us to perform exhaustive computations to identify all states that satisfy a given formula. The perspective of computing \llbracket\phi\rrbracket aligns with the challenge of global model checking , where the focus extends beyond a single configuration. This approach guides the remainder of the article. 4.3 Use case: Mutual exclusion p_{0} p_{1} p_{3} p_{4} p_{2} t_{0} t_{3} t_{1} t_{4} k(p_{0})=\infty k(p_{1})=\infty k(p_{2})=\infty k(p_{3})=\infty k(p_{4})=\infty Figure 7 : Petri net modelling the mutual exclusion problem. Figure 7 illustrates a Petri net example containing the well-known mutual exclusion problem . Markings are displayed using the order: (p_{0},p_{1},p_{2},p_{3},p_{4}) . Avoiding mutual exclusion in this Petri net can be expressed by the property: \forall m\in M,m\models\neg(\mathbf{EF}~isFireable(t_{3})\land isFireable(t_{4})) , computed as follows: \displaystyle\llbracket\mathbf{EF}~isFire \displaystyle able(t_{3})\land isFireable(t_{4})\rrbracket=\mu Y.\{(\{(0,0,0,1,1)\},\varnothing)\}\cup_{svs}pre_{svs}(Y) \displaystyle(1) \displaystyle=\{(\{(0,0,0,1,1)\},\varnothing)\} \displaystyle(2) \displaystyle=\{(\{(0,0,0,1,1)\},\varnothing),(\{(0,1,1,1,0)\},\varnothing),(\{(1,0,1,0,1)\},\varnothing)\} \displaystyle(3) \displaystyle=\{(\{(0,0,0,1,1)\},\varnothing),(\{(0,1,1,1,0)\},\varnothing),(\{(1,0,1,0,1)\},\varnothing), \displaystyle(\{(1,1,2,0,0)\},\varnothing),(\{(0,1,0,2,0)\},\varnothing),(\{(1,0,0,0,2)\},\varnothing)\} In the fixpoint computation of \mathbf{EF} , we have omitted the detailed steps and provided the final result of each step. The result does not change after step (3). Hence, a marking that is part of \llbracket\mathbf{EF}~isFireable(t_{3})\land isFireable(t_{4})\rrbracket is considered not safe from the mutual exclusion problem. For example, (1,1,1,0,0) is a valid marking, whereas (1,1,2,0,0) is not. This result also yields an infinite number of valid markings. Note that when the capacity of places is unbounded, the computation may not terminate if the solutions diverge. Conversely, if all places are bounded, the computation always concludes. 4.4 Optimisation through saturation Similarly to methods such as decision diagrams that encounter a peak [ 7 , 13 ] effect, the construction of symbolic vector sets is subject to the same challenge. While computing the solution iteratively through the fixed-point, intermediate solutions are generated. However, among these steps, some of the intermediate solutions will converge to the same solution. Thus, we end up working with more objects than necessary to obtain the final solution. To address this issue, we propose a solution called saturation , which effectively mitigates the peak effect during computation. ⬇ 1 func evalEF ( \phi : CTL ) -> SVS { 2 n = 1 // The current capacity 3 svsRes = \llbracket\phi\rrbracket_{svs} 4 weights = collectLabelWeights (). sorted () 5 while n \leq k { 6 svsCap = svsRes // Keep result from previous capacity 7 do { 8 svsTemp = svsRes 9 svsRes = svsRes \cup_{svs}~pre_{svs_{n}}(svsRes) 10 } while !( svsRes \subseteq_{svs} svsTemp ) 11 if svsRes \subseteq_{svs} svsCap { 12 weight = weights . first ( where : { w > n }) 13 if weight . isNil () { break } 14 n = weight 15 } else { n = n + 1 } // Increment current capacity 16 } 17 return svsRes 18 } Figure 8 : Saturated algorithm of the evaluation of \mathbf{EF}~\phi Figure 8 is the pseudo-code summarising this notion for the CTL temporal operator \mathbf{EF} . svsRes is the symbolic vector set storing the solution that will evolve, initialised with the previous evaluation of \phi (line 3). weights is an array that compiles all weight labels from a Petri net, sorted from the smallest to the largest (line 4). The functions collectLabelWeights and sorted are given. To streamline our approach, we consider the capacity k as a uniform bound for all places. The idea is to iterate on k (using n ) starting from 1 (line 2) and compute the intermediate results of the CTL formula for a lower k . Subsequently, the result of the previous step is leveraged to compute the next one, creating an iterative process (from line 5 to 16). From line 7 to 10 , we have the computation of fixed-point for \mathbf{EF} . The main difference from the common evaluation is the use of pre_{svs_{n}} . This function defined earlier in Definition 4.4 has been complemented by the index n . This index specifies the current capacity used when computing pre_{svs} . It ensures that symbolic vectors cannot contain markings with a value greater than n . Upon completing the computation of the fixed-point for a given capacity, we compare the new result svsRes with the previous one stored in svsCap (line 6). Furthermore, if the result of two consecutive iterations for two different capacities remains unchanged (line 11), we inspect the weights collected previously (line 4) to determine whether any of them is capable of generating a marking greater than the current capacity n but less than k (line 12). The function first serves as a filter that attempts to extract a weight from the array weights such that its value is greater than n . Here, w is the variable that iterates through each value of weights . If the function fails to find such a value, it returns nil . This means that no transition in the net is capable of altering the final result. Then, the break statement (line 13) is executed to exit the loop and return svsRes (line 17). If such a weight is found, we update the corresponding capacity (line 14), allowing the potential discovery of new symbolic vectors in the next iteration. On the other hand, if condition line 11 does not hold, n is incremented by one (line 15). Note that if the value of weight is greater than k , the condition of the loop while will also terminate. For example, consider an arc of a transition that requires 6 tokens with k=9 . If svsRes remains unchanged for n=2 and n=3 , and the only other transition available also demands 6 tokens for an arc, we can update n to 6 . In fact, if no new transition is available under such conditions, the creation of new markings is not possible. To make this pseudo-code work for other CTL temporal operators, it is enough to update line 9 for the corresponding CTL operation. In addition, line 10 and 11 should be modified for the operations \mathbf{EG} and \mathbf{AG} due to the greatest fixed-point, requiring the elements of both relations to be swapped. 4.5 Optimization: clustering Clustering consist in using smaller vectors and combine them, this approach can have optimization potential for reachability computations while keeping the idea of global model checking. If nets have no transitions covering more than one cluster, then the reachable states is the cartesian product of all vectors. This can be computed on each local symbolic structures. For transition covering more than one vector, the principle is to compute as usual the effect of these transitions over several clusters which is in this case more costly. This two step process is the reapplied until finding a fix point. The same principle is used with decision [ 14 ] . The new necessary definition for defining formally this princiople is the new concept of concatenation of vectors. Unformally it is the concatenation of the bound of each vector, we will not describe these concepts here for space reasons. 5 Benchmarks and results This section is dedicated to examining the results obtained with our tool, namely SVSKit , which is a Swift library available on GitHub . Our library implements the theory developed in this article. All the showcased examples are sourced directly from the model checking contest for the year 2022. However, our tool is presented from the perspective of global model checking. All tests were conducted on a MacBook Pro computer equipped with a 3.2 GHz CPU and 32 GB of RAM. 5.1 Circadian clock: A general model The Petri net of the circadian clock model, originally defined in [ 24 ] , consists of 14 places, 16 transitions, and 58 arcs. Several places in this net are associated with a variable value N , which can be adjusted according to specific objectives. In our system, N can be considered as the number that determines the capacity of each place. In addition, increasing this value raises the system’s complexity. Capacity Saturated Time (s) Peak SV number Final SV number 1 true 1.9 29 26 false 1.9 29 2 true 3.2 29 false 45 86 6 true 3.2 29 false 19000 954 Table 1 : Comparison of a reachability property computation ( \mathbf{EF~\phi} ) for the circadian clock model, with and without the use of saturation. In Table 1 , we compare the calculation of a reachability property both with and without saturation, for various capacities. Saturation optimisation is instrumental in making symbolic vector sets practical for Petri nets of reasonable size. It is worth noting that without saturation, the time complexity grows exponentially, reaching over 5 hours for a capacity of 6. In contrast, with saturation enabled, the time remains constant starting from capacity 2 and above. The use of saturation allows us to build symbolic vector sets step by step with the minimum of information required. This can be observed in the Peak SV number column, where the saturated solution remains consistently below 29 and does not exhibit significant growth. Moreover, the final solution consistently comprises 26 symbolic vectors for all capacities, indicating that increasing it should not significantly alter the computational complexity. We have implemented the query reduction optimisation discussed in [ 5 ] . In fact, because the CTL formulas for the competition are generated randomly, we are interested in simplifying them before evaluating them. However, only some of the reduction rules are available in the context of global model checking. Furthermore, only the reduction rules concerning global model checking have been reused, which does not require any initial marking i.e. in such a way that it is not necessary to give any initial marking. Capacity Marking number (\sim) Final SV number Time (s) 100 1.1\times 10^{28} 26 3.2 10000 1.0\times 10^{56} 1000000 1.0\times 10^{84} \infty \infty Table 2 : Progression of the prior \mathbf{EF} reachable property from Table 1 across varying capacities, assuming the saturation by default. In Table 2 , we observe the behaviour when we assume saturation by default and only vary the capacity. This result aligns with the previous finding, indicating that changing the capacity no longer significantly impacts the efficiency of the computation. The primary result affected by this change is the number of markings encoded by the symbolic vector set. Although the count of symbolic vectors remains consistent across all rows, the decoded version can still change. This is because capacity is not taken into account in the creation of symbolic vectors, and will only appear when decoding the set of symbolic vectors. In addition, the table offers an approximate count of markings, calculated without the need to decode the structure. Note that this number is related to the number of initial markings satisfying the CTL formula and not to the number of reachable markings from a given configuration. Thus, we can efficiently handle markings until, potentially, infinity if the result converges. The earlier convergence occurs, the more efficient the computation becomes, enabling the capture of the Petri net’s evolution at the earliest possible stage thanks to saturation. # Time (s) SV nb Marking nb \ast # Time (s) SV nb Marking nb \ast 00 11 1 2.0\times 10^{60} F 08 3.8 3 1.0\times 10^{60} F 01 1.7 0 0 F 09 0.15 17 1.0\times 10^{70} T 02 1.7 1 3.0\times 10^{60} F 10 4 20 1.0\times 10^{60} F 03 0.06 0 0 F 11 1350 1 1.0\times 10^{84} F 04 20.5 17 1.0\times 10^{70} T 12 0.28 6 1.1\times 10^{70} T 05 2.4 1 1.0\times 10^{70} T 13 1.4 9 2.0\times 10^{65} T 06 418 686 1.0\times 10^{84} T 14 11.4 29 1.0\times 10^{70} T 07 6.6 4 1.0\times 10^{70} F 15 23.8 40 1.0\times 10^{60} F Table 3 : Computation of CTL fireability formulas for the circadian clock model with N=100~000 . Each CTL formula is numbered in \# from 00 to 15 , following the order provided in competition resources. \ast column contains the local answer of each formula of the competition, where F and T stand for false and true , respectively. ”nb” is the abbreviation for ”number”. In the context of the model checking contest, the same model is provided with varying initial markings, each time increasing the number of tokens. The most challenging scenario for the circadian clock model is when N is set to 100~000 , which means that several places in the Petri net contain such a number of tokens. In the CTL fireability category, three tools participated in 2022: GreatSPN [ 3 ] , ITS-Tools [ 27 ] , and Tapaal [ 15 ] . None of these tools managed to produce responses to all queries within the 60-minute time limit, underscoring the challenging nature of the task. The best tool for this execution was Tapaal, which was able to answer 9 out of 16 queries 5 5 5 The results can be found here , by looking for the CircadianClock table. . In contrast, our results in Table 3 show that our symbolic technique successfully addressed all queries in approximately 30 minutes. Furthermore, we computed the complete set of valid solutions and checked whether the initial marking of the model belongs to the resulting symbolic vector set. By focussing on a specific configuration, new optimisations become available, such as the on-the-fly technique [ 4 ] , structural reduction [ 6 ] , or stubborn reduction [ 29 ] . It should be noted that while our tool was not tested under identical conditions, the setup was not significantly different 6 6 6 Each execution on the virtual machine for the MCC was limited to a maximum of 16 GB, 2.4 GHz, and 4 cores. . Nevertheless, our present implementation of canonical symbolic vector sets faces scalability challenges. Efficiency hinges on the implementation of canonical operations, exhibiting a worst-case complexity of \mathcal{O}(n!) . Our implementation strategy involves moving each element from one set to the other. Throughout this process, we must ensure that each moved element does not conflict with elements in the other set. Additionally, when conflicts arise, the lexicographical order determines the symbolic vector that will contain the shared portion. Obtaining this shared part entails merging it with the lowest symbolic vector and subtracting it from the greatest symbolic vector. This subtraction may result in the creation of new symbolic vectors, requiring the canonical union to be reapplied to each of them, causing a deeper level of recursion. In addition, most operations rely on canonical union.Hence, we restricted our testing to a relatively small-sized Petri net due to these limitations. Despite the inherent complexity, our method allows us to compute formulas that even the most proficient tools find challenging. This approach already demonstrates its viability in specific scenarios, and we are confident that further refinement can address the mentioned issue and enhance its capabilities. 6 Background & Related works The original framework, initially introduced as Predicate structures in [ 22 ] , remained stagnant for almost 30 years without further development. In its initial version, performance limitations rendered it nearly unusable or, at the very least, non-competitive. Building on this foundation, we have expanded and enhanced it by introducing new operations, a novel canonical form, and optimisations. In the realm of techniques addressing the state-space explosion problem in model checking, our method resembles symbolic model checking approaches. Decision diagrams [ 1 , 12 , 13 , 14 , 28 ] are the prevailing methods in symbolic model checking, employing various types of data encoding and optimisations [ 2 , 7 , 17 , 25 ] . These representations enhance the efficiency of data representation and leverage homomorphisms for symbolic processing. In contrast to our approach, based on encapsulation akin to intervals, decision diagrams exploit shared representations, allowing common components to be shared among different entities when encoding a set. Moreover, our representation can handle certain infinite representations, a capability not universally shared by decision diagrams. Among the big family of decision diagrams, Interval decision diagrams (IDDs) [ 25 ] appear to be the most closely related to our work. However, symbolic vector sets generalise intervals for vectors, while IDDs consist of vectors of intervals. 7 Conclusion In this paper, we introduce a novel structure termed symbolic vector set . Alongside this structure, we present homomorphic operations, canonical form, and saturation optimisation to enhance computational efficiency. Using this approach, we encode Petri net markings and employ the symbolic representation for CTL formula evaluation. Our initial results are promising, indicating potential avenues for further explorations and analysis. We believe that our current implementation can be improved, particularly by enhancing the canonical operations. Our work opens up several research directions. Exploring our approach within the realm of local model checking holds promise.Additionally, exploring models beyond Petri nets is another line of research, contingent upon our ability to construct the pre operation symbolically for the model. One of the most promising directions for our research is to integrate our method with other symbolic model checking methods, such as decision diagrams. We believe that both approaches are orthogonal and could mutually benefit from each other.