Partial Petri Net Languages and their Properties

Abstract

The languages derived from Petri Net provides a efficient technique for verification, validation and synthesis for the system. Partial words are extensively used in the fields such as bioinformatics, pattern matching and text searching. In this paper, we introduce a Partial Petri Net and then define its associated languages. Further, we discuss the closure properties that hold over these derived languages.

1 Introduction

The Petri Net, a formal model for the flow of information, was first presented in 1962 by Carl Adam Petri [1]. Petri Nets have found applications in the analysis of systems that exhibit concurrent, asynchronous, distributed, parallel, non deterministic and stochastic behaviors. Tokens, which are identical and represented as black dots, are used in Petri Nets to emulate the system’s dynamic and simultaneous processes. A language can be associated with the execution of a Petri Net. By formulating a labeling function for transitions over a given alphabet, a language over the alphabet is generated from all firing sequence set that origin from a particular starting marking and lead to a final marking set. The firing rule is solely dependent on the presence of these tokens and the number available in the input places for the transition to fire [1]. Henry Baker investigated Petri Net and its languages in 1972 [2]. This was followed by Michael Hack on Petri Net languages in 1976 [3] and in the same year, James L. Peterson introduced Petri Net as an automaton and investigated its languages [4]. In 1978, Starke studied the free terminal language of a Petri Net [5]. Jantzen investigated the hierarchy of Petri Net languages in 1979 [6]. During the year 1981, Valk et al. discussed Petri Nets and regular languages [7], while Araki et al. discussed that flow languages for some restricted class of flow expressions are equivalent to Petri Net languages [8]. Vidal Naquet, in 1982, investigated deterministic languages of Petri Nets [9]. Parigot et al. investigated the Buichi-like theorem, which characterizes Petri Net languages in terms of second-order logical formulas [10]. In 1987, the language theory of Petri Nets was studied by Jantzen [11] and Pelz investigated closure properties of deterministic languages of Petri Nets [12]. Various classes of Petri Net languages have been identified, based on the selection of transition labeling (free, $\lambda$-free and with $\lambda$-transitions) and the choice of the final markings set. In the literature [1, 11], three options for final markings are commonly chosen.

Tiplea investigated the selective Petri Net languages in 1992 [13]. In 1996, Gaubert and Giua explored Petri Net languages with infinite sets of final markings [14] and further extended their research in 1999 to investigate the infinite subsets within these sets [15]. In 2005, Valk et al. studied the rationality of Petri Net languages [16] and in 2006, minimal representations of Petri net languages were studied by Sreenivas R. S. [17]. Kunimochi Y. investigated the algebraic properties of Petri Net languages and codes in 2009 [18]. In 1974, Fischer and Paterson [19] introduced partial words, which are defined as strings that include “do not care” symbols. In 1999, Berstel and Boasson [20] inaugurated the investigation into “Combinatorics on partial words”. This was further studied by Blanchet-Sadri [21, 22]. Periodicity in partial words and primitive partial words was investigated by Blanchet-Sadri [23, 24]. Certain properties of partial words was studied in [25]. Blanchet-Sadri [26] initiated the study of partial languages by presenting the notion of pcodes, defined as sets of partial words that maintain the uniqueness of factorization. Sasikala et al. [27] investigated the study of regular partial languages and local partial languages. Dassow et al. [28] presented a relationship between regular languages and partial words. Blanchet-Sadri et al. [29] explored questions posed by Dassow et al. regarding the relationship between the sizes of these structures, while Dassow et al. [30] investigated the regular languages of partial words. Sasikala et al. [31] introduced the Partial Array Token Petri Net to generate partial array languages.

Moreover, Mary Ann et al. proposed a bio-model engineering framework using Petri Nets [32]. Recent advancements, such as the improved database concurrency control algorithm [33] and the wavelet neural network model for intrusion detection [34], have significantly contributed to diverse computing tools and applications [35]. The exploration of secure keyword search in cloud computing has also been notable [36]. Muhammad Rizwan Ali et al. proposed cloud computing modeling and analysis based on Petri Net [37]. A timed neural network for the shortest path problem was investigated [38]. Toeplitz matrices-based key exchange protocols for the Internet of Things have been proposed [39].

The signifcant contributions of this research are:

• To understand the behavior of a system, analyzing its execution is essential. This approach is more useful and efficient in comprehending the system’s behavior.

• We study partial languages generated from the Partial Petri Net.

• We investigate closure properties over partial languages to provide a precise technique for verification, validation and synthesis for the important class of uncertain distributed systems.

• In existing literature, partial array languages have been studied with the introduction of Partial Array Token Petri Net [31], focusing on partial array languages. No prior work has been found to directly address this study. Notably, our study is specifically focused on the partial languages derived from the Partial Petri Net.

• The Partial Petri Net model established here is useful to enhance the modeling and analysis of concurrent, distributed systems characterized by uncertainty or partial observability of process executions. This potential application of the Partial Petri Net opens up new possibilities for research and exploration in the field.

The paper is organized as follows. Section 2 presents the basic definitions used in this paper. The Partial Petri Net is defined and its execution, state space and labelings, including an algorithm, are discussed in Sect. 3. In Sect. 4, Partial Petri Net languages and closure properties of these languages are studied. Finally, Sect. 5 gives the conclusion along with future scope.

2 Preliminaries

In this section, we have given some basic definitions and notations of partial words, partial languages and Petri Net.

Let $\Sigma$ be a finite set of symbols or letters that is not empty. A sequence of letters from $\Sigma$ is referred to as a string or word over $\Sigma$. The empty word is represented by the symbol $\lambda$. All strings that are made up of letters from $\Sigma$, including $\lambda$, are represented by $\Sigma ^{*}$. On the other hand, $\Sigma ^{+}$ represents the set of all strings in $\Sigma$, but excludes $\lambda$. A language L is defined as any subset of $\Sigma ^{*}$. A finite partial word (or partial word) is a sequence of symbols that has a number of unspecified symbols, denoted by $\diamondsuit$, that are called “holes” or “do not care symbols”. Consider a partial word $u = u[1...n]$ over the alphabet $\Sigma$. u is a partial function that maps the set $\{1,2,...,n\}$ to $\Sigma$. If u(i) is defined for any i where $1\le i<n$, then i is part of the domain of u, represented as D(u). If not, i is included in the set of holes of u, represented as H(u). To represent the positions of the holes in u, we define the partial word $u_{\diamondsuit }$ (Eq. 1) to be the total function $u_{\diamondsuit }: \{1,2,...,n\} \rightarrow \Sigma _{\diamondsuit }$ that maps to the extended alphabet $\Sigma _{\diamondsuit }=\Sigma \cup \{\diamondsuit \}$ and $\diamondsuit \notin \Sigma$, such that:

$$\begin{aligned} u_{\diamondsuit }(i)= {\left\{ \begin{array}{ll} u(i) &{} \text {if}\quad i\in D(u)\\ \diamondsuit &{} \text {if}\quad i\in H(u). \end{array}\right. } \end{aligned}$$

(1)

The set of all finite partial words over $\Sigma _{\diamondsuit }$ is denoted by ${\Sigma _{\diamondsuit }}^{*}$. Within this, ${\Sigma _{\diamondsuit }}^{+}$ denotes the subset containing all non-empty partial words over $\Sigma _{\diamondsuit }$. A partial language $L_{\diamondsuit }$ is then defined as any subset $L_{\diamondsuit } \subseteq {\Sigma _{\diamondsuit }}^{*}$, that is, a set of partial words over the extended alphabet $\Sigma _{\diamondsuit }$.

A Petri Net structure, denoted as C, can be expressed as a quintuple: $C = (P, T, I, O, \mu _{0})$. Here, P represents a set of finite places, and T represents a finite transitions set. The intersection of the sets of transitions and places is empty, indicated by $P \cap T = \emptyset$. The input function, denoted as $I: T \rightarrow P^{\infty }$, maps transitions to bags of places, while the output function, denoted as $O: T \rightarrow P^{\infty }$, performs a similar mapping. The initial marking, represented by $\mu _{0}: P \rightarrow \{0, 1, 2, \dots \}$, defines the initial state of the places in the Petri Net. if $p_{i}\in I(t_j)$ then a place $p_{i}$ serves as an input place of an transition $t_{j}$. Conversely if $p_{i}\in O(t_j)$, $p_{i}$ acts as an output place. The inputs and outputs associated with a transition are bags of places. A bag is a concept that builds upon the notion of a set. Similar to a set, a bag constitutes a group of elements from a certain domain. However, in contrast to a set, the elements in a bag can recur multiple times. A function, denoted as $\#(\cdot , \cdot )$, is represented for components in a given domain and bags within that domain, this determines the frequency of each component in the bag. Specifically, $\#(x, \beta ) = k\ge 0$ indicates that element x appears k times exactly in the bag $\beta$. Since set theory is a subset of bag theory when the range of the $\#$ function is $\{0,1\}$, we utilize a significant amount of the symbols and fundamental concepts of sets when dealing with bags. A Labeled Petri Net, denoted as $A = (C, \Sigma , \sigma )$ where $C = (P, T, I, O, \mu _{0})$, $\Sigma$ is the input alphabet and a labeling function $\sigma : T \rightarrow \Sigma$. The labeling function extends to firing sequences, where if $\gamma$ represents a firing sequence, $\sigma (\gamma )$ is termed a label sequence. The languages generated by Petri Nets consist of the sets of label sequences corresponding to all firing sequences or just all terminal firing sequences.

3 Partial Petri Net

In this section, we define Partial Petri Net with an example and discuss its execution, state space and labelings, including an algorithm.

Definition 1

A Partial Petri Net, ${PN}_{\diamondsuit }$, is a quintuple defined by

$$\begin{aligned} {PN}_{\diamondsuit }=(P, T_{\diamondsuit }, \Sigma _{\diamondsuit }, S, F), \end{aligned}$$

where

• P is a finite set of places,

• $T_{\diamondsuit }= T_{r} \cup T_{p}$ and $T_r \cap T_p=\phi$, here

• $T_{r}$ is a finite set of regular transitions and $T_{p}$ is a finite set of partial transitions,

• $\Sigma _{\diamondsuit }$ is the input alphabet,

• $S\in P$ is the start place,

• $F\subseteq P$ is the finite set of final places.

Every transition, denoted as $\tau _{j}$ from the set $T_{\diamondsuit }$, is defined by an ordered triple, expressed as

$$\begin{aligned} \tau _{j}=(\alpha _{j}, \mathcal {I}_j, \mathcal {O}_j) \end{aligned}$$

where

• $\alpha _{j} \in \Sigma _{\diamondsuit }$ representing the label for $\tau _{j}$,

• $\mathcal {I}_j\subseteq P$ denotes the input places of the transition,

• $\mathcal {O}_j\subseteq P$ denotes the output places of the transition.

Example 1

Consider the ${PN}_{\diamondsuit }=(P, T_{\diamondsuit }, \Sigma _{\diamondsuit }, S, F),$ where $P=\{p_1, p_2, p_3\}$, $T_{\diamondsuit }=\{\tau _{r1}, \tau _{r2}, \tau _{r3}, \tau _{p}\}$, $\Sigma _{\diamondsuit }=\{a, b, c\}\cup \{\diamondsuit \}$, $S=\{p_{1}\}$ and $F=\{{p}_{3}\}$.

When dealing with Partial Petri Nets, it is necessary to mention the individual elements of the ordered triples that constitute transitions. To aid in the precise recognition of these elements within a transition, we present three mapping functions (Eq. 2): the label function denoted by ($\alpha$), the input function represented by $(\mathcal {I})$ and the output function represented by $(\mathcal {O})$. For a transition $\tau _j=(\alpha _j, \mathcal {I}_j, \mathcal {O}_j)$, where $\tau _j\in T_{\diamondsuit }$, the definitions of these functions are as follows:

$$\begin{aligned} \alpha (\tau _j)=\alpha _j, \mathcal {I}(\tau _j)=\mathcal {I}_j, \mathcal {O}(\tau _j)=\mathcal {O}_j \end{aligned}$$

(2)

To map transition sequences to label sequences, we expand the label function by

$$\begin{aligned} \alpha (y)= {\left\{ \begin{array}{ll} \epsilon &{} \text {if}\quad y=\epsilon \\ \alpha (\tau _{j})\alpha (x) &{} \text {if}\quad y=\tau _{j}x,\tau _{j}\in T_{\diamondsuit }, x\in {T_{\diamondsuit }}^{*} \end{array}\right. } \end{aligned}$$

(3)

3.1 Execution rules

The Definition (1) focus on describing the structural characteristics of a $PN_{\diamondsuit }$. As an abstract machine, the $PN_{\diamondsuit }$ exhibits computational properties that govern its behaviour during firing. The firing process of a $PN_{\diamondsuit }$ is influenced by the presence and positioning of tokens, which are represented as black dots and traverse according to the firing rules for $PN_{\diamondsuit }$ Fig. 1).

Fig. 1

An example of the $PN_{\diamondsuit }$

These rules can be summarized as follows:

• Initialization: Initiate the $PN_{\diamondsuit }$ by placing a single token in the start state (Fig. 2).

• Final State Check: If the net reaches a terminal state, the execution may halt; otherwise, compute the firing transition set, V (Fig. 3).

• Transition Firing: If V is nonempty, initiate the firing of one transition from V and subsequently revert to step second step (Fig. 4). If V is empty, the firing comes to a halt (Fig. 5).

When there are enough tokens in each of a transition’s input places, the transition becomes enabled. Tokens are taken out of all of a transition’s input places and deposited into all of its output places when the transition is fired. These definitions are clarified further by

Definition 2

A transition, $\tau _j\in T_{\diamondsuit }$, is enabled if for every $p_n\in P$, the number of tokens in $p_n$ is atleast $\#(p_n,\mathcal {I}(\tau _j))$.

Definition 3

An firable transition, $\tau _j$, initiates by first eliminating the token $\#(p_n,\mathcal {I}(\tau _j))$ from every place $p_n\in P$ and proceeds by inserting the token $\#(p_n,\mathcal {O}(\tau _j))$ to each place $p_n\in P$.

3.2 The state space

Token distribution and number inside the net define the structure of a $PN_{\diamondsuit }$. Alternatively, this can be written as the cardinality of tokens, permitting zero, at every place within the $PN_{\diamondsuit }$, which is known as a marking. An n-vector of non-negative numbers represents the place of a $PN_{\diamondsuit }$ and the token cardinality in each place is always a non-negative integer. A change in the place of $PN_{\diamondsuit }$ is indicated by the firing of a transition. If there is a sequence of firings that can change the initial statewhich corresponds to one token at the beginning and no tokens everywhere else into the target state, then that state is said to be reachable. We define M as the reachable state space, which is also commonly known as the marking of a $PN_{\diamondsuit }$.

Fig. 2

Initially, place $p_1$ contains one token and the set of tokens is denoted as $V={\tau _{r1}, \tau _{p}}$

Fig. 3

After firing $\tau _{r1}$, then $V=\{\tau _{r1}, \tau _{p}\}$

Fig. 4

After firing $\tau _{p}$, then $V=\{\tau _{r2}, \tau _{r3}\}$

Fig. 5

After firing $\tau _{r3}$, then $V=\{\phi \}$

If we represent the set of non-negative integers as N, then $M\subseteq N^n$. Every element in M is structured as an $n-$vector, with its $\mathfrak {K}^{th}$ element indicating the tokens cardinality at place $p_n$ where $1\le \mathfrak {K} \le n)$. The symbol S is used to denote the initial state and the vector $(1,0,0, \dots ),$ whereas F represents the final state set and the vector $(0,0, \dots , 1)$.

The subsequent-state function, represented as $\delta ,$ is a function mapping from $N^n\rightarrow T_{\diamondsuit }$ into $N^n$. For a m and a $\tau _j \in T_{\diamondsuit }$, the subsequent-state function, denoted as $\delta (m,\tau _j),$ is defined iff for all n,$(1\le n \le k),$

$$\begin{aligned} m_n\ge \#(p_n,I(\tau _j)) \end{aligned}$$

(4)

Therefore, $\tau _j\in T_{\diamondsuit }$ is considered firable in a state m iff $\delta (m,\tau _j)$ is defined. If $\delta (m,\tau _j)$ is defined, the resulting state vector from firing $\tau _j$ is determined. The $n^{th}$ element of the subsequent state is

$$\begin{aligned} \delta (m,\tau _j)_n =m_n - \#(p_n,\mathcal {I}(\tau _j)) + \#(p_n,\mathcal {O}(\tau _j)) \end{aligned}$$

(5)

If $\delta (m, \tau _j)$ is defined and Eq. (4), with $\#(p_n, \mathcal {I}(\tau _j)) \ge 0$, it follows that $\delta (m, \tau _j) \ge 0$, ensuring $\delta (m, \tau _j) \in N^n$.

The definition of $\delta (m, \tau _j)$ can be reformulated as a system of vector replacement [40]. For every $\tau _j\in T_{\diamondsuit }$, we define $u_j$ and $v_j$, where $(u_j)_n=-(p_n, \mathcal {I}(\tau _j))$ and $(v_j)_n=-\#(p_n,\mathcal {I}(\tau _j)) + \#(p_n,\mathcal {O}(\tau _j))$. $\delta (m, \tau _j)$ is defined if $m+u_j\ge 0$, and if $\delta (m, \tau _j)$ is defined, then $\delta (m, \tau _j)=m+v_j$. The reachable state space of the $PN_{\diamondsuit }$ is analogous to the reachability set of a vector replacement system.

We expand the subsequent-state function from a single transition to the transition sequence, similar to the label function (Eq. 3). If y represents a transition sequence, denoted as $y\in {T_{\diamondsuit }}^{*}$, then

$$\begin{aligned} \delta (m, y)= {\left\{ \begin{array}{ll} m &{} \text {if}\quad y=\varepsilon \\ \delta (\delta (m, \tau _j), x) &{} \text {if}\quad y=\tau _{j}x,\tau _{j}\in T_{\diamondsuit }, x\in {T_{\diamondsuit }}^{*} \end{array}\right. } \end{aligned}$$

(6)

Certainly, the subsequent-state functions mentioned in the Eq. (5) are defined for their corresponding inputs if and only if Eq. (6) is defined.

We can now define the smallest subset of $N^n$ defined by the reachable state space, M.

• $S\in M$

• if $m\in M$, and Eq. (6) is defined for $y\in {T_{\diamondsuit }}^{*}$, then Eq. (6) $\in M$

We constrain the subsequent-state function to the reachable set M, since we are only focus in reachable states. As a result, $\delta : M \times T_{\diamondsuit } \rightarrow M$, and with the possible exception of the initial state, this mapping is surjective.

3.3 Labelings

A distinct labeling of the $PN_{\diamondsuit }$ means that each transition possesses a unique label [that is, if $\alpha (\tau _i)=\alpha (\tau _j)$, then $\tau _i=\tau _j$]. On the other hand, the $\lambda -$free Partial Petri Net Language class permits transitions to have the same labels, but it does not allow transitions to be empty, (i.e)., for every $\tau _j\in T_{\diamondsuit }:\alpha (\tau _j)\ne \lambda$. Additionally, a more inclusive labelling function has been considered, permitting null-labelled transitions, denoted as $\alpha (\tau _j)=\lambda$. These transitions are not present in the language and their existence in the $PN_{\diamondsuit }$ execution is not recorded. Furthermore, the deterministic labeling has an additional property. For each marking and each label, only one transition with that label is eligible for firing. (i.e)., for every $m_i$ and for every $\tau _j, {\tau _j}^{'} \in T_{\diamondsuit }: (\alpha (\tau _j)=\alpha ({\tau _j}^{'})$ and $m_{i}(\tau _j)$ and $m_{i}(\tau _j^{'}))$ $\implies \tau _{j}=\tau _j^{'}$. These various types of labelings, including distinct (d), $\lambda -$free, $\lambda -$transitions $(\lambda )$ and deterministic (def), yield four distinct languages types.

Algorithm 1

Partial Petri Net Execution and Language Study

4 Partial Petri Net Languages and its closure properties

This section defines Partial Petri Net Language classes and studies their closure properties.

Definition 4

A partial language ${L}_{\diamondsuit }\in {\Sigma _{\diamondsuit }}^{*}$ is said to be an ${{\mathcal{L}}_{\diamondsuit }}$-type Partial Petri Net Language (PPNL) if there exists a $PN_{\diamondsuit }$ such that $L_{\diamondsuit }=\{\alpha (y)\in {\Sigma _{\diamondsuit }}^{*}|y\in {T_{\diamondsuit }}^{*}$ & $\delta (m,y) \in F \}$.

Definition 5

A partial language ${L}_{\diamondsuit }\in {\Sigma _{\diamondsuit }}^{*}$ is said to be an ${{\mathcal{G}}_{\diamondsuit }}$-type PPNL if there exists a $PN_{\diamondsuit }$ such that $L_{\diamondsuit }=\{\alpha (y)\in {\Sigma _{\diamondsuit }}^{*}|y\in {T_{\diamondsuit }}^{*}$, $\exists$ $m_f\in F$: $\delta (m,y)\ge m_f\}$.

Definition 6

A partial language ${L}_{\diamondsuit }\in {\Sigma _{\diamondsuit }^{*}}$ is said to be an ${{\mathcal{P}}_{\diamondsuit }}$-type PPNL if there exists a $PN_{\diamondsuit }$ such that $L_{\diamondsuit }=\{\alpha (y)\in {\Sigma _{\diamondsuit }}^{*}|y\in {T_{\diamondsuit }}^{*}$ & $\exists$ $\delta (m,y)$ but $\forall$ $\tau _{j}\in T_{\diamondsuit },$ $\not \exists$ $\delta (\delta (m,y),\tau _{j})\}$.

Definition 7

A partial language ${L}_{\diamondsuit }\in {\Sigma _{\diamondsuit }^{*}}$ is said to be an ${{\mathcal{R}}_{\diamondsuit }}$-type PPNL if there exists a $PN_{\diamondsuit }$ such that $L_{\diamondsuit }=\{\alpha (y)\in {\Sigma _{\diamondsuit }}^{*}|y\in {T_{\diamondsuit }}^{*}$ & $\exists$ $\delta (m,y)\}$.

Example 2

Consider the ${PN}_{\diamondsuit }=(P, T_{\diamondsuit }, \Sigma _{\diamondsuit }, S, F),$ where $P=\{p_1, p_2, p_3, p_4\}$, $T_{\diamondsuit }=\{\tau _{r1}, \tau _{r2}, \tau _{r3}, \tau _{p}\}$, $\Sigma _{\diamondsuit }=\{a, b, c\}\cup \{\diamondsuit \}$, $S=\{p_{1}\}$ and $F=\{p_{3}\}$.

Fig. 6

An example $PN_{\diamondsuit }$ to illustrate the different partial languages

Table 1 Four different PPNLs

The languages generated by the $PN_{\diamondsuit }$ in Fig. (6) are shown in Table (1). In addition to the four types of partial languages (definitions 4, 5, 6 and 7) defined by differences in the final state set, further classifications arise from variations through labelings (Table 2).

Table 2 Different Classes of PPNLs

Although the definitions vary, the classes of PPNLs exhibit a close relationship. Specifically, the distinct labelings set is contained within the set of deterministic labelings, which in turn, is contained within the $\lambda -$free labelings set and this set is also contained within the $\lambda -$labelings set (Eqs. 7, 8, 9 and 10).

$$\begin{aligned}{} & {} {\mathcal {L}}_{\diamondsuit }^{d} \subseteq {\mathcal {L}}_{\diamondsuit }^{def} \subseteq {\mathcal {L}}_{\diamondsuit } \subseteq {\mathcal {L}}_{\diamondsuit }^{\lambda } \end{aligned}$$

(7)

$$\begin{aligned}{} & {} {\mathcal {G}_{\diamondsuit }}^{d} \subseteq {\mathcal {G}_{\diamondsuit }}^{def} \subseteq \mathcal {G}_{\diamondsuit } \subseteq {\mathcal {G}_{\diamondsuit }}^{\lambda } \end{aligned}$$

(8)

$$\begin{aligned}{} & {} {\mathcal {P}_{\diamondsuit }}^{d} \subseteq {\mathcal {P}_{\diamondsuit }}^{def} \subseteq \mathcal {P}_{\diamondsuit } \subseteq {\mathcal {P}_{\diamondsuit }}^{\lambda } \end{aligned}$$

(9)

$$\begin{aligned}{} & {} {\mathcal {R}_{\diamondsuit }}^{d} \subseteq {\mathcal {R}_{\diamondsuit }}^{def} \subseteq \mathcal {R}_{\diamondsuit } \subseteq {\mathcal {R}_{\diamondsuit }}^{\lambda } \end{aligned}$$

(10)

Our investigation is confined to a specific set of standard form Partial Petri Nets, even though our interest extends to the entire class of $\mathcal {L}_{\diamondsuit }-$type PPNLs. This limitation narrows the class of PPNLs without making the proofs and constructs more difficult. Every $PN_{\diamondsuit }$ language can be generated by multiple Partial Petri Nets, however we only work with nets which have specific characteristics. We show that a standard form of $PN_{\diamondsuit }$ exists, which generates a language of ${\mathcal {L}}_{\diamondsuit }-$type for every PPNL, proving that this is not reducing the language set. First, we define the $PN_{\diamondsuit }$ in standard form.

Definition 8

A Partial Petri Net, ${PN}_{\diamondsuit }=(P, T_{\diamondsuit }, \Sigma _{\diamondsuit }, S, F)$ is in standard form if

• 1. $\mathcal {I}(\tau _j)\ne \phi$ and $\mathcal {O}(\tau _j)\ne \phi$ $\forall$ $\tau _j \in T_{\diamondsuit }$.

• 2. $S\notin \mathcal {O}(\tau _j)$ $\forall$ $\tau _j\in T_{\diamondsuit }$

• 3. $\exists$ $p_f\in P$ such that

  • $F={p_f}$ (if $\lambda \notin L_{\diamondsuit }({PN}_{\diamondsuit }))$ or $F=\{p_f, S\}$ (if $\lambda \in L_{\diamondsuit }({PN}_{\diamondsuit }))$,

  • $p_f\notin \mathcal {I}(\tau _j)$ $\forall$ $\tau _j\in T_{\diamondsuit }$

  • For any $\tau _j\in T_{\diamondsuit }$ and $m\in M$ with a token in $p_f$ (i.e., $m_f > 0)$), $\delta (m, \tau _j)$ is undefined.

The standard form for Partial Petri Nets requires transitions to possess both non-empty input bags and output bags. Additionally, this standard formulation necessitates the existence of two special places: a separate final place that connects to no transition inputs, as well as a single start place that does not defined as the output for any transitions.

When executed, the $PN_{\diamondsuit }$ in standard form initiates with a solitary token placed in the starting place. This token gets removed upon the firing of the first transition, resulting in an empty start place thereafter. A token reaching the designated final place can halt the $PN_{\diamondsuit }$, as no transitions accept input from the final place. As a result, the token remains in the final place. To demonstrate standard-form Partial Petri Nets possess equivalent capability as the generalized form, we provide the subsequent theorem.

Theorem 1

For any $PN_{\diamondsuit }$, there exists an equivalent $PN_{\diamondsuit }$ in standard form.

Proof

Consider a ${PN}_{\diamondsuit }=(P, T_{\diamondsuit }, \Sigma _{\diamondsuit }, S, F)$. We illustrate the construction of an equivalent ${{PN}_{\diamondsuit }}^{'}=({P}^{'}, {T_{\diamondsuit }}^{'}, \Sigma _{\diamondsuit }, {S}^{'}, F^{'})$ in standard form (Fig. 7). First, we introduce three additional places that are distinct from P: $p_{r}$, $S^{'}$, and $p_{f}$. The starting place is $S^{'}$, the terminal place is $p_f$ and the run place is $p_r$. Tokens in $p_r$ are required for the firing of any transition in $T_{\diamondsuit }$. One token will be present in $S^{'}$ for the initial marking of ${{PN}_{\diamondsuit }}^{'}$ and one token will be present in $p_f$ [for $\lambda \in L_{\diamondsuit }({PN}_{\diamondsuit })$] or $S^{'}$ [if $\lambda \notin L_{\diamondsuit }({PN}_{\diamondsuit })$].

At this point, we have to make sure that all of the transition sequences in ${PN}_{\diamondsuit }$ that move from the starting marking to the terminal marking are also in ${{PN}_{\diamondsuit }}^{'}$ respectively. In order to do this, we examine three different kinds of strings in $L_{\diamondsuit }({PN}_{\diamondsuit })$. First, $F^{'}$ is defined in a way that appropriately recognizes the empty string $\lambda$. By examining if the starting marking is the terminal marking $m\in F$, we can determine whether $\lambda \in L_{\diamondsuit }({PN}_{\diamondsuit })$.

Fig. 7

The built structure of a $PN_{\diamondsuit }$ in its standard form

Second, we consider a particular transition from $S^{'}$ to $p_f$ in ${{PN}_{\diamondsuit }}^{'}$ for all strings of length 1 in $L_{\diamondsuit }({PN}_{\diamondsuit })$, as follows: Define $\tau _{\sigma } \in {T_{\diamondsuit }}^{'}$ for $\sigma \in \Sigma$ with $\sigma \in L_{\diamondsuit }({PN}_{\diamondsuit })$, where $\mathcal {I}(\tau _\sigma )=\{S^{'}\}$ and $\mathcal {O}(t_\sigma )=\{p_f\}$. Label $\sigma$ is associated with $\tau _\sigma$. By examining each transition $\tau _j\in T_{\diamondsuit }$, with $\alpha (\tau _j)=\sigma$, we can determine that $\sigma \in L_{\diamondsuit }({PN}_{\diamondsuit })$. Also, we can determine that $\delta (m, \tau _j)\in F$. Lastly, take into consideration all strings longer than 1. These strings forms a sequence in $T_{\diamondsuit }$, denoted by $\tau _{j_{1}}, \tau _{j_{2}}, \dots , \tau _{j_{n}}$. We then define a sequence incorporating new transitions a and b: $a{\tau _{j1}}^{'},\dots , {\tau _{jn}}^{'}b$. To generate the initial marking m of ${PN}_{\diamondsuit }$ and a token in $p_r$, the transition a would require a token from $S^{'}$. With the exception of $p_r$, which functions as both an input and an output, each ${\tau _j}^{'} \in {T_{\diamondsuit }}^{'}$ is identical to ${\tau _j}\in T_{\diamondsuit }$. This allows us to remove the token in $p_r$, hence disabling all transitions in ${T_{\diamondsuit }}^{'}$. At last, the b transition would output a token to $p_f$ and eliminate the token from $p_r$ along with a terminal marking of ${PN}_{\diamondsuit }$. A sequence $a{\tau _{j1}}^{'},\dots , {\tau _{jn}}^{'}b$ would be the only way for the token in the initial to the terminal places in ${{PN}_{\diamondsuit }}^{'}$ under this construction. This sequence aligns with $\tau _{j_{1}}, \tau _{j_{2}}, \dots , \tau _{j_{n}}$ leading from m to a terminal marking in ${PN}_{\diamondsuit }$.

Incorporating the additional symbols for transitions a and b would make the sequence overly long, since those symbols would only apply to ${{PN}_{\diamondsuit }}^{'}$ and not the ${PN}_{\diamondsuit }$. A null labeling for a and b would be one way to solve this, but null labelings are not allowed in ${\mathcal {L}}_{\diamondsuit }-$type languages. To resolve this, we need to merge transitions b and ${\tau _{j1}}^{'}$ into a single transition denoted ${\tau _{j1}}^{'''}$, as well as merge transitions a and ${\tau _{j1}}^{'}$ into ${\tau _{j1}}^{''}$. Therefore, we define the combined transitions in ${T_{\diamondsuit }}^{'}$, corresponding to any $\tau _j \in T_{\diamondsuit }$:

• Define ${\tau _{j}}^{'}\in {T_{\diamondsuit }}^{'}$, where $\mathcal {O}({\tau _j}^{'})=\mathcal {O}(\tau _j)\cup \{p_r\}$ and $\mathcal {I}({\tau _j}^{'})=\mathcal {I}(\tau _j)\cup \{p_r\}$.

• Define ${\tau _{j}}^{''}$ with $\mathcal {I}({\tau _j}^{''})=\{S^{'}\}$ and $\mathcal {O}({\tau _j}^{''})=m-\mathcal {I}(\tau _j)+\mathcal {O}(\tau _j)\cup \{p_r\}$ if $\mathcal {I}(\tau _j) \subseteq m$.

• For every $m^{'}$ in F representing a terminal marking that could result from $\tau _j$ firing as the terminal transition, we define ${\tau _{j}}^{'''}$ with $\mathcal {O}({\tau _j}^{'''})=\{p_f\}$ and $\mathcal {I}({\tau _j}^{'''})=m^{'}-\mathcal {O}(\tau _j)+\mathcal {I}(\tau _j)\cup \{p_r\}$.

The labeling $\alpha ^{'}$ (Eq. 11) is now defined by

$$\begin{aligned} \alpha ^{'}({\tau _j}^{'})=\alpha ^{''}({\tau _j}^{''})=\alpha ^{'''}({\tau _j}^{'''})=\alpha (\tau _j) \end{aligned}$$

(11)

Any string $\sigma$ that is in $L_{\diamondsuit }({PN}_{\diamondsuit })$ is generated, by $\tau _{j_{1}}, \tau _{j_{2}}, \dots , \tau _{j_{n}}$ such that $\sigma =\alpha (\tau _{j_{1}}, \tau _{j_{2}}, \dots , \tau _{j_{n}})$. By formulation

$$\begin{aligned} \sigma =\alpha ({\tau _{j1}}^{''}, {\tau _{j2}}^{'}, \dots , {\tau _{jn-1}}^{'}, {\tau _{jn}}^{'''}) \end{aligned}$$

(12)

and so Eq. (12) $\in L_{\diamondsuit }({PN}_{\diamondsuit })$. Therefore, given that $L_{\diamondsuit }({PN}_{\diamondsuit })=L_{\diamondsuit }({{PN}_{\diamondsuit }}^{'})$, ${PN}_{\diamondsuit }$ and ${{PN}_{\diamondsuit }}^{'}$ are equivalent. $\square$

Figure (8) shows a simple $PN_{\diamondsuit }$ which is not in standard form. Applying the proof’s construction to this $PN_{\diamondsuit }$ results in the standard form, shown in Fig. (9).

Fig. 8

A $PN_{\diamondsuit }$ which is not in standard form

Fig. 9

A standard form of $PN_{\diamondsuit }$

We will delve into the closure properties of PPNL. Given two such languages, $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$, we know that the $PN_{\diamondsuit }$ in standard form generates each of these languages. We therefore consider two Partial Petri Nets in standard form. ${PN}_{\diamondsuit 1}=(P_{1}, T_{\diamondsuit 1}, \Sigma _{\diamondsuit }, S_{1}, F_{1})$ and ${PN}_{\diamondsuit 2}=(P_{2}, T_{\diamondsuit 2}, \Sigma _{\diamondsuit }, S_{2}, F_{2})$ with $L_{\diamondsuit 1}=L_{\diamondsuit }(PN_{\diamondsuit 1})$ and $L_{\diamondsuit 2}=L_{\diamondsuit }(PN_{\diamondsuit 2})$. Given that both are in standard form, the start places of $PN_{\diamondsuit 1}$ and $PN_{\diamondsuit 2}$ are ${S_{1}\in P_{1}}$ and ${S_{2}\in P_{2}}$, respectively. Further, $F_2=\{S_{2}, p_{f2}\}$ or $\{p_{f2}\}$ and $F_1=\{S_{1}, p_{f1}\}$ or $\{p_{f1}\}$.

Using the given Partial Petri Nets, we demonstrate the construction of another ${{PN}_{\diamondsuit }}^{'}=(P^{'}, {T_{\diamondsuit }}^{'}, \Sigma _{\diamondsuit }, S^{'}, F^{'})$ with a language $L_{\diamondsuit }({{PN}_{\diamondsuit }}^{'})$, representing the combination of $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$.

Theorem 2

Let $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$ be two PPNLs, then $L_{\diamondsuit 1}L_{\diamondsuit 2}$ is also a PPNL.

Proof

Consider constructing a new ${{PN}_{\diamondsuit }}^{'}$ where the final place of $PN_{\diamondsuit 1}$, denoted $p_{f1}$, is made equivalent to the start place of $PN_{\diamondsuit 2}$, denoted $S_2$. This has the effect that the transition depositing a token in $p_{f1}$ also signals the start of execution in $PN_{\diamondsuit 2}$. Due to this construction, any string formed by concatenating elements from $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$ will have a valid path in ${{PN}_{\diamondsuit }}^{'}$ from the initial place $S_1$ through the overlap place $p_{f1}=S_2$ to the final place $p_{f2}$. Hence, the concatenated string must be an element of the language $L_{\diamondsuit }({{PN}_{\diamondsuit }}^{'})$. A similar argument can show that any string generated from ${{PN}_{\diamondsuit }}^{'}$ must consist of a string from $L_{\diamondsuit 1}$ followed by one from $L_{\diamondsuit 2}$. To properly account for the possibility of empty strings, the formal definition of ${{PN}_{\diamondsuit }}^{'}$ requires defining it as the union of $PN_{\diamondsuit 1}$ and $PN_{\diamondsuit 2}$ along with some additional transitions. Specifically, for any transition $\tau _j$ in $T_{\diamondsuit 2}$ with input place $S_2$, introduce a corresponding transition ${{\tau _j}^{'}}$ in ${{PN}_{\diamondsuit }}^{'}$ with input place $p_{f1}$ and output places $O_2(\tau _j)$. Also, if $S_1$ is a final place in $PN_{\diamondsuit 1}$ add another transition ${{\tau _j}^{''}}$ with input place $S_1$ and output places from $O_2(\tau _j)$. The labeling functions ${\alpha }^{'}$ for the new transitions ${{\tau }^{'}j}$ and ${{\tau }^{''}j}$ mirror those from $PN_{\diamondsuit 2}$. The final place set $F^{'}$ for ${{PN}_{\diamondsuit }}^{'}$ is defined as the union of $F_1$ and $F_2$, unless ${S_{2}^{'}}$ is not a final place, in which case $F^{'}= F_2$. The construction is illustrated in Fig.  (10). $\square$

Fig. 10

An example of concatenating two Partial Petri Net Languages

Theorem 3

Let $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$ be two PPNLs, then $L_{\diamondsuit 1}\cup L_{\diamondsuit 2}$ is also a PPNL.

Proof

The approach for proving this theorem follows a similar construction that was shown previously. Specifically, we introduce a new ${{PN}_{\diamondsuit }}^{'}$ defined such that its language satisfies $L_{\diamondsuit }({{PN}_{\diamondsuit }}^{'}) = L_{\diamondsuit 1} \cup L_{\diamondsuit 2}$. This is accomplished via ${{PN}_{\diamondsuit }}^{'}$ containing a single new start place formed by combining the start places of $PN_{\diamondsuit 1}$ and $PN_{\diamondsuit 2}$. An initial transition in ${{PN}_{\diamondsuit }}^{'}$ removes the token from this unified start place. Subsequently, depending on whether this initial transition lies in $T_{\diamondsuit 1}$ or $T_{\diamondsuit 2}$, the underlying net $PN_{\diamondsuit 1}$ or $PN_{\diamondsuit 2}$ proceeds to execute as it normally would, just as defined previously. we introduce a new start place ${S}^{'}$ along with additional transitions ${{\tau _{j1}}^{'}}$ and ${{\tau _{j2}}^{'}}$ defined as follows. For each transition $\tau _{j1}$ in $T_{\diamondsuit 1}$ that has the start place $S_1$ as an input place, create a corresponding transition ${{\tau _{j1}}^{'}}$ with input place ${S}^{'}$ and output places identical to those of $\tau _{j1}$ in $PN_{\diamondsuit 1}$, (i.e.) $\mathcal {O}_{1}(\tau _{j1})$. Similarly, for each transition $\tau _{j2}$ in $T_{\diamondsuit 2}$ with start place $S_2$ as input, add transition ${{\tau _{j2}}^{'}}$ with input ${S}^{'}$ and outputs $\mathcal {O}_{2}(\tau _{j2})$. The labeling ${\alpha }^{'}$ map to ${\alpha }_1$ and ${\alpha }_2$ accordingly. The starting marking assigns a single token in ${S}^{'}$ and the terminal marking set $F^{'}$ is defined as the union of $F_1$ and $F_2$. Further, if $S_1 \in F_{1}$ or $S_2 \in F_{2}$, then ${S}^{'} \in F^{'}$. The construction is demonstrated in Fig. (11). $\square$

Fig. 11

An example of union of two Partial Petri Net Languages

Theorem 4

The intersection of two PPNLs, $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$, is also a PPNL.

Proof

Constructing a ${PN_\diamondsuit }^{'}$ that generates the intersection of two PPNLs poses certain difficulties. As sequences are being generated, a transition that fires in one $PN_\diamondsuit$, necessitates an equivalent labeled transition to be enabled in the other and vice versa. When multiple transitions carrying the same label exist across the pairs of nets, all possible pairings between these matching transitions require consideration. For each such pair, we introduce a new transition which activates iff both transitions in the pair can fire in their respective original Partial Petri Nets. The input and output places for this new transition are defined as the sums of the input and output places of the associated pair of old transitions. Formally, if $\tau _j \in T_{\diamondsuit 1}$ and $\tau _k \in T_{\diamondsuit 2}$ have $\alpha (\tau _j) = \alpha (\tau _k)$, the corresponding $\tau _{j,k} \in {T_{\diamondsuit }}^{'}$ such that $\mathcal {I}^{'}(\tau _{j,k}) = \mathcal {I}_{1}(\tau _j) + \mathcal {I}_{2}(\tau _k)$ and $\mathcal {O}^{'}(\tau _{j,k}) = \mathcal {O}_{1}(\tau _j) + \mathcal {O}_{2}(\tau _k)$. Any such $\tau _{j,k}$ with combined input places forming the set ${S_1, S_2}$ are replaced with a transition ${\tau _{j,k}}^{'}$ with the unified start place $S^{'}$ as its sole input. Through this merging process, the two Partial Petri Nets are effectively joined into one unified ${PN_{\diamondsuit }}^{'}$ capable of generating their language intersection. Figure (12) illustrates this construction. $\square$

Fig. 12

An example of intersection of two Partial Petri Net Languages

Theorem 5

The concurrent of two PPNLs, $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$, is also a PPNL.

Proof

Constructing ${PN_{\diamondsuit }}^{'}$ to generates the concurrent property of languages $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$ can be formulated as follows, given Partial Petri Nets that generate $L_{\diamondsuit 1}$ and $L_{\diamondsuit 2}$. First, initialize the marking by inserting tokens in the start places of $PN_{\diamondsuit 1}$ and $PN_{\diamondsuit 2}$. Then, define the set of terminal markings of the combined net to be any marking such that the restriction of that marking to places $P_1$ belongs to final marking set $F_1$ of $PN_{\diamondsuit 1}$ concurrently with its restriction to places $P_2$ belonging to final marking set $F_2$ of $PN_{\diamondsuit 2}$. This construction is illustrated in Fig. (13) $\square$

Fig. 13

An example of concurrent of two Partial Petri Net Languages

Theorem 6

Let $L_{\diamondsuit }$ be a PPNL, then its reverse, ${{L}_{\diamondsuit }}^{R}$ is also a PPNL.

Proof

The procedure for obtaining the reverse language is simple. Consider the $PN_{\diamondsuit }$ and construct the reverse ${{PN}_{\diamondsuit }}^{'}$ by swapping the initial and final markings and similarly transposing the places for each transition. This reversal of arcs and markings causes ${{PN}_{\diamondsuit }}^{'}$ to accept exactly the reverse strings of those accepted by the $PN_{\diamondsuit }$. Thus we have $L_{\diamondsuit }({{PN}_{\diamondsuit }}^{'}) = L_{\diamondsuit }({{PN}_{\diamondsuit }})^{R}$, showing that operating $PN_{\diamondsuit }$ in reverse yields its reverse language. Consequently, this construction inverts the order of all strings generated by $PN_{\diamondsuit }$. $\square$

Remark 1

Closure under complementation may not hold for PPNLs.

5 Conclusion and future scope

In this paper, the Partial Petri Net is defined. By modifying final state markings reached through execution sequences, we generated associated PPNLs. Further, by varying the labeling of transitions, we categorized these language classes. We demonstrated closure properties like union, intersection, concatenation, concurrency and reversal hold for these languages. While these initial results developing the formal theory of Partial Petri Nets and their languages are significant, further exploration remains.

Future work includes a more extensive categorization and analysis of additional classes of PPNL beyond the ${\mathcal {L}}_{ \diamondsuit }-$type studied thus far. Relationships between properties of these classes of PPNL and those of regular and local partial languages also warrant research. The incorporation of place-based labeling represents an open possibility that may yield valuable new insights into the process of behavioral languages and results. There remains a rich opportunity to enhance the understanding of concurrent systems using Partial Petri Nets. Moreover, future work could integrate Partial Petri Nets with bio-inspired techniques like neural networks and evolutionary algorithms for learning and optimization. Additional opportunities include improving concurrency control in databases extending intrusion detection systems formally verifying security and privacy in cloud platforms, optimizing concurrent paths with learning methods, and improving the efficiency of cloud task scheduling algorithms. Furthermore, Partial Petri Nets could be applied to analyse emerging lightweight security protocols tailored for Internet of Things and edge computing architectures. By pursuing both theoretical advancements and practical implementations, the understanding and impact of Partial Petri Nets can continue to expand.