# Non-Recursive LSAWfP Models are Structured Workflows

Milliam Maxime Zekeng Ndadji, Daniela Marionne Nguedia Momo, Franck Bruno Tonle Noumbo, Maurice Tchoupé Tchendji

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

## To cite this version:

Milliam Maxime Zekeng Ndadji, Daniela Marionne Nguedia Momo, Franck Bruno Tonle Noumbo, Maurice Tchoupé Tchendji. Non-Recursive LSAWfP Models are Structured Workflows. Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 2023, Volume 38 - CARI 2022 - 2023 (CARI 2022), 10.46298/arima.11183. hal-04064065v2

HAL Id: hal-04064065

https://inria.hal.science/hal-04064065v2

Submitted on 5 Jul 2023

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

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

<figure><img src="image_2.png" /></figure>
# Non-Recursive LSAWfP Models are Structured Workflows

Milliam Maxime ZEKENG NDADJI*<fnref n="1" />,<fnref n="2" />,
Daniela Marionne NGUEDIA MOMO<fnref n="1" />,
Franck Bruno TONLE NOUMBO<fnref n="1" />,<fnref n="3" />,
Maurice TCHOUPÉ TCHENDJI<fnref n="1" />,<fnref n="2" />

*E-mail: ndadjimaxime@yahoo.fr

DOI: 10.46298/arima.11183

Submitted on 13 april 2023 - Published on 04 july 2023

Volume: 38 - Year: 2023

Special Issue: **CARI 2022**

Editors: Mathieu Roche, Nabil Gmati, Amel Ben Abda, Marcellin Nkenlifack

## Abstract

Workflow languages are a key component of the Business Process Management (BPM) discipline: they are used to model business processes in order to facilitate their automatic management by means of BPM systems. There are numerous workflow languages addressing various issues (expressiveness, formal analysis, etc.). In the last decade, some workflow languages based on context-free grammars (having then formal semantics) and offering new perspectives to process modelling, have emerged: LSAWfP (a Language for the Specification of Administrative Workflow Processes) is one of them. LSAWfP has many advantages over other existing languages, but it is its expressiveness (which has been very little addressed in previous works) that is studied in this paper. Indeed, the work in this paper aims to demonstrate that any non-recursive LSAWfP model is a structured workflow. Knowing that the majority of commercial BPM systems only implement structured workflows, the result of this study establishes that, although LSAWfP is still much more theoretical, it is a language with commercial potential.

## Keywords

BPM; LSAWfP; Structured Workflows; Dyck Language; Serialisation

# I INTRODUCTION

In Business Process Management (BPM), process modelling is a key phase [1]. It is done using workflow languages and consists for a given process, in analysing it in order to define in a graphical way or by means of rules, its tasks and their execution order (this is called the process *control flow*), the actors in charge of executing these tasks and the data flow between the

<footnote n="1">¹Department of Mathematics and Computer Science, University of Dschang</footnote>

<footnote n="2">²FUCHSIA Research Associated Team, https://project.inria.fr/fuchsia/</footnote>

<footnote n="3">³International Centre of Insect Physiology and Ecology, http://www.icipe.org/</footnote>
tasks: the result is called a workflow model or process model<fnref n="1" /> [1]. Regarding the diversity of
application domains and professional needs for process modelling, researchers have proposed a
plethora of workflow languages; making it difficult to reach a consensus on which one to adopt
[1]. Among the most significant workflow languages are BPMN (Business Process Model and
Notation, considered as the de-facto workflow language) [2], WF-Net (Workflow Net) [3] and
YAWL (Yet Another Workflow Language) [3]. In 2020, Zekeng et al. proposed the *Language
for the Specification of Administrative Workflow Processes* (LSAWfP) [4] addressing several
issues encountered by classical languages, notably: the absence of formal semantics, the use of
processes as modelling units, the obtention of either non-executable specifications or context-
specific executable ones, etc. LSAWfP proposes to model the control flow of a given process
using a grammatical model called *Grammatical Model of Workflow* (GMWf).

This work is interested in the expressiveness of LSAWfP from its control flow perspective. In the BPM domain, the study of the expressiveness of workflow languages is a common practice whose goal is to show their credibility; however, previous works on LSAWfP have paid insufficient attention to this aspect. For instance, the work in [4] shows that, for its control flow, LSAWfP supports the four basic routings, namely: sequential, parallel, alternative and iterative routings; but, the results of this study don't provide sufficient evidence to characterise the class(es) of workflows supported by LSAWfP. The contribution of this paper is to formally establish that LSAWfP models whose GMWf does not admit recursivity<fnref n="2" /> (non-recursive LSAWfP models) are *structured workflows*. It is then established that some elements of the subclass of structured workflows that do not admit iteration can be modelled using LSAWfP.

The concept of structured workflow has been popularised in works published in the early 2000s
[5] and has been the subject of several studies in the last two decades; it refers to a class of work-
flows for which several syntactic restrictions have been applied on the control flow. Throughout
these works, several formalizations of structured workflows and identification of their properties
were made. Furthermore, it was established that this class of workflows is supported by many
commercial BPM systems (TIBCO BPM Enterprise<fnref n="3" />, Signavio<fnref n="4" />, Bizagi<fnref n="5" />, SAP R/4HANA<fnref n="6" />,
etc.). The study carried out in this paper finds its relevance in showing that LSAWfP is ex-
pressive enough to be embedded in a commercial BPM system; and in this case, LSAWfP will
provide a new and advantageous tool for designing workflow models, while preserving the al-
ready existing commercialised knowledge.

The rest of this paper is organised as follows: some basic concepts useful for the understanding of this paper are briefly presented in section II. The contribution is presented in section III. Sections IV and V are dedicated respectively to a discussion and conclusion.

<footnote n="1">¹Process and workflow are often used as synonyms: this is the case in this paper.</footnote>

<footnote n="2">²Informally, a non-recursive grammar is a grammar in which there is no non-terminal symbol whose expansion by means of productions allows to obtain a string containing this same symbol.</footnote>

<footnote n="3">³https://www.tibco.com/products/business-process-management</footnote>

<footnote n="4">⁴https://www.signavio.com/</footnote>

<footnote n="5">⁵https://www.bizagi.com/</footnote>

<footnote n="6">⁶https://www.sap.com/products/s4hana-erp.html</footnote>
### 2.1 Some basic concepts

A workflow is generally composed of a collection of activities/tasks, a set of actors, and dependencies between activities. Activities correspond to individual steps in a business process, actors are responsible for the enactment of activities, and dependencies determine the execution sequence of activities and the data flow between them. From the control flow perspective, Kiepuszewski et al. [6] state that a workflow $\mathcal{W}$ consists of a set of process elements $\mathcal{P}$, and a transition relation $\mathit{Trans} \subseteq \mathcal{P} \times \mathcal{P}$ between elements. The set of process elements can be further divided into a set $O_j$ of or-joins, a set $O_s$ of or-splits, a set $A_j$ of and-joins, a set $A_s$ of and-splits, and a set $\mathcal{A}$ of activities.

Generally, the main purpose of a workflow language is to provide tools (graphical or not) to represent process elements and the relations between them. For example, the BPMN language [2] represents the activities (elements of $\mathcal{A}$) by rectangles, the elements of $O_j$, $O_s$, $A_j$, $A_s$ by associated diamond shapes and their relations by arrows. One of the main criticisms of workflow languages is that, they permit an arbitrary composition of process elements when building workflow models. Indeed, this arbitrary character is illustrated by a lack of ordering during the aggregation of the different elements constituting the workflows [6]. In order to remedy this, Kiepuszewski et al. propose several concepts, in particular, that of structured workflows.

### 2.2 Structured workflows

#### 2.2.1 Definition

A Structured Workflow (SW) is intuitively defined as a workflow in which, each or-split has a corresponding or-join and each and-split has a corresponding and-join [5]. This type of workflow guarantees significant properties: for example, a well-formed SW can't deadlock (become stuck in an indefinite waiting state) [5]. This class of workflows is one of the most requested by researchers in their formal analysis of workflows [7]. In a more formally way, Kiepuszewski et al [6] define a SW inductively as follows:

**Definition 1: Structured Workflow (SW)**

1. A workflow consisting of a single activity is a SW (**Single-activity pattern**);

2. Let X and Y be SWs. The concatenation of these workflows is a SW (**Sequence pattern**);

3. Let $X_1, \dots, X_n$ be SWs, $oj$ an or-join and $os$ an or-split. The workflow with $os$ as initial element, $oj$ as final element, transitions between $os$ and the initial elements of $\{X_i\}_{1\le i\le n}$ and, other transitions between the final elements of $\{X_i\}_{1\le i\le n}$ and $oj$, is then also SW (**Or pattern**);

4. Let $X_1, \dots, X_n$ be SWs, $aj$ an and-join and $as$ an and-split. The workflow with $as$ as initial element, $aj$ as final element, transitions between $as$ and the initial elements of $\{X_i\}_{1\le i\le n}$, and other transitions between the final elements of $\{X_i\}_{1\le i\le n}$ and $aj$, is then also SW (**And pattern**);

5. Let X and Y be SWs, $oj$ an or-join and $os$ an or-split. The workflow with $oj$ as initial element, $os$ as final element, transitions between $oj$ and the initial element of X, between
the final element of X and *os*, between *os* and the initial element of Y, and between the
final element of Y and *oj*, is then also a SW (**Loop pattern**).

Figure 1 shows minimum SWs corresponding to the five patterns in definition 1.

<figure><img src="image_3.png" /><figcaption>Figure 1: Illustration of structured workflows patterns</figcaption></figure>

2.2.2 Some formalizations of SWs

Several studies have been focused on SWs during the last two decades; they proposed formal tools for the smooth handling of SWs. Jussi Vanhatalo et al. [8] have proposed to represent a structured workflow as a unique tree called Process Structure Tree (PST). This tree is obtained after the decomposition of the workflow into Single Entry Single Exit fragments. *A fragment of a given SW is a subset of its process elements that form a graph.* More precisely, the workflow is split into canonical fragments<fnref n="7" />; then, these canonical fragments are arranged to form a PST. The PST, computed in linear time, provides the necessary information about all the process elements, as well as the precedence relations between them. Its tree structure also allows formalizing operations such as well-structured and soundness verifications.

Another version of the PST called Redefined Process Structure Tree (RPST) has been proposed by Jussi Vanhatalo et al. [7]. Unlike PST, RPST guarantees that a local change on the initial SW will only cause a local change on the resulting RPST. These tree-based formalizations of SWs gives us confidence in the grammatical approach of the work done in this paper. Indeed, in this paper, SWs are handled as Dyck words: i.e. as serializations of derivation trees for the grammar of the well-formed parenthesis language (Dyck language). It is this connection between SW and Dyck language that allows to establish the results presented in section III.

Besides PST and RPST, other studies [9, 10] have proposed Petri nets as a formal tool for
handling SWs. Thanks to the mathematical character of Petri nets and to the numerous existing
studies on their properties, they prove to be very useful for the study of the properties of SWs.

**2.3 Non-recursive LSAWfP models**

LSAWfP (a Language for the Specification of Administrative Workflow Processes) is a work-
flow language proposed by Zekeng et al [4]. In this one, the process control flow is modelled
using a grammar $G = (S, P, A)$ called **Grammatical Model of Workflow (GMWf)** defined as
follows :

Definition 2: Grammatical Model of Workflow (GMWf)

A GMWf $G$ is defined by a triplet $(S, P, A)$ in which :

* $S$ is a finite set of **grammatical symbols** or **sorts** corresponding to various **activities** to be carried out in the studied process;

<footnote n="7">⁷A canonical fragment is a fragment containing as few process elements as possible and whose combination corresponds to one of the patterns defined in [8], making it convertible into one or more elements of a PST.</footnote>
• $\mathcal{A} \subseteq \mathcal{S}$ is a finite set of particular symbols called **axioms**, representing activities that can start an execution scenario, and

• $\mathcal{P} \subseteq \mathcal{S} \times \mathcal{S}^*$ is a finite set of **productions** decorated by the annotations $"\overset{\circ}{\mathcal{S}}"$ (is sequential to) and $"\|\|$" (is parallel to): they are **precedence rules**. A production $P = (X_{P(0)}, X_{P(1)}, \dots, X_{P(|P|)})$ is either of the form $P : X_0 \rightarrow X_1 \overset{\circ}{\mathcal{S}} \dots \overset{\circ}{\mathcal{S}} X_{|P|}$, or of the form $P : X_0 \rightarrow X_1 \| \dots \| X_{|P|}$. The first form $P : X_0 \rightarrow X_1 \overset{\circ}{\mathcal{S}} \dots \overset{\circ}{\mathcal{S}} X_{|P|}$ (resp. the second form $P : X_0 \rightarrow X_1 \| \dots \| X_{|P|}$) means that activity $X_0$ must be executed before activities $\{X_1, \dots, X_{|P|}\}$ that must be (resp. can be) executed in sequence (resp. in parallel) from the left to the right. A production with the symbol $X$ as left-hand side is called a **X-production**. Given a production $P$, $|P|$ designates the length of its right-hand side.

The obtained specification after modelling a process with LSAWfP is called a LSAWfP model. A preliminary study of LSAWfP's expressiveness in [4], shows that it supports the basic routings pattern (sequential, parallel, alternative, iterative) in the definition of control flows. But, in this study, we are interested in a restricted form of LSAWfP models named *non-recursive LSAWfP models* that can be defined as follows:

**Definition 3: Non-recursive LSAWfP model**

A non-recursive LSAWfP model is a LSAWfP model whose GMWf (its grammar) is non-recursive.

We are interested in non-recursive LSAWfP models because they are the subclass of LSAWfP models in which activities are joined in a non-arbitrary way, using GMWf productions; this is actually their common point with structured workflows. Despite the fact that non-recursive LSAWfP models do not directly express iterative routing between process activities, they are useful in several practical cases; especially for administrative processes in which the recursivity (the number of repetitions) is generally bounded [11].

### III SERIALIZING NON-RECURSIVE LSAWFP MODELS INTO WORDS OF A VERSION OF DYCK'S LANGUAGE DEDICATED TO LOOPLESS STRUCTURED WORKFLOWS SPECIFICATION

Let's remind that the goal of this paper is to establish that any non-recursive LSAWfP model is a SW. To achieve this, we first consider a restriction of SWs class called *Loopless Structured Workflows (LSW)*; and, we establish that the workflows in this new class can be assimilated to words of a version of Dyck's language that is presented. Conversely, we show that the words in this version of Dyck's language which we refer to as *Dyck's language for LSW* (denoted $Dyck^{LSW}$), are LSW. Finally, we present a production rewriting algorithm to serialize any non-recursive GMWf into a word of $Dyck^{LSW}$ (i.e., into a SW through transitivity). The result of this paper (corollary 1) is therefore the consequence of two necessary and sufficient demonstrations (even if we provide an additional result with proposition 2):

1. The demonstration that any non-recursive GMWf is a word in the $Dyck^{LSW}$ language (proposition 3) and,

2. The demonstration that any word in the $Dyck^{LSW}$ language is a LSW (proposition 1).
## 3.1 Loopless Structured Workflows (LSW)

Inspired by the notion of fragment used in the definition of PST and RPST (see section 2.2.2), we introduce the notion of *structured fragments*.

**Definition 4: Structured fragment**

A structured fragment is a fragment corresponding to one of the five patterns in definition 1, allowing to recursively define SW.

Intuitively, a LSW is a SW in which no structured fragment matches the loop pattern of the SW definition (definition 1). Therefore, a LSW can be defined inductively as follows:

**Definition 5: Loopless Structured Workflow (LSW)**

1. A workflow consisting of a single activity is a LSW (**Single-activity pattern**);

2. Let X and Y be LSWs. The concatenation of these workflows is a LSW (**Sequence pattern**);

3. Let $X_1, \dots, X_n$ be LSWs. The "Or pattern" as defined in definition 1, applied to $X_1, \dots, X_n$, results to a LSW (**Or pattern**);

4. Let $X_1, \dots, X_n$ be LSWs. The "And pattern" as defined in definition 1, applied to $X_1, \dots, X_n$, results to a LSW (**And pattern**).

Given the only four patterns considered in the definition of LSWs, these can be expressed as words in a version of Dyck's language: the *Dyck's language for LSW (Dyck<sup>LSW</sup>)*. As a reminder, the Dyck language consists of strings of equal number of opening and closing brackets, and the number of closing brackets is never more than the opening brackets in any prefix of the string [12]. Indeed, considering definition 5, one can represent a single activity workflow by the following *Dyck<sup>LSW</sup>*'s word : $\langle (i)_i \rangle$. In this representation, $\langle$ and $\rangle$ represent the start and end events of the process and, $(i)_i$ is a pair of colored parentheses representing the single activity being considered. The language *Dyck<sup>LSW</sup>* is denoted by the grammar of definition 6:

**Definition 6: Dyck<sup>LSW</sup>'s grammar**

The grammar for the language *Dyck<sup>LSW</sup>* is defined by $\mathcal{G}_{Dyck<sup>LSW</sup>} = (\mathcal{N}, \mathcal{T}, \mathcal{P}, Flow)$ where:

* $\mathcal{N} = \{Flow, FragList, Frag, NextFrag, Seq, Or, And\}$ is the set of non-terminals;

* $\mathcal{T} = \{(\langle), \rangle, [\searrow], ]\searrow, [\wedge], ]\wedge, (\cdot)\} \cup \{(i), (i)_i\}_{1\le i\le n}$ is the set of terminals; these are colored brackets that specify respectively, the start event, the end event, the or-split, the or-join, the and-split, the and-join, classical parentheses used to group blocks to avoid ambiguity when necessary and the different activities that make up processes;

* $\mathcal{P}$ is the set composed by the following productions:

<figure><img src="image_4.png" /></figure>
• *Flow* is the axiom.

One can observe from the productions $p_5$ and $p_6$ of $\mathbb{G}_{Dyck^{LSW}}$, that in any word of $Dyck^{LSW}$, to each or-split (resp. and-split) corresponds an or-joint (resp. and-joint). Moreover, the productions $p_1, p_2, p_3$ and $p_7$ show that the simplest words accepted by $\mathbb{G}_{Dyck^{LSW}}$ are of the form $\langle (i)_i \rangle$: they are LSWs consisting of a single activity.

**Proposition 1:**

Any word in the $Dyck^{LSW}$ language is a LSW.

*Proof.* Based on the LSW definition (see section 3.1, first paragraph), providing a proof of this proposition means to show that any word $w$ of the language $Dyck^{LSW}$ is a sequence of (loopless) structured fragments. One can also reason by the absurd and so, establish that it is absurd to assert that $w$ is not a sequence of (loopless) structured fragments: that is what is done in this proof.

By analysing the productions $p_1, p_2$ and $p_7$ of $\mathbb{G}_{Dyck^{LSW}}$, it is obvious to establish that $w \in Dyck^{LSW}$ has the form $\langle f_1f_2\dots f_n \rangle$; i.e. $w$ is a sequence of fragments (the $\{f_i\}_{1\le i \le n}$) surrounded by the symbols $\langle$ and $\rangle$. This corresponds to the workflow diagram shown in figure 2. Therefore, $w$ is not a sequence of (loopless) structured fragments if and only if at least one of

<figure><img src="image_5.png" /><figcaption>Figure 2: Workflow diagram patterns for a Dyck<sup>LSW</sup> word.</figcaption></figure>

the fragments that compose it is not structured; i.e., among the workflow diagrams associated to the fragments of $w$, there are one or more in which there are or-splits (resp. and-splits) without corresponding or-joints (resp. and-joints) and conversely. Another analysis of the productions of $\mathbb{G}_{Dyck^{LSW}}$ reveals that each fragment $f_i$ is of one of the following forms:

1. $(i)_i$ (see production $p3$);

2. $(f_{i1})$ (see productions $p2$ and $p7$);

3. $f_{i1}f_{i2}\dots f_{im}$ (see productions $p3$ and $p4$);

4. $[\vee f_{i1}f_{i2}\dots f_{i0}]_{\vee}$ (see productions $p3$ and $p5$);

5. $[\wedge f_{i1}f_{i2}\dots f_{ip}]_{\wedge}$ (see productions $p3$ and $p6$).

In these, the $\{f_{ij}\}$ are also fragments and the workflow diagrams that are associated with each of these forms are those presented in figure 3: all the fragments are therefore structured (i.e. they match the patterns listed in definition 5 and illustrated in figure 1) and consequently, it is absurd to think that there could be a situation in which one could find some or-splits (resp. and-splits) without corresponding or-joints (resp. and-joints) and vice versa. For any $Dyck^{LSW}$ word, one can always find an equivalent LSW, by combination of structured fragments. ☐

**Proposition 2:**

Any LSW is a word in the language $Dyck^{LSW}$.
<figure><img src="image_6.png" /><figcaption>Figure 3: Patterns of fragments in a Dyck<sup>LSW</sup> word and corresponding workflow diagram patterns.</figcaption></figure>

*Proof.* By definition, a LSW can be decomposed into a list of structured fragments (see section 3.1). The different patterns of structured fragments of LSW (see definition 5) can be derived from the productions of the grammar $G_{Dyck^{LSW}}$ as established in the proof of proposition 1. Also in this proof, it is established that *Dyck*<sup>*LSW*</sup> words are lists of structured fragments. Therefore, any LSW can be expressed as a *Dyck*<sup>*LSW*</sup> word. ☐

Having established that any word in the *Dyck*<sup>*LSW*</sup> language is a LSW, the next part of this paper's contribution consists in showing that any non-recursive LSAWfP model (its GMWf) can be serialised into a *Dyck*<sup>*LSW*</sup> word.

## 3.2 Non-recursive LSAWfP models serialisation to *Dyck*<sup>*LSW*</sup> words

The proof of the proposition 1 allowed to establish that similarly to LSWs, each word of *Dyck*<sup>*LSW*</sup> is built by combining structured fragments. However, this combination is not made randomly. Indeed, the structured fragments are combined in such a way that the resulting fragment is also structured: it thus becomes a potential *Dyck*<sup>*LSW*</sup> word (all that remains is to surround it with the start and end events represented by the symbols ( and )). A structured fragment can therefore be simple (it is of the form $(i)_i$) or composite (i.e. it results from the combination of several simple or composite structured fragments). Figure 3 through its patterns 3, 4 and 5, shows that in the *Dyck*<sup>*LSW*</sup> language, there are exactly three ways to combine structured fragments. Formally, one can define the operators *CONCAT*, *OR* and *AND* allowing to realise each of these combinations of structured fragments, as follows:

### Definition 7: Operators *CONCAT*, *OR* and *AND*

Let $w_1, w_2, w_3, \dots, w_n$ be structured fragments that can compose a *Dyck*<sup>*LSW*</sup> word.

1. The concatenation of these fragments is done using the operator *CONCAT* that acts as follows:

$$ \text{CONCAT}(w_1, w_2, w_3, \dots, w_n) = w_1 w_2 w_3 \cdots w_n. $$

2. The operator *OR* acts as follows:

$$ \text{OR}(w_1, w_2, w_3, \dots, w_n) = [\bigvee (w_1) (w_2) (w_3) \cdots (w_n)]\bigvee \text{ or} $$

$$ \text{OR}(w_1, w_2, w_3, \dots, w_n) = [\bigvee w_1 w_2 w_3 \cdots w_n]\bigvee \text{ when there is no ambiguity. In addition,} $$

$\text{OR}(w_1)$ is identity: i.e. $\text{OR}(w_1) = w_1$;

3. The operator *AND* acts as follows:

$$ \text{AND}(w_1, w_2, w_3, \dots, w_n) = [\bigwedge (w_1) (w_2) (w_3) \cdots (w_n)]\bigwedge \text{ or} $$

$$ \text{AND}(w_1, w_2, w_3, \dots, w_n) = [\bigwedge w_1 w_2 w_3 \cdots w_n]\bigwedge \text{ when there is no ambiguity. In addition, } \text{AND}(w_1) = w_1. $$
**Property 1:**

Operators *CONCAT*, *OR* and *AND* are well-defined functions of domain $\mathcal{T}^* \times \dots \times \mathcal{T}^*$ and codomain $\mathcal{T}^*$ where $\mathcal{T}$ is the set of terminals of $\mathbb{G}_{Dyck}^{LSW}$ presented in definition 6.

### 3.2.1 The serialisation principle

The first step to serialise a given GMWf $\mathbb{G} = (\mathcal{S}, \mathcal{P}, \mathcal{A})$, is to know how to rewrite the right-hand sides of productions such as to obtain structured fragments in these right-hand parts. In the context of this paper, this rewriting is done using the function $Rw$ defined as follows:

**Definition 8: Function $Rw$**

For a given GMWf $\mathbb{G} = (\mathcal{S}, \mathcal{P}, \mathcal{A})$, the function $Rw: \mathcal{P} \to \mathcal{S} \times \mathcal{T}^*$ takes as input a production $p \in \mathcal{P}$ and produces as output a rewritten version of $p$ noted $p' \in \mathcal{S} \times \mathcal{T}^*$ such as the right hand side of $p'$ is a structured fragment that can compose a word of $Dyck^{LSW}$. $Rw$ operates as follows:

$$Rw(p) = \left\{ \begin{array}{ll} X & \rightarrow \epsilon \qquad \text{if } p: X \rightarrow \epsilon \\ X_0 & \rightarrow \text{CONCAT} \left( \left\{ (i)_i \text{ OR } \left( \{\text{rhs}(Rw}(p_{X_{ij}})\)}_{1 \le j \le m_i} \right) \right\}_{1 \le i \le |p|} \right) \\ X_0 & \rightarrow \text{AND} \left( \left\{ (i)_i \text{ OR } \left( \{\text{rhs}(Rw}(p_{X_{ij}})\)}_{1 \le j \le m_i} \right) \right\}_{1 \le i \le |p|} \right) & \text{if } p: X_0 \rightarrow X_1 \left\| \dots \left\| X_{|p|} \end{array} \right. \right. $$

*CONCAT*, *OR* and *AND* are the operators presented in definition 7⁸; the $\{p_{X_{ij}}\}_{1 \le j \le m_i}$ are the $X_i$-productions of the GMWf $\mathbb{G}$ and $\epsilon$ is also used to represent an empty fragment.

**Property 2:**

The function $Rw$ is well-defined (it is defined for all the types of productions used to build GMWfs and the rewrites only make use of well-defined functions).

**Property 3:**

The $Rw$ function loops indefinitely for productions that allow recursive symbols (appearing on both the left hand and right hand sides).

**Property 4:**

Even more globally, the $Rw$ function produces the expected result only for the productions of a non-recursive GMWf.

Knowing how to rewrite the right-hand sides of productions, the serialised version of a given GMWf $\mathbb{G}$ is obtained using the function $Ser$ defined as follows:

**Definition 9: Function $Ser$**

$$ \begin{array}{l} Ser: (\mathcal{S}, \mathcal{P}, \mathcal{A}) \rightarrow \mathcal{T}^* \\ \mathbb{G} \mapsto \left\langle OR \left( \left\{ (A_i)_{A_i} \text{ OR } \left( \{\text{rhs}(Rw}(p_{A_{ij}})\)}_{1 \le j \le m_i} \right) \right\}_{1 \le i \le |\mathcal{A}|} \right) \right\rangle \\ \text{where the } \{p_{A_{ij}}\}_{1 \le i \le |\mathcal{A}|; 1 \le j \le m_i} \text{ are the } A_i\text{-productions and the} \\ \{A_i \in \mathcal{A}\} \text{ are the axioms of } \mathbb{G}. \end{array} $$

<footnote n="8">⁸For the sake of clarity in the presentation, the following $OR(\{\text{rhs}(Rw}(p_{X_{ij}})\)}_{1 \le j \le m_i}$ is noted for $OR(\text{rhs}(Rw}(p_{X_{i_1}}), \dots, \text{rhs}(Rw}(p_{X_{i_m}}))$; this notation is also used for the operators *CONCAT* and *AND*.</footnote>
**Property 5:**

The function *Ser* is well defined (as the result of the application of well-defined functions).

**Proposition 3:**

Any non-recursive GMWf is "serialisable" as a word in the *Dyck*<sup>*LSW*</sup> language.

*Proof.* The function *Ser* that serialises a given GMWF acts by combining with the help of the *OR* function, the right hand sides of the rewritten versions of the *A*<sub>*i*</sub>-productions (rewrites are always possible when the GMWF is non-recursive). It thus combines structured fragments (the right hand sides of the rewritten productions are structured fragments) to obtain another one. The resulting structured fragment is surrounded by the symbols ( and ) to obtain the desired serialisation: this one is thus a Dyck word as established in the proof of proposition 1. ☐

**Corollary 1: The defended result in this paper**

Non-Recursive LSAWfP Models are Structured Workflows (propositions 3 and 1 make this true).

### 3.2.2 An illustrative example

To better illustrate the presented concepts, let us take as an application case, the serialisation of the LSAWfP model coming from the running example of [13]. The considered GMWF $\mathcal{G} = (\mathcal{S}, \mathcal{P}, \mathcal{A})$ is the one describing a peer review process. In it, $\mathcal{S}$ (the set of activities) is given by $\mathcal{S} = \{A, B, C, D, S1, E1, E2, F, G1, G2, H1, H2, I1, I2\}$, $\mathcal{A}$ (the set of axioms) is given by $\mathcal{A} = \{A\}$ and, the productions are the ones listed in the leftmost column of table 1. By applying the rewrite principle described in definition 8, one should obtain the rewritten productions listed in the rightmost column of table 1.

<table><caption>Table 1: GMWF productions and their rewritten versions</caption><thead><tr><th>Productions</th><th>Rewritten Productions</th></tr></thead><tbody><tr><td>P<sub>1</sub>: A → B<sub>9</sub> D</td><td>RP<sub>1</sub>: A → (B)<sub>B</sub> (D)<sub>D</sub></td></tr><tr><td>P<sub>2</sub>: A → C<sub>9</sub> D</td><td>RP<sub>2</sub>: A → (C)<sub>C</sub> (E)<sub>E</sub> [∧((G<sub>1</sub>)<sub>G<sub>1</sub></sub>(H<sub>1</sub>)<sub>H<sub>1</sub></sub>(I<sub>1</sub>))((G<sub>2</sub>)<sub>G<sub>2</sub></sub>(H<sub>2</sub>)<sub>H<sub>2</sub></sub>(I<sub>2</sub>))]∧(F)<sub>F</sub>(D)<sub>D</sub></td></tr><tr><td>P<sub>3</sub>: C → E<sub>9</sub> F</td><td>RP<sub>3</sub>: C → (E)<sub>E</sub> [∧((G<sub>1</sub>)<sub>G<sub>1</sub></sub>(H<sub>1</sub>)<sub>H<sub>1</sub></sub>(I<sub>1</sub>))((G<sub>2</sub>)<sub>G<sub>2</sub></sub>(H<sub>2</sub>)<sub>H<sub>2</sub></sub>(I<sub>2</sub>))]∧(F)<sub>F</sub></td></tr><tr><td>P<sub>4</sub>: E → G1 || G2</td><td>RP<sub>4</sub>: E → [∧((G<sub>1</sub>)<sub>G<sub>1</sub></sub>(H<sub>1</sub>)<sub>H<sub>1</sub></sub>(I<sub>1</sub>))((G<sub>2</sub>)<sub>G<sub>2</sub></sub>(H<sub>2</sub>)<sub>H<sub>2</sub></sub>(I<sub>2</sub>))]∧</td></tr><tr><td>P<sub>5</sub>: G1 → H1<sub>9</sub>I1</td><td>RP<sub>5</sub>: G1 → (H<sub>1</sub>)<sub>H<sub>1</sub></sub> (I<sub>1</sub>)<sub>I1</sub></td></tr><tr><td>P<sub>6</sub>: G2 → H2<sub>9</sub>I2</td><td>RP<sub>6</sub>: G2 → (H<sub>2</sub>)<sub>H<sub>2</sub></sub> (I<sub>2</sub>)<sub>I2</sub></td></tr><tr><td>P<sub>7</sub>: B → ε</td><td>RP<sub>7</sub>: B → ε</td></tr><tr><td>P<sub>8</sub>: D → ε</td><td>RP<sub>8</sub>: D → ε</td></tr><tr><td>P<sub>9</sub>: F → ε</td><td>RP<sub>9</sub>: F → ε</td></tr><tr><td>P<sub>10</sub>: H1 → ε</td><td>RP<sub>10</sub>: H1 → ε</td></tr><tr><td>P<sub>11</sub>: I1 → ε</td><td>RP<sub>11</sub>: I1 → ε</td></tr><tr><td>P<sub>12</sub>: H2 → ε</td><td>RP<sub>12</sub>: H2 → ε</td></tr><tr><td>P<sub>13</sub>: I2 → ε</td><td>RP<sub>13</sub>: I2 → ε</td></tr></tbody></table>

The serialised version of the GMWF $\mathcal{G}$ is finally obtained by applying the formula presented in definition 9, and its value is as follows:

$$ Ser(\mathcal{G}) = \langle (A)_A[\bigvee((B)_B(D)_D) ((C)_C(E)_E [\bigwedge((G_1)_{G_1}(H_1)_{H_1}(I_1))((G_2)_{G_2}(H_2)_{H_2}(I_2))]) \wedge (F)_F(D)_D] \bigvee \rangle $$

Figure 4 gives a graphical representation of the structured workflow described by the obtained *Dyck*<sup>*LSW*</sup> word.
<figure><img src="image_7.png" /><figcaption>Figure 4: Workflow diagram corresponding to the GMWf of the illustrative example.</figcaption></figure>

## IV DISCUSSION AND FURTHER WORK

The work done and presented in this paper has established that a class of workflows modelled with LSAWfP is equivalent to the class of LSWs. The results obtained reinforce the idea that LSAWfP language is defined on a solid formal basis that can facilitate the study of the properties of LSAWfP models. Most of the existing studies like [14], aiming at showing the equivalence between two classes of workflows specified in two different languages, proceed by converting models from one language to the other. This is what has been done in this paper with the particularity that, it was first necessary to find a formal mean (the language *Dyck<sup>LSW</sup>*) to specify structured workflows. As a result, it can be observed that it is possible to model structured workflows not only using a version of Dyck's language, but also using the LSAWfP language. The methodology used in this paper has been strengthened by proofs of several properties of the manipulated mathematical tools. However, the paper was only interested in a sub-language of the LSAWfP language (the non-recursive LSAWfP models); an extension of the work done here to the whole LSAWfP language would certainly be more beneficial.

The result presented here opens the way to several potential works, notably: the conversion of LSAWfP specifications into classical formats such as those of the BPMN language, the verification of LSAWfP models and the use of a version of the Dyck language as a workflow language.

## V CONCLUSION

In this paper, we have conducted some formalisation studies in order to show the relation between a subset of structured workflows (LSW) and a subset of workflows that can be modelled with the LSAWfP language (non-recursive LSAWfP models). We used a variant of Dyck's language as an intermediate mathematical tool between the two manipulated subsets. The results of this paper help to promote LSAWfP by revealing a little more its commercial potential and, offers some interesting perspectives in the analysis of its expressiveness. Immediate research avenues that could be of interest to potential researchers are: analysis and verification of LSAWfP specifications, conversion of an LSAWfP specification into a BPMN specification, integration of LSAWfP as a process modelling method in various commercial BPM systems.

## REFERENCES

[1] M. Dumas, M. La Rosa, J. Mendling, and H. A. Reijers. *Fundamentals of Business Process Management, Second Edition*. Springer, 2018. ISBN: 978-3-662-56508-7.

[2] B. P. Model. "Notation (BPMN) version 2.0". In: *OMG Specification, Object Management Group* (2011), pages 22–31.
[3] W. M. P. Van Der Aalst and A. H. M. Ter Hofstede. "YAWL: yet another workflow language". In: *Information systems* 30.4 (2005), pages 245–275.

[4] M. M. Zekeng Ndadji, M. Tchoupé Tchendji, C. Tayou Djamegni, and D. Parigot. "A Language and Methodology based on Scenarios, Grammars and Views, for Administrative Business Processes Modelling". In: *ParadigmPlus* 1.3 (2020), pages 1–22.

[5] B. Kiepusewski. "Expressiveness and suitability of languages for control flow modelling in workflows". PhD thesis. Queensland University of Technology, Brisbane, 2003.

[6] B. Kiepuszewski, A. H. M. ter Hofstede, and W. M. P. van der Aalst. "Fundamentals of control flow in workflows". In: *Acta Informatica* 39.3 (2003), pages 143–209.

[7] J. Vanhatalo, H. Völzer, and J. Koehler. "The refined process structure tree". In: *Data & Knowledge Engineering* 68.9 (2009), pages 793–818.

[8] J. Vanhatalo, H. Völzer, and F. Leymann. "Faster and more focused control-flow analysis for business process models through sese decomposition". In: *International Conference on Service-Oriented Computing*. Springer. 2007, pages 43–55.

[9] N. R. Adam, V. Atluri, and W.-K. Huang. "Modeling and analysis of workflows using Petri nets". In: *Journal of Intelligent Information Systems* 10.2 (1998), pages 131–158.

[10] D. Liu, J. Wang, S. C. Chan, J. Sun, and L. Zhang. "Modeling workflow processes with colored Petri nets". In: *computers in industry* 49.3 (2002), pages 267–281.

[11] M. M. Zekeng Ndadji. "A Grammatical Approach for Distributed Business Process Management using Structured and Cooperatively Edited Mobile Artifacts". PhD thesis. University of Dschang, Cameroon, 2021.

[12] X. Yu, N. T. Vu, and J. Kuhn. "Learning the Dyck language with attention-based Seq2Seq models". In: *Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP*. 2019, pages 138–146.

[13] M. M. Zekeng Ndadji, M. Tchoupé Tchendji, C. Tayou Djamegni, and D. Parigot. "A projection-stable grammatical model for the distributed execution of administrative processes with emphasis on actors' views". In: *Journal of King Saud University - Computer and Information Sciences* (2021). ISSN: 1319-1578.

[14] S. Pornudomthap and W. Vatanawood. "Transforming YAWL workflow to BPEL skeleton". In: *2011 IEEE 2nd International Conference on Software Engineering and Service Science*. 2011, pages 434–437.