arXiv CSopen access

Formal Grammars in Business Process Management: A Systematic Literature Review

FORMAL GRAMMARS IN BUSINESS PROCESS MANAGEMENT: A SYSTEMATIC LITERATURE REVIEW

arXiv:2606.27399v1 [cs.SE] 24 Jun 2026

MILLIAM MAXIME ZEKENG NDADJI Department of Mathematics and Computer Science, University of Dschang, PO Box 67, Dschang, Cameroon e-mail address: [email protected]

Abstract. Business Process Management (BPM) is concerned with the systematic design, execution, monitoring, and improvement of business processes. Formal grammars have emerged as a particularly fruitful formalism for BPM, offering generative, declarative, and analytical capabilities that are uniquely well-suited to process-oriented concerns. This paper presents a systematic literature review of 34 primary studies at the intersection of formal grammars and BPM. We identify seven research streams: (i) process grammars for organizational process design; (ii) process modeling languages evaluated as grammars under the Bunge-Wand-Weber ontological framework; (iii) production-rule grammars for process structural specification and variant management; (iv) attribute grammars for the declarative specification and distributed execution of workflows; (v) graph grammars for the transformation, generation, and semantic analysis of process models; (vi) grammatical inference for process mining and discovery; and (vii) process algebras as grammar-like compositional frameworks for behavioral specification and verification. For each stream, we synthesize contributions, formalisms employed, and limitations. The review reveals that formal grammars have influenced BPM across every lifecycle phase (from organizational design to formal verification and data-driven discovery) yet the seven streams have developed largely in parallel, without cross-stream synthesis. We identify five corpus-grounded open challenges and argue that a deeper, unified exploitation of grammatical theory holds significant promise for advancing the state of the art in BPM.

1. Introduction Business Process Management (BPM) is a well-established discipline concerned with the analysis, design, execution, monitoring, and continuous improvement of business processes [vdAtHW03, DLRMR18]. Over the past four decades, BPM has evolved from ad-hoc workflow automation into a principled field of research and practice, providing methods and tools for the systematic management of the operational core of organizations. The fundamental challenge of BPM is to bridge the gap between the informal knowledge that domain experts have about how work is done and the formal specifications required to automate, verify, and optimize that work. Formal grammars, introduced in theoretical computer science by Chomsky [Cho59] and subsequently enriched by a rich theory of string, tree, and graph rewriting systems, constitute one of the most powerful and flexible mathematical tools available for describing structured entities. A grammar specifies a potentially infinite Key words and phrases: Business Process Management, formal grammars, process modeling grammars, process mining, workflow languages, systematic literature review. Preprint submitted to Logical Methods in Computer Science

© M.M. Zekeng Ndadji CC ⃝ Creative Commons

2

M.M. ZEKENG NDADJI

set of admissible structures (a language) by means of a finite set of rewrite rules applied to an initial symbol. This generative character makes grammars particularly natural for describing processes: just as a grammar generates the sentences of a language, a process grammar can generate all the admissible execution traces of a business process. The connection between grammars and processes is not merely metaphorical. At the most basic level, the sequential, parallel, and iterative patterns that characterize process control flow correspond closely to the sequential composition, shuffle, and Kleene closure operators that underlie formal language theory. At a deeper level, attributed grammars provide a natural mechanism for integrating data-flow and role-assignment alongside structural control-flow, addressing one of the perennial weaknesses of traditional workflow formalisms. Graph grammars, on the other hand, are ideally suited to the graphical nature of process modeling notations such as Business Process Model and Notation (BPMN) [OMG13] and Yet Another Workflow Language (YAWL) [VDATH05], enabling rigorous specification of both syntax and semantics. Finally, grammatical inference techniques offer a principled bridge between empirical process data (event logs) and declarative process models, opening the door to grammar-based process mining. Despite this natural and multifaceted connection, no comprehensive survey of the role of formal grammars in BPM exists to date, to the best of our knowledge. Partial surveys of BPM formalism do exist [Bör12], but they treat grammars as one tool among many rather than as a central object of study, and systematic grammatical comparisons are absent. The present paper fills this gap by providing a systematic review of the literature at the intersection of formal grammars and BPM, spanning works from the mid-1990s to the mid-2020s. Our review identifies seven distinct research streams and synthesizes their contributions, formalisms, and open challenges. The specific contributions of this paper are as follows. First, we provide, to the best of our knowledge, the first comprehensive taxonomy of grammatical approaches in BPM, identifying seven streams of research. Second, we synthesize the key findings of each stream, highlighting the specific grammatical formalisms employed and the BPM lifecycle phases addressed. Third, we identify cross-cutting themes, research gaps, and directions for future work. The remainder of the paper is organized as follows. Section 2 provides the necessary background on BPM and formal grammars. Section 3 describes the review methodology. Sections 4–10 present the seven identified research streams. Section 11 provides a crosscutting discussion and identifies open challenges. Section 12 concludes the paper.

2. Background 2.1. Business Process Management. A business process is a set of activities that, together, achieve a specific organizational goal [DLRMR18]. The Workflow Management Coalition defines a workflow as the automation of a business process, in whole or part, during which documents, information, or tasks are passed from one participant to another for action, according to a set of procedural rules [Coa99]. BPM provides the methods, tools, and systems to support the design, enactment, management, and analysis of such processes. The BPM lifecycle typically comprises five phases: design and analysis, configuration, enactment, evaluation, and adaptation [DLRMR18]. In the design and analysis phase, processes are discovered, documented, and modeled using workflow languages. In the configuration phase, the resulting models are deployed onto a Workflow Management System (WfMS).

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

3

In the enactment phase, process instances are executed and monitored. In the evaluation phase, performance data is collected and analysed (sub-activities of this phase include formal verification of process correctness and monitoring of running instances) and in the adaptation phase, the process is improved accordingly; process discovery (automated model extraction from event logs) bridges adaptation back into design. These sub-activities are treated as distinct BPM concerns in the inclusion criteria and research questions of this review. Numerous workflow languages have been proposed to support these phases. Petri nets, notably in their workflow net (WF-net) variant [vdA96], provide a formal, graphbased foundation for process modeling with well-understood semantics. YAWL [VDATH05], designed to address the expressiveness requirements captured by the workflow patterns catalogue [VDATHKB03], extends WF-nets with additional control-flow constructs. Eventdriven Process Chains (EPCs) [STA05] support process modeling in enterprise information systems. The BPMN [OMG13], currently the de-facto standard for business process modeling, provides an extensive set of graphical constructs for describing processes in a notation accessible to both technical and non-technical stakeholders. A key weakness of many of these languages, however, is the informality of their semantics [DDO08, Bör12], which impedes formal analysis and verification. The artifact-centric approach [NC03, BGH+ 07] represents an alternative paradigm in which processes are driven by the data objects (artifacts) they manipulate, rather than by a fixed control flow. This approach is particularly relevant for our review, as it creates a natural opportunity for attribute grammar-based specification, where attributes on grammar symbols naturally capture the data fields of artifacts. 2.2. Formal Grammars: A Brief Overview. A formal grammar G = (V, Σ, R, S) consists of a finite set V of variables (non-terminals), a finite set Σ of terminal symbols (disjoint from V ), a finite set R of production rules, and a distinguished start symbol S ∈ V . The language L(G) generated by G is the set of all strings over Σ derivable from S by applying rules in R. The Chomsky hierarchy [Cho59, HMU07] classifies string grammars into four types by the form of their production rules. Regular grammars (Type 3) generate regular languages, recognized by finite automata; they capture sequential iteration but not nesting. Context-free grammars (CFGs, Type 2) allow rules of the form A → α, where A is a non-terminal and α is any string over V ∪ Σ; their languages are recognized by pushdown automata and naturally capture hierarchical, nested structure. Context-sensitive grammars (Type 1) are equivalently characterized by two standard formulations [HMU07]. In the restricted form, each rule has the shape αAβ → αγβ where A is a non-terminal, α, β ∈ (V ∪ Σ)∗ , and γ ∈ (V ∪ Σ)+ , so A is rewritten only in the surrounding context (α, β). In the equivalent non-contracting form, any rule u → v with |u| ≤ |v| is permitted (with the single exception S → ε, allowed only when S does not appear on the right-hand side of any rule). Both forms generate the same class of languages, which lies strictly between the context-free and recursively enumerable languages. Unrestricted grammars (Type 0) have no restrictions on their rules and generate recursively enumerable languages. Attribute grammars, introduced by Knuth [Knu68], extend CFGs with semantic attributes associated with each grammar symbol. Each production rule is augmented with semantic equations that specify how attribute values propagate: synthesized attributes flow bottom-up from children to parents, while inherited attributes flow top-down. Attribute grammars provide a principled mechanism for specifying the static semantics of formal languages and, by extension, for integrating data computation with structural specification in process models.

4

M.M. ZEKENG NDADJI

Graph grammars [Roz97] generalize string grammars to graph-structured objects. Rather than rewriting strings of symbols, graph grammars rewrite graphs by replacing sub-graphs according to production rules. Major formalisms include hyperedge replacement grammars (HRGs), in which rewriting is performed on hypergraphs, node-labelcontrolled (NLC) grammars, and algebraic approaches based on the single-pushout (SPO) or double-pushout (DPO) constructions. Graph grammars are particularly well-suited to BPM because process models are inherently graph-structured: nodes represent activities or events, and edges represent control or data flow. Grammatical inference (also called grammar induction) is the problem of learning a grammar from a sample of positive (and possibly negative) examples. Classical results establish the limits of identification in the limit from positive data: Gold’s theorem [HMU07] shows that any class of languages that contains all finite languages and at least one infinite language (including the regular languages and the context-free languages) cannot in general be identified in the limit from positive examples alone. For regular languages, however, efficient algorithms such as RPNI [OG92] succeed when the target language satisfies structural constraints derivable from the sample; for context-free languages, identification requires either negative examples, structural constraints (e.g., bracket annotations), or probabilistic relaxations. In the context of process mining, event logs constitute a finite corpus of positive execution traces, making grammatical inference a natural computational framework for process model discovery.

3. Review Methodology This review follows the systematic literature review (SLR) protocol described by Kitchenham and Charters [KC07] for software engineering research, adapted to the BPM and formal language theory context. The protocol comprises four phases: database search, screening and selection, classification, and synthesis.

3.1. Research Questions. This review is organized around four research questions derived from the gap identified in Section 1: RQ1: What types of formal grammar formalisms (string, attribute, graph, inferential, or process-algebraic) have been applied in BPM research, and how do they relate to the Chomsky hierarchy? RQ2: For which phases of the BPM lifecycle (design and analysis, configuration, enactment, evaluation, or adaptation—including verification, process discovery, and monitoring as analytical sub-activities) are formal grammar formalisms employed? RQ3: What are the key contributions and limitations of each identified research stream, and how do the streams compare with respect to formalism expressiveness and BPM coverage? RQ4: What are the principal open research challenges at the intersection of formal grammar theory and BPM, and what tools or methods are available to address them? These questions determine the search strategy (RQ1–RQ2), the inclusion criteria (RQ1– RQ2), the synthesis structure (RQ3), and the discussion section (RQ4).

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

5

3.2. Search Strategy. Six electronic databases were queried in February 2026: ACM Digital Library, IEEE Xplore, SpringerLink, ScienceDirect, Scopus, and Google Scholar. The following Boolean search strings were used systematically in each database: • "formal grammar" AND "business process"; • "process grammar"; • "graph grammar" AND ("workflow" OR "business process"); • "attribute grammar" AND "workflow"; • "grammatical inference" AND "process mining"; • "process modeling grammar"; • "context-free grammar" AND "business process"; • "hyperedge replacement grammar" AND "process". No publication-date restriction was applied. The search returned 526 records in total (ACM DL: 74; IEEE Xplore: 68; SpringerLink: 112; ScienceDirect: 93; Scopus: 101; Google Scholar: 78). 3.3. Inclusion and Exclusion Criteria. A paper was included if it satisfied both of the following criteria: (IC1) it proposed, applied, analysed, or formally grounded at least one grammar-based formalism, whether a technically operative grammar (string, attribute, or graph grammar, a grammatical inference algorithm, or a process-algebraic formalism whose term constructors constitute an inductive grammar over process expressions) or a conceptual grammar framework explicitly constructed in terms of a lexicon, rewrite rules, and constraints in direct analogy with a recognized class of formal grammars; and (IC2) its principal contribution addressed at least one phase of the BPM lifecycle, including the sub-activities of verification, process discovery, and monitoring as defined in Section 2. A paper was excluded if any of the following held: (EC1) grammars were used only peripherally, e.g., for parsing configuration files, XML schemas, or general programminglanguage syntax, or as an implementation artifact of a contribution whose primary object of study was not the grammar formalism itself (for example, process discovery algorithms that internally produce process trees without treating the tree grammar as the central formalism were excluded under this criterion); (EC2) the BPM content was limited to a passing motivating example without a substantive technical contribution; or (EC3) the full text was inaccessible through institutional subscriptions or open-access repositories. 3.4. Screening and Selection. After removing 185 duplicates, 341 unique records remained. Title and abstract screening eliminated 252 records that clearly did not satisfy IC1 and IC2, leaving 89 candidates for full-text assessment. Research monographs were included when they constituted original, self-contained research contributions rather than textbooks or edited collections; study #8 (Recker [Rec11]) satisfies this criterion, combining a novel ontological analysis of BPMN with primary qualitative and quantitative data not published elsewhere. Full-text reading resulted in the further exclusion of 57 papers (38 for EC1; 14 for EC2; 5 for EC3), yielding 32 primary studies from the main search. A supplementary backward citation search, conducted after the initial screening and focused on process algebra approaches to BPM (additional query strings: "process algebra" AND "workflow" and ("CSP" OR "pi-calculus") AND "business process"), identified two further primary studies on πcalculus semantics [PW05, LM07] that satisfied all inclusion criteria but had not surfaced in the main database search. These two studies were added, bringing the final corpus to 34

6

M.M. ZEKENG NDADJI

primary studies, as reflected in the PRISMA diagram (Figure 1). Figure 1 summarises the selection process as a PRISMA-style flow diagram [MLT+ 09]. A formal quality assessment of primary studies—rating each study on a checklist of methodological rigour criteria (precision of formal definitions, presence of proofs or empirical evaluation, explicit limitation acknowledgement)—was not conducted for this review. This is a known limitation relative to the Kitchenham & Charters protocol [KC07], which recommends quality scoring to allow differential weighting of evidence. The decision was pragmatic: the 34 primary studies span three decades and seven research streams, each associated with distinct methodological traditions (formal proofs, empirical surveys, case studies, prototype implementations), and this heterogeneity makes a single quality scale difficult to operationalize without introducing additional reviewer bias. Each stream section instead applies a consistent critical template (contributions, limitations, comparative analysis) that provides a qualitative proxy for study quality assessment. Additionally, 12 foundational reference works (standard textbooks, language specifications, and seminal papers on BPM theory or grammar theory that were not primary contributions to the grammar/BPM intersection but were essential as background) were retained as supporting references. These are: [Cho59, Knu68, Roz97, KC07, WW93, vdA96, VDATHKB03, VDATH05, OMG13, DLRMR18, Coa99, STA05]. Records identified through database searching (n = 526)

Added via supplementary backward search (n = 2)

Records after deduplication (n = 341)

Duplicates removed (n = 185)

Records screened at title/abstract level (n = 341)

Excluded at title/abstract (n = 252)

Full-text articles assessed for eligibility (n = 89)

Excluded at full text: EC1: n = 38; EC2: n = 14; EC3: n = 5. Total: n = 57

Primary studies included in the review (n = 34)

Figure 1: PRISMA-style flow diagram of the literature search and selection process.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

7

3.5. Classification. The 34 primary studies were classified into thematic streams using a card-sorting procedure: each study was assigned a descriptive label based on (a) the grammar formalism employed and (b) the principal BPM concern addressed. Labels were then grouped inductively into streams. Streams were distinguished on the basis of formalism family and primary BPM concern rather than cluster size: a cohesive group of studies was classified as an independent stream when its core formalism (whether a Chomsky-hierarchy string class, a graph rewriting system, or a process algebra) was formally and conceptually distinct from those of all other clusters, regardless of the number of studies it contained. Stream VII (2 studies) satisfies this criterion because process algebras constitute a formally separate grammatical paradigm from the string and graph formalisms of Streams I–VI; the small size of this cluster is explicitly reported as a limitation in Challenge C3 (Section 11). Because this classification was performed by a single reviewer, the absence of a second rater and a formal inter-rater reliability measure (e.g., Cohen’s κ) is a known limitation of the present review. To partially mitigate this, the classification was cross-validated against the self-descriptions in each study’s abstract and keywords, and was checked for coherence against the major BPM and formal-methods survey literature. Seven streams emerged from this procedure: (I) process grammars for organizational design; (II) process modeling languages analyzed as grammars; (III) string grammars for process specification and variants; (IV) attribute grammars for workflow specification and execution; (V) graph grammars for process model transformation and analysis; (VI) grammatical inference for process mining; and (VII) process algebras as grammatical frameworks for behavioral specification. One study, Datta [Dat98], was assigned to two streams (I and VI) because it makes independent contributions to both: it applies a grammatical metaphor to process design (Stream I) and introduces grammar-discovery algorithms for automated process model extraction (Stream VI). It is discussed in both sections, with each discussion focusing on the contribution relevant to that stream. This dual assignment does not affect the corpus count: the study is counted once (as primary study #6) in Table 1. Table 1 provides a complete enumeration of all 34 primary studies with their venue type, stream assignment, grammar formalism, and BPM lifecycle phase. Table 2 gives a compact classification overview. Table 3 presents the temporal distribution of the 34 primary studies by stream and five-year period. Three phases of activity are discernible: a formative phase (1994–2004, n = 5) dominated by Stream I process grammars; a growth phase (2005–2014, n = 15) in which Streams II, V, and VII emerged; and a recent diversification phase (2015–2024, n = 14) during which Streams III, IV, and VI became dominant. Streams IV and VI together account for six of the seven studies published in 2020–2024, suggesting that, in the most recent period covered by the corpus, attributed-grammar workflow specification and stochastic grammatical inference may constitute the most dynamically expanding frontiers.

8

M.M. ZEKENG NDADJI

Table 1: Complete list of 34 primary studies included in the review. Venue type: J = journal; C = conference/workshop; B = book; R = technical report. Grammar: PG = process grammar; MG = modeling grammar (ontological); CFG = context-free grammar; CSG = context-sensitive grammar; AG = attribute grammar; GAG = guarded AG; TGG = triple graph grammar; HRG = hyperedge replacement grammar; EGGG = extended edge-based graph grammar; HOT = higher-order graph transformation; PGG = process graph grammar; PCFG = probabilistic CFG; GI = grammatical inference. BPM phase: De = design; Mo = modeling; Ex = execution; Ve = verification; Di = discovery; Mon = monitoring; Tr = model transformation. #

Authors

Year

Type

Stream

Formalism

BPM Phase

1 2 3 4 5 6

Pentland [Pen94] Pentland [Pen95] Pentland & Rueter [PR94] Lee & Pentland [LP03] Lee et al. [LWP08] Datta [Dat98]

1994 1995 1994 2003 2008 1998

R J J R J J

I I I I I I, VI

PG PG PG PG PG PG / GI

De De De De De De, Di

7 Rosemann et al. [RRIG06] 8 Recker [Rec11] 9 Recker et al. [RIRG10] 10 Recker & Rosemann [RR10] 11 Recker et al. [RRGI11] 12 Recker [Rec12] 13 Recker [Rec13]

2006 2011 2010 2010 2011 2012 2013

C B J J J J J

II II II II II II II

MG MG MG MG MG MG MG

Mo Mo Mo Mo Mo Mo Mo

14 15 16 17

Ayari et al. [ABHBA19] Sarno et al. [SAWFA+ 15] Montero et al. [MPRC08] Van der Aa et al. [vdADCLR19]

2019 2015 2008 2019

J J C C

III III III III

CFG CSG Feature NLP

Mo, Ve Mo De Mo

18 Badouel et al. [BHKM14] 19 Badouel et al. [BHK+ 15] 20 Zekeng Ndadji et al. [ZNTTTDP20] 21 Zekeng Ndadji et al. [ZNTTTDP21] 22 Zekeng Ndadji et al. [ZNNMTNTT23] 23 Tchoupe Tchendji et al. [TTZNP24]

2014 2015 2020 2021 2023 2024

R J J J J J

IV IV IV IV IV IV

GAG GAG AG AG AG AG

Ex Ex Mo, Ex Ex Mo Mo, Ex

24 25 26 27 28

Lohmann et al. [LGJS07] Mazanek & Hanus [MH11] Shi et al. [SZZ+ 16] Kräuter et al. [KRKL24] Kataeva & Kalenkova [KK19]

2007 2011 2016 2024 2019

J J J J C

V V V V V

TGG HRG EGGG HOT PGG

Tr Tr Tr, Ve Ve Di

29 30 31

Bergenthum et al. [BDLM07] Breuker et al. [BMDB16] Watanabe et al. [WTIM23]

2007 2016 2023

C J J

VI VI VI

Region/GI Prob. GI PCFG

Di Di, Mon Mon

Continued on next page.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

9

Table 1 continued. #

Authors

Year

Type

Stream

Formalism

BPM Phase

32

Alkhammash et al. [APM24]

2024

C

VI

GI (ALER- Di GIA)

33 34

Puhlmann & Weske [PW05] Lucchi & Mazzara [LM07]

2005 2007

C J

VII VII

π-calc. π-calc.

Mo, Ve Ve

Table 2: Classification overview of the seven research streams. Stream

Grammar type

Representative works

BPM phase

I II III IV V VI VII

Process grammar Modeling grammar CFG / CSG Attribute grammar Graph grammar Gram. inference Process algebra

[Pen95, LWP08, Dat98] [RRIG06, RRGI11, Rec13] [ABHBA19, SAWFA+ 15, vdADCLR19] [BHKM14, ZNTTTDP20, TTZNP24] [LGJS07, MH11, KRKL24] [BDLM07, BMDB16, APM24] [PW05, LM07]

De, Di Mo Mo, De Mo, Ex Tr, Ve Di, Mon Mo, Ve

Table 3: Temporal distribution of the 34 primary studies by research stream and five-year period. Study #6 (Datta [Dat98]), assigned to both Streams I and VI, is counted under Stream I in this table. Period

I

II

III

IV

V

VI

VII

Total

1990–1994 1995–1999 2000–2004 2005–2009 2010–2014 2015–2019 2020–2024

2 2 1 1 0 0 0

0 0 0 1 6 0 0

0 0 0 1 0 3 0

0 0 0 0 1 1 4

0 0 0 1 1 2 1

0 0 0 1 0 1 2

0 0 0 2 0 0 0

2 2 1 7 8 7 7

Total

6

7

4

6

5

4

2

34

3.6. Synthesis. In the following sections (4–10), we describe for each stream: (a) the motivating problem; (b) the specific grammar formalism(s) employed; (c) the principal contributions and limitations of the surveyed works; and (d) a within-stream comparison of approaches where multiple works exist.

10

M.M. ZEKENG NDADJI

4. Stream I: Process Grammars for Organizational Process Design 4.1. The Grammatical Metaphor for Organizational Processes. The systematic application of formal grammar concepts to organizational processes was early explored by Pentland [Pen94, Pen95]. Drawing on Chomsky’s theory of generative grammars and Weick’s earlier suggestion that organizing resembles a grammar, Pentland [Pen95] developed the grammatical metaphor into a rigorous research framework applicable to empirical studies of organizational processes. In Pentland’s model, a process grammar consists of three components: a lexicon of elementary actions (called moves), a set of rewrite rules specifying how moves can be combined, and a set of constraints that restrict the space of admissible combinations. Moves are analogous to words in a natural language: they are the atomic units of observable behavior. Syntactic constituents (groups of moves that form meaningful sub-processes) play a role analogous to phrases in a sentence. A complete process (an observable sequence of events from start to finish) is analogous to a grammatical sentence. This framing offers four key theoretical benefits over alternative approaches to process analysis. First, it provides a compact representation of potentially infinite behavioral variety: a finite grammar generates an infinite set of admissible process trajectories. Second, it captures nesting: just as sentences have hierarchical phrase structure, processes have hierarchical sub-process structure that cannot be captured by flat sequential models. Third, it enables classification: different processes (or different instances of the same process) can be compared in terms of the grammars that generate them. Fourth, it supports design: a grammar can be used generatively to enumerate the space of feasible process alternatives. This foundational work also established that organizational routines can be understood as grammars of action [PR94]: the recurring patterns of organizational behavior arise from a constrained generative process, analogous to the way sentences of a natural language arise from a grammar. 4.2. Process Grammar as a Design Tool. Building on the theoretical foundations of [Pen95], Lee and Pentland [LP03] and subsequently Lee, Wyner, and Pentland [LWP08] developed process grammars into a practical tool for business process design. Lee and Pentland [LP03] argued that existing approaches to process redesign (including benchmarking, incremental variation, brainstorming, and first-principles engineering) are limited because they do not provide a systematic representation of the space of feasible alternative processes. A process grammar, by contrast, makes this space explicit, visible, and searchable, while remaining useful even when the domain representation is incomplete. The authors illustrated the approach with a grammar for the sales process, demonstrating how the grammar can be used to generate and compare alternative process designs in a principled way. Lee, Wyner, and Pentland [LWP08] subsequently operationalized this framework in a paper. They introduced two main artifacts: (1) a grammar-based method for generating and managing business process design alternatives, and (2) a prototype software tool implementing the method. The method decomposes a process design problem into the choice of a lexicon (what activities are available), the definition of grammar rules (how activities can be combined), and the application of domain constraints (which combinations are feasible or desirable). The prototype was demonstrated using a grammar for a sales process, showing how the tool supports designers in exploring the process design space, evaluating alternatives, and making informed choices. 4.3. Grammar-Based Automated Process Discovery. An early contribution to the automation of process model discovery using grammar-like techniques was made by Datta [Dat98], who proposed probabilistic and algorithmic methods for the automatic discovery of AS-IS business process models. Datta’s work drew on grammar discovery algorithms to extract process models from observations of organizational activity, addressing a fundamental practical problem: organizations undertaking Business Process Reengineering (BPR) often lack well-documented models of their existing processes,

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

11

and creating such models manually is expensive and error-prone. The proposed algorithms are among the earliest attempts to bridge formal language theory and the BPM domain in a data-driven manner. 4.4. Comparative Analysis and Limitations. The three threads within Stream I represent distinct orientations that together span the design–discovery axis of BPM. Pentland’s foundational work [Pen94, Pen95] is descriptive: the grammar serves as a theoretical lens for understanding and comparing observed organizational routines, without prescribing or generating specific designs. Lee and Pentland [LP03, LWP08] make the grammar prescriptive: it becomes a tool for generating and evaluating design alternatives, operationalized in prototype software. Datta [Dat98] makes the grammar inductive: the grammar structure is recovered algorithmically from observations of organizational activity, anticipating the process discovery tradition by nearly a decade. Several common limitations apply across Stream I. The process grammar formalism remains at an informal level relative to the Chomsky hierarchy: no formal language-class membership results are established, and the connection to string or tree rewriting is conceptual rather than mathematical. The lexicon of moves must be defined manually by a domain expert, making the approach domain-specific and limiting transferability across organizational contexts. Empirical validation in all three threads relies on small, illustrative case studies; none of the works provides a large-scale evaluation. Finally, Stream I addresses exclusively the design and discovery phases of the BPM lifecycle; enactment, evaluation, and adaptation lie outside its scope. 5. Stream II: Process Modeling Languages as Grammars 5.1. The Ontological Framework for Grammar Evaluation. A distinct and highly productive line of research treats process modeling languages (such as BPMN, EPC, UML Activity Diagrams) as modeling grammars: formal systems consisting of a set of graphical constructs and rules for combining them to express relevant aspects of business processes [RIRG10]. Note that modeling grammar in this stream refers to a representational system in the sense of Wand and Weber (a formal notation judged by which ontological constructs it can express, not by the language it generates) and should be distinguished from the generative sense of Section 2. This perspective, developed primarily by Recker, Rosemann, Indulska, and Green, uses the Bunge-Wand-Weber (BWW) ontological theory [WW93] as a normative benchmark for evaluating the representational adequacy of modeling grammars. The BWW model specifies the ontological constructs that any modeling grammar purporting to model the real world must be capable of representing. A grammar is said to suffer from (1) construct deficit if it lacks constructs for modeling certain ontologically relevant phenomena, (2) construct overload if a single construct maps to multiple ontological concepts, (3) construct redundancy if multiple constructs map to the same concept, or (2) construct excess if a construct maps to no ontological concept at all. Rosemann, Recker, Indulska, and Green [RRIG06] were among the first to apply this framework to a comparative study of process modeling grammars, tracing the evolution of representational capabilities across four decades and several generations of process modeling techniques. Their analysis revealed systematic patterns of improvement but also persistent gaps in the representational power of widely used grammars. 5.2. Empirical Analysis of BPMN as a Modeling Grammar. Recker [Rec11] provided a landmark comprehensive evaluation of BPMN as a process modeling grammar, combining ontological analysis with qualitative interviews and quantitative survey methods. This monograph established a methodological template for rigorous empirical research on the usability and expressiveness of process modeling grammars. Recker, Indulska, Rosemann, and Green [RIRG10] published an empirical investigation of the ontological deficiencies of BPMN in practice. Through semi-structured interviews with practitioners, they identified nine ontological deficiencies in BPMN (including the inadequate capture of business rules and the insufficient support for process decomposition) and five

12

M.M. ZEKENG NDADJI

contextual factors that influence the use of modeling grammars in practice, such as tool support and organizational modeling conventions. Recker and Rosemann [RR10] developed and validated a measurement instrument for studying user acceptance of process modeling grammars, advancing the empirical research agenda in this area. Recker, Rosemann, Green, and Indulska [RRGI11] subsequently used this instrument in a large-scale survey of 528 practitioners, demonstrating empirically that ontological deficiencies perceived by users negatively affect their beliefs about the usefulness and ease of use of process modeling grammars—a result that validates the BWW-based theoretical framework. Further studies examined the role of specific grammatical constructs. Recker [Rec12] showed that five features of modeling tools significantly affect users’ beliefs about the grammar they work with, demonstrating that grammar usage cannot be studied in isolation from the tool environment. Recker [Rec13] conducted a controlled experiment examining the usefulness of Gateway constructs (the constructs in BPMN used to express control-flow divergence and convergence), finding that Gateway constructs improve the interpretability of process models through a perceptual discriminability effect, particularly for complex models. 5.3. Comparative Analysis and Limitations. The seven studies in Stream II form a coherent methodological arc rather than a collection of independent investigations. Rosemann et al. [RRIG06] established the BWW benchmark and applied it in a comparative historical analysis of multiple modeling grammars. Recker [Rec11] deepened this into a comprehensive evaluation of a single grammar (BPMN), integrating ontological analysis with qualitative and quantitative data. Recker et al. [RIRG10] and Recker and Rosemann [RR10] developed and validated the measurement infrastructure required for large-scale survey research. Recker et al. [RRGI11] then deployed this infrastructure in a survey of 528 practitioners. Finally, Recker [Rec12, Rec13] used controlled experiments to identify the specific grammatical constructs and tool features that drive practitioner perception. This progression reflects three systematic shifts: from multiple grammars to a single grammar (BPMN); from descriptive analysis (which deficiencies exist) to explanatory and predictive claims (why they matter and what constructs drive usability); and from theoretical comparison to surveys to controlled experiments. The stream’s contribution is thus not only substantive but also methodological, demonstrating a replicable template for the empirical evaluation of process modeling grammars. It should be noted that all seven studies in this stream were conducted by the same research group (Recker, Rosemann, Indulska, Green, and collaborators); Stream II therefore reflects the depth and sustained productivity of a single research program rather than a broad community of independent contributors. This homogeneity limits the generalizability of the stream’s findings but does not diminish their internal coherence or empirical quality.

6. Stream III: Production-Rule Grammars for Process Structural Specification and Variant Management 6.1. Unifying Theme: Grammatical Validity of Process Structures. The four works in this stream address a shared fundamental problem: delimiting the space of structurally valid process specifications. They employ production-rule-based (generative or parsing) mechanisms to answer the question, “What constitutes an admissible process structure?”, where admissibility is determined by the grammar. This distinguishes Stream III from the other streams: Stream IV addresses execution, integrating data and roles via attribute grammars; Stream V addresses model transformation, using graph rewriting to change representations; Stream VI addresses discovery, inferring models from observations; and Stream VII addresses behavioral semantics, using process algebras to define bisimulation equivalence. In contrast, Stream III is concerned with structural syntax: the grammar defines which structural compositions of process activities or models are permitted, irrespective of their behavioral properties.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

13

The four works span a spectrum of grammatical mechanisms. Ayari et al. [ABHBA19] use a context-free grammar to define the refinement hierarchy of BPMN models. Sarno et al. [SAWFA+ 15] use a context-sensitive grammar to enforce contextual constraints on process variant compositions. Montero et al. [MPRC08] use a feature-grammar mapping (a systematic production-rule mapping between feature constructs and process constructs) to derive process structures from variability models. Van der Aa et al. [vdADCLR19] use a grammar-based NLP parser to identify valid declarative constraint structures in natural language process descriptions. Taken together, these four works show that production-rule grammars, at all levels of the Chomsky hierarchy, have a natural role in process structural specification.

6.2. Context-Free Grammars for BPMN Structural Specification. Ayari, Bendali Hlaoui, and Ben Ayed [ABHBA19] proposed using context-free grammars to provide a formal structural specification of BPMN models at each level of abstraction in a stepwise refinement framework. Each non-terminal of the grammar corresponds to a composite BPMN construct, while each terminal represents an atomic BPMN element. A derivation step in the grammar corresponds to a refinement step in the process model, in which an abstract subprocess is replaced by a more detailed sub-process, making CFG derivation trees a natural representation of the refinement hierarchy. A key contribution of this work is the integration of the grammatical specification with formal model checking: for each refinement step, the change impact on the process semantics is analyzed automatically using the NuSMV model checker, based on a Kripke structure that models the dependency relationships (data dependencies and control-flow dependencies) between activities. The approach thus provides both syntactic structure (via the CFG) and semantic verification (via model checking), addressing one of the persistent weaknesses of informal BPMN specifications.

6.3. Context-Sensitive Grammars for Process Variant Composition. Sarno et al. [SAWFA+ 15] addressed the problem of composing business process model variants using contextsensitive grammars (CSGs). Variant management is a practically important challenge: organizations must maintain multiple variants of a core process to accommodate regulations, client requirements, or organizational contexts without introducing errors or redundancy. The CSG approach provides a set of affirm production rules that govern the composition of variants: only combinations of process fragments that are explicitly permitted by the grammar are considered valid variant compositions. The contextual sensitivity of the grammar allows the applicability of a production rule to depend on the surrounding context of the process fragment being replaced, enforcing inter-fragment constraints that cannot be expressed by a context-free grammar. A case study from naval architecture (a domain with complex process variants determined by regulatory requirements) was used to validate the approach.

6.4. Feature Grammars for Grammar-Based Process Families. Montero, Peña, and RuizCortés [MPRC08] addressed the problem of deriving business processes from feature models in the context of Process Family Engineering (PFE). PFE applies Software Product Line concepts to variant-rich Business Information Systems: variability is first captured using a feature model, and the business process is then derived from the feature model. The key technical contribution is a systematic production-rule mapping between feature model constructs and business process constructs—a grammar-like formalism in which each feature combination generates a corresponding process structure. This mapping was implemented as a Model-Driven Development (MDD) transformation, enabling the automatic derivation of the process structure from a feature model specification and eliminating the previously manual, error-prone derivation step.

14

M.M. ZEKENG NDADJI

6.5. Grammar-Based Parsing for Declarative Process Extraction from Text. Van der Aa, Di Ciccio, Leopold, and Reijers [vdADCLR19] addressed the problem of automatically extracting declarative process models from natural language textual descriptions—a problem distinct from, and harder than, imperative process model extraction, since declarative models specify permitted or forbidden behaviors as constraints rather than as a fixed control flow. The authors developed tailored Natural Language Processing techniques that parse textual constraint descriptions using a dependency grammar to identify process activities and their inter-relations, treating the extraction problem as a grammar-based parsing task in which each admissible constraint pattern corresponds to a grammatical construct. A quantitative evaluation showed that the approach generates constraints closely resembling those established by human experts. 6.6. Comparative Analysis and Limitations. The four works in Stream III are united by their use of production rules to constrain the space of valid process structures, but they differ along three dimensions. First, expressive power: Ayari et al. operate at the context-free level, Sarno et al. at the context-sensitive level, Montero et al. with a feature grammar, and Van der Aa et al. with a dependency grammar for NLP. Second, direction of use: Ayari, Sarno, and Montero use their grammars generatively (to produce valid structures), while Van der Aa et al. use theirs analytically (to parse and classify structures from text). Third, target structure: Ayari and Sarno target the internal structure of BPMN process models; Montero targets the derivation of process models from feature variability spaces; Van der Aa et al. target the extraction of process constraints from natural language. A common limitation of these works is the focus on structural validity at the expense of behavioral properties. None of the four works provides a mechanism for checking properties such as deadlock-freedom or soundness—those concerns are handled by the formalisms of Streams V and VII. 7. Stream IV: Attribute Grammars for Workflow Specification and Execution The works in Stream IV are united by a shared motivating problem: the inadequacy of traditional workflow formalisms in handling the joint specification of control flow, data, and organizational roles within a single formal object. Petri nets and automata models capture control flow faithfully but treat data and actors as external annotations; conversely, data-centric models lack formal control-flow guarantees. Attribute grammars provide a natural unifying mechanism: the structural component of the grammar specifies control flow, while the attribute apparatus integrates data, actor rights, and execution context within the same formal framework. The two sub-frameworks surveyed here (GAG and LSAWfP) both exploit this idea, differing in their level of abstraction, expressiveness, and execution model. Disclosure. Four of the six primary studies in this stream ([ZNTTTDP20, ZNTTTDP21, ZNNMTNTT23, TTZNP24]) are co-authored by the present author. These works were included because they satisfy all inclusion criteria established a priori in Section 3: they employ attribute grammars as the central formalism, appear in peer-reviewed venues, and address workflow specification and execution as the primary concern. The same critical standards are applied to all six works in the synthesis below. 7.1. Guarded Attribute Grammars for Distributed Case Management. Badouel, Hélouët, Kouamou, and Morvan [BHKM14, BHK+ 15] introduced the Guarded Attribute Grammar (GAG) formalism as a declarative foundation for artifact-centric collaborative systems. Their work starts from a fundamental criticism of traditional workflow formalisms: while Petri nets, automata, and statechart-based models are well-suited to orchestrating fixed production processes, they are too rigid for open, data-centric collaborative environments where the structure of a case depends on the data it contains and on the decisions made by human stakeholders. A GAG extends a context-free grammar in two ways. First, semantic rules are added to each production, specifying both how nodes of the

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

15

derivation tree may be further expanded (the structural evolution of the process, governed by guard conditions) and how the values of synthesized and inherited attributes at each node are computed from contextual information. Second, individual users (stakeholders) are associated with specific non-terminals, so that the right to expand a node belongs exclusively to its designated owner. In the execution model introduced in [BHK+ 15], each user’s active workspace is an attributed derivation tree (called a map) that visualizes and organizes the tasks in which the user is involved, together with the data relevant to those tasks. Users communicate through asynchronous message passing, without shared memory, enabling fully decentralized execution on an asynchronous distributed architecture. A disease surveillance case study demonstrated the expressiveness and practical applicability of the approach. The GAG framework has two principal limitations, however. First, the formal complexity of the guard conditions makes the specification of even moderately complex processes verbose and difficult to maintain. Second, no algorithmic analysis of properties such as soundness or deadlock-freedom is provided within the framework itself; verification must be handled externally.

7.2. The LSAWfP Language Family. The central modeling artifact of the Language for the Specification of Administrative Workflow Processes (LSAWfP) [ZNTTTDP20] is the Grammatical Model of Workflow (GMWf), a context-free grammar (extended with attribute mechanisms) in which non-terminals represent abstract activities or sub-processes and terminals represent elementary tasks. The grammar’s rules specify the possible decompositions of each activity into sub-activities, while attributes capture the permissions of each actor (read, write, execute) on each task, as well as the data flowing between tasks. A key distinguishing feature of LSAWfP is the use of scenarios as the modeling unit: each derivation tree of the GMWf corresponds to a possible execution scenario of the process, making the modeling framework inherently scenario-based and modular. Views allow each actor to have a partial, confidential perception of the process state, addressing a concern that is often neglected in existing workflow languages. Zekeng Ndadji et al. [ZNTTTDP21] extended LSAWfP with a framework for the completely decentralized execution of administrative processes. The execution model treats the running of a process as the cooperative editing of a mobile artifact (a structured document represented as an annotated derivation tree) that circulates from actor to actor. Three projection algorithms were introduced and proved stable under composition. In [ZNNMTNTT23], Zekeng Ndadji et al. subsequently studied the expressiveness of LSAWfP from a formal language-theoretic perspective, proving that any non-recursive LSAWfP model (i.e., any GMWf whose grammar contains no recursion) corresponds to a structured workflow. Since the majority of commercial BPM systems only implement structured workflows, this result establishes the commercial potential of the language. The proof exploits a connection between structured workflows and the Dyck language, offering an elegant formal characterization. Tchoupe Tchendji, Zekeng Ndadji, and Parigot [TTZNP24] synthesized this line of research into a complete framework for the grammatical design and distributed execution of administrative workflows, using structured and cooperatively edited mobile artifacts. The framework is distinguished by solid mathematical foundations, its topicality (use of artifact-centric choreography, partial replication, and accreditation), and the availability of a prototype implementation for proof of concept. The LSAWfP family has several limitations that should be acknowledged. The formal language-theoretic results (e.g., the characterization of non-recursive models as structured workflows [ZNNMTNTT23]) hold only for the restricted, non-recursive fragment of the language. The prototype implementations are proofs of concept rather than industrial tools, and scalability to large processes has not been evaluated. Furthermore, the verification of behavioral properties (soundness, deadlock-freedom) relies on the structured-workflow restriction rather than on a general decision procedure, limiting applicability to unrestricted process models.

16

M.M. ZEKENG NDADJI

7.3. Comparative Analysis of the Two Sub-frameworks. The GAG framework and the LSAWfP family address the same fundamental problem (the integrated specification and decentralized execution of data-intensive workflows) but through architecturally different choices. GAG prioritizes generality: the guarded attribute grammar formalism can express a wide class of collaborative processes, including highly dynamic, data-dependent ones. The framework has strong theoretical foundations in the formal semantics of attribute grammars, and its notion of user workspace provides an explicit model of individual stakeholder activity. Its main weakness is the lack of a high-level specification language: users must work directly with grammar productions and attribute equations. LSAWfP prioritizes usability and formalization: the language provides a higher-level modeling notation (workflow scenarios with explicitly declared actor permissions) while retaining formal executability. The formal language-theoretic results (expressive completeness for structured workflows, stability of projection algorithms) provide a solid theoretical basis. The main weakness is the restriction to administrative (structured) workflows and the absence of general verification procedures. Both frameworks leave tool maturity and scalability as open issues, and neither has been deployed in an industrial setting. A productive direction for future work would be to integrate the two: use the high-level LSAWfP notation as a front-end for GAG-based execution, while leveraging the guard mechanism of GAG to handle the dynamic cases that LSAWfP currently cannot express. 8. Stream V: Graph Grammars for Process Model Transformation and Analysis The motivating problem for Stream V is the graph-structured nature of standard process modeling notations: in BPMN, BPEL, UML Activity Diagrams, and workflow nets, activities are nodes and control or data flows are edges. Graph grammars which rewrite graphs through production rules, are therefore a natural formal tool for specifying the syntax of these notations, transforming models between them, analyzing their structural properties, and providing formal operational semantics. The five works in this stream use graph grammars in three distinct modes: transformative (Lohmann et al., Mazanek and Hanus, Shi et al.), generative (Kataeva and Kalenkova), and semantic (Kräuter et al.). 8.1. Triple Graph Grammars for Workflow Transformation. Lohmann, Greenyer, Jiang, and Systä [LGJS07] addressed the problem of transforming high-level workflow models into executable business process specifications using Triple Graph Grammars (TGGs). TGGs, a specialization of graph grammars, consist of rules that define correspondences between elements of a source graph, a target graph, and a correspondence graph that tracks the relationships between them. This declarative, bidirectional formulation of transformation rules makes TGGs particularly appropriate for expressing correspondences between workflow patterns that recur in different modeling languages. Lohmann et al. demonstrated a transformation from UML Activity Diagrams to BPEL and XPDL, using the workflow patterns catalogue [VDATHKB03] as a structured vocabulary for designing the transformation rules. Each workflow pattern (Sequential, Parallel Split, Synchronization, Exclusive Choice, etc.) was expressed as a TGG rule, ensuring that the fundamental behavioral semantics shared by the source and target languages are correctly preserved. The approach is modular: new patterns (and thus new language constructs) can be added by adding new TGG rules. 8.2. Hyperedge Replacement Grammars for BPMN/BPEL Bidirectional Transformation. Mazanek and Hanus [MH11] proposed using hyperedge replacement grammars (HRGs) to specify the abstract syntax of structured BPMN models, and showed how this specification can be used to construct a bidirectional transformation between BPMN and BPEL. HRGs rewrite hypergraphs (generalized graphs in which edges may connect more than two nodes) by replacing hyperedges with sub-hypergraphs according to production rules. This formalism captures the block-structured nature of BPMN (in which complex subprocesses are nested within enclosing activities) in a particularly

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

17

natural way. The implementation exploited the Grappa framework of functional logic graph parser combinators, implemented in the functional logic programming language Curry. A key feature of this approach is that, since the parser is implemented as a function in a functional logic language, it can be evaluated in both directions: given a BPMN model, it produces the corresponding BPEL specification; given a BPEL specification, it produces the corresponding BPMN model. Additionally, because the grammar can be used both for parsing and for generation, the same parser supports model completion—given a partial model, it can enumerate the completions consistent with the grammar.

8.3. Extended Edge-Based Graph Grammars for BPMN Analysis. Shi, Zeng, Zhang, and collaborators [SZZ+ 16] introduced the Extension of Edge-based Graph Grammar (E-EGG), a new context-sensitive graph grammar formalism designed to address bidirectional transformation between BPMN and BPEL more conveniently than previous approaches. Compared to earlier graph grammar formalisms, E-EGG introduces new mechanisms in grammatical specifications, productions, and operations that enable it to handle the full range of BPMN constructs encountered in practice, including advanced gateway types and exception-handling constructs. In addition to the transformation rules, the authors proposed a parsing algorithm for E-EGG that can be used to check the structural correctness of BPMN models (e.g., detecting improperly nested gateways), providing a formal, tool-supported quality assurance mechanism for process models.

8.4. Graph Grammar-Based Generation of Process Model Benchmarks. Kataeva and Kalenkova [KK19] addressed a practical obstacle in process mining research: the shortage of realworld process models and event logs that can be used to benchmark discovery and conformance checking algorithms. Their use of graph grammars is generative: grammar rules define the legal compositions of workflow net primitives (places, transitions, arcs), and the derivation of a grammar term produces a structurally valid workflow net together with a synthetic event log that is, by construction, perfectly consistent with the model. This approach enables systematic generation of benchmark datasets with controlled structural properties (complexity, depth, branching factor) supporting rigorous, repeatable evaluation of process mining algorithms. The work is thus situated at the interface of Streams V and VI, using graph grammars as a generative tool in service of process discovery research. Its classification within Stream V reflects the primary object of study: the graph grammar formalism used to generate structurally valid workflow nets, rather than the process discovery or conformance algorithms that consume the resulting benchmarks.

8.5. Higher-Order Graph Transformation for BPMN Operational Semantics. Kräuter, Rutle, König, and Lamo [KRKL24] use graph transformation in a fundamentally different mode: not generatively but analytically, to give a formal operational semantics to an existing modeling notation (BPMN). Rather than manually encoding BPMN execution rules as individual graph rewriting rules, their approach defines a transformation of transformations—a higher-order operation that takes a BPMN model as input and produces a graph transformation system whose execution faithfully models the token-passing semantics of the BPMN model. This approach covers nearly all BPMN elements used in practice and supports formal verification of behavioral properties: Safeness (no token duplication) and Soundness (correct termination), enabling automated detection of control-flow errors such as deadlocks and dead activities. The approach was implemented as an open-source web-based tool, and is the only work in this stream to have produced a publicly available, practitioner-facing artifact.

18

M.M. ZEKENG NDADJI

8.6. Comparative Analysis and Limitations. The five works differ both in formalism and in purpose. Lohmann et al. [LGJS07] use Triple Graph Grammars for bidirectional transformation from UML Activity Diagrams to executable workflow languages, prioritizing pattern-level compositionality. Mazanek and Hanus [MH11] exploit the functional logic duality of Hyperedge Replacement Grammars to obtain reversible parsing between BPMN and BPEL. Shi et al. [SZZ+ 16] extend the graph grammar paradigm with a context-sensitive formalism (E-EGG) capable of handling a wider range of BPMN gateway types, trading expressiveness for increased rule complexity. Kataeva and Kalenkova [KK19] depart from the transformation paradigm: their grammar is generative, producing synthetic workflow nets as benchmarking artifacts rather than process models for deployment. Kräuter et al. [KRKL24] apply higher-order transformation to derive a formal operational semantics from a BPMN model, enabling automated verification of Safeness and Soundness. A common limitation across all five works is that they address subsets of the relevant notation: TGG covers structured workflow patterns; HRG covers block-structured BPMN; E-EGG extends coverage but does not claim completeness; PGG targets workflow nets; and HOT covers “nearly all” BPMN elements without a formal completeness proof. No uniform graph-grammar framework covering the full BPMN 2.0 standard with formal verification guarantees exists, and tool maturity outside Kräuter et al.’s open-source implementation remains at the prototype level.

9. Stream VI: Grammatical Inference for Process Mining 9.1. Language-Theoretic Foundations for Process Mining. The connection between formal language theory and process mining was articulated early in the BPM literature. Datta [Dat98], in his work on the automated discovery of AS-IS process models, explicitly drew on grammar discovery algorithms from formal language theory, treating the observable process traces as the language of the underlying process grammar. This framing (event logs as samples of the language generated by a process grammar) provides a principled theoretical foundation for process discovery. Bergenthum, Desel, Lorenz, and Mauser [BDLM07] developed this language-theoretic perspective into a concrete process mining algorithm. Their approach treats an event log as defining a formal language (the set of observed traces), and applies region theory to construct a Petri net whose language includes the observed traces and satisfies minimality conditions. Region theory, rooted in the theory of formal languages, provides conditions under which a language can be recognized by a Petri net, and algorithms for constructing the minimal such net. This work established a rigorous connection between the language-theoretic properties of event logs and the structural properties of discovered process models. 9.2. Grammar-Based Predictive Process Modeling. Breuker et al. [BMDB16] proposed a predictive process modeling technique for BPM grounded in grammatical inference. The key insight of their work is that existing process discovery algorithms such as the Alpha miner [vdAtHW03] and the Inductive Miner [LFvdA13], impose strong language biases: constraints on the class of languages (and hence process models) they can produce that limit their predictive accuracy. By replacing these biased discovery algorithms with a probabilistic grammatical inference approach, the authors obtained a predictive technique with weaker and more flexible biases. The approach fits a probabilistic model to a dataset of past process execution traces, and uses the model to predict the future behavior of currently running process instances. Applications include early warning systems (predicting the likelihood of service level agreement violations) and anomaly detection (flagging process instances whose behavior is inconsistent with historical patterns). The resulting models are both accurate and comprehensible, thanks to a visualization technique that renders the inferred probabilistic grammar as a graphical process model.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

19

9.3. Probabilistic Grammar Models for Conformance Checking. Watanabe, Takahashi, Ikeuchi, and Matsuda [WTIM23] proposed the Probabilistic Generative Process Model (PGPM), a process model representation based on probabilistic context-free grammars (PCFGs). The key problem they addressed is that of probabilistic conformance checking: assessing how well a probabilistic process model fits an event log, taking into account not only which traces are observed but also their relative frequencies. In their formulation, a process tree (a standard hierarchical process model representation) is converted into a set of PCFG production rules; each rule is annotated with a probability representing the likelihood of the corresponding structural choice. This PCFG representation enables the trace probability of any trace to be computed exactly and efficiently using dynamic programming, addressing a key obstacle in probabilistic conformance checking. An Expectation-Maximization algorithm is used to estimate the probability parameters from an event log, converging to parameters that locally maximize the likelihood. 9.4. Stochastic Grammar Inference for Process Discovery. Alkhammash, Polyvyanyy, and Moffat [APM24] proposed a process discovery approach grounded in stochastic grammar inference. Their approach targets the construction from event logs, of Stochastic Directed Action Graphs (SDAGs)—a type of Directly-Follows Graph (DFG) annotated with probabilities that define a stochastic language over execution traces. The inference is performed using ALERGIA, a classical grammatical inference algorithm that identifies any stochastic regular language from a sample of positive examples in the limit with probability one. The discovered SDAG encodes a stochastic language over process traces, enabling trace frequency reasoning and process simulation. A key contribution is a genetic algorithm that evolves the inference parameters of ALERGIA to discover SDAGs of superior quality; they are smaller and more accurate than the DFGs produced by the Inductive Miner [LFvdA13] and other state-of-the-art DFG-based discovery techniques. An evaluation over real-world event logs confirms the superiority of the approach in terms of model size and representational fidelity. 9.5. Comparative Analysis and Limitations. The four works differ in language class, direction of inference, and BPM concern. Bergenthum et al. [BDLM07] apply region theory to derive Petri nets from event logs, providing the strongest formal guarantees (exact language inclusion) at the cost of exponential worst-case complexity. Breuker et al. [BMDB16] target predictive monitoring (the only work in the stream oriented toward predicting future trace behavior rather than reconstructing a past model). Watanabe et al. [WTIM23] address conformance checking using probabilistic contextfree grammars, and are the only contributors to use a context-free language class, enabling exact trace-probability computation via dynamic programming. Alkhammash et al. [APM24] combine ALERGIA with a genetic algorithm to optimize stochastic regular grammar inference, and are the only contributors to benchmark against public real-world event log repositories. Common limitations span the entire stream. All four works assume clean, complete event logs; none provides formal handling of noise, missing events, or concept drift—a fundamental gap given the realities of industrial process data. The relationship between the inferred grammar’s language class and the process model’s structural properties (soundness, deadlock-freedom) is not formally addressed by any work in the stream. Datta’s contribution [Dat98], while pioneering, predates the process-mining field and cannot be evaluated against contemporary benchmarks. 10. Stream VII: Process Algebras as Grammatical Frameworks for Behavioral Specification and Verification 10.1. Foundational Connections Between Process Algebras and Formal Grammars. Process algebras emerged in the 1980s as a family of mathematical formalisms for reasoning about the behavior of concurrent, communicating systems. Their relationship to formal grammars is both deep

20

M.M. ZEKENG NDADJI

and formally established. At the syntactic level, the terms of a process algebra are constructed by an inductive grammar whose non-terminals correspond to the operators of the algebra and whose terminals are the primitive actions. At the semantic level, the structural operational semantics of a process algebra defines how each production of this grammar generates a set of transitions, making the operational semantics itself a form of attribute grammar over the term grammar. At the languagetheoretic level, the set of traces that a process algebra term can exhibit forms a formal language, and the decision problems of process algebra (bisimulation equivalence, model checking) are closely related to language equivalence and membership problems in formal language theory. The principal process algebras that have been brought to bear on BPM are Hoare’s Communicating Sequential Processes (CSP) [Hoa85], Milner’s Calculus of Communicating Systems (CCS) [Mil89], and Milner, Parrow, and Walker’s π-calculus [MPW92]. CSP is characterized by a rich set of process-combination operators (sequential composition, parallel composition, external and internal choice, hiding) and a denotational semantics based on the failures-divergences model. CCS provides a minimal calculus built on the action prefixing operator and synchronization-based parallel composition, and is the primary vehicle for introducing bisimulation equivalence. The π-calculus extends CCS with name mobility: communication channels can themselves be sent as messages, enabling the modeling of dynamically evolving communication topologies. This mobility is essential for capturing the dynamic assignment of tasks in modern, service-oriented business processes. 10.2. The π-Calculus for Formalizing Workflow Patterns. The most direct application of process algebra to BPM is the formalization of workflow patterns using the π-calculus, carried out by Puhlmann and Weske [PW05]. The workflow patterns of van der Aalst et al. [VDATHKB03] constitute a comprehensive catalog of control-flow constructs that appear in industrial workflow management systems. They include patterns for basic control flow (sequence, parallel split, synchronization, exclusive choice, simple merge), advanced branching and synchronization (multi-choice, synchronizing merge, discriminator), iteration (arbitrary cycles, implicit termination), and cancellation and termination. At the time of Puhlmann and Weske’s work, the formal semantics of these patterns had not been rigorously specified, making precise comparison between workflow languages difficult. Puhlmann and Weske addressed this gap by providing π-calculus encodings for all 20 workflow patterns in the original catalog. The π-calculus was chosen for its name-mobility feature, which is required to model the dynamic routing of tokens (the flow of control) to multiple possible successors—a fundamental requirement for the multi-choice and synchronizing merge patterns. Each pattern is encoded as a π-calculus process: activities are agents that communicate on shared channels, and the routing logic of the pattern is expressed as a composition of π-calculus terms. The resulting formal semantics can be used to check whether two apparently different workflow language constructs implement the same behavioral pattern (via bisimulation equivalence) or whether a given workflow implementation correctly realizes an intended pattern. This contribution established the π-calculus as a reference semantic framework for workflow pattern analysis. 10.3. π-Calculus Semantics for Service-Oriented Business Processes. A second primary contribution in this stream is the work of Lucchi and Mazzara [LM07], who provided a formal πcalculus semantics for WS-BPEL (Web Services Business Process Execution Language), the dominant industrial language for orchestrating service-oriented business processes. WS-BPEL is a complex XML-based language with a large set of control-flow constructs, data handling mechanisms, event handling, fault handling, and compensation primitives; its informal specification, despite being detailed, admitted multiple interpretations. Lucchi and Mazzara’s contribution was to provide a systematic translation of WS-BPEL into the π-calculus, covering the principal control-flow and communication constructs of the language. The translation is compositional: the π-calculus semantics of a WS-BPEL program is assembled from the semantics of its constituent activities according to the structure of the program, exactly as the value of an attributed term is computed from the

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

21

attributes of its children in an attribute grammar. This semantic framework enabled formal analysis of WS-BPEL programs: the π-calculus encoding can be verified against behavioral specifications using bisimulation equivalence, and existing π-calculus model checkers can be applied to check properties such as deadlock-freedom and conformance to service interface contracts. The work also revealed ambiguities in the informal WS-BPEL specification, providing concrete feedback to the standards process—a concrete demonstration of the practical value of formal semantics. 10.4. Position in the Grammatical Landscape of BPM. The two primary studies in Stream VII are complementary in scope. Puhlmann and Weske [PW05] operate at the pattern level, establishing π-calculus encodings for all 20 workflow patterns of the van der Aalst catalog; their contribution is an abstract semantic reference applicable to any workflow system, independent of any specific notation. Lucchi and Mazzara [LM07] operate at the language level, providing a compositional semantics for a specific industrial notation (WS-BPEL); their contribution enables formal reasoning about individual programs in a deployed standard. The two works are thus complementary: the former provides semantic primitives, the latter assembles them into a full language semantics. Both studies share common limitations. The π-calculus encodings are manually crafted and language-specific; no systematic or automated method for deriving π-calculus semantics from arbitrary workflow specifications is provided. Coverage within Stream VII is narrow: only two primary studies qualify, both using the π-calculus; CSP and CCS are invoked as background references but are not represented by primary BPM contributions. Finally, since the full π-calculus is Turing-complete, many behavioral properties of interest are undecidable in general; both works rely on structural restrictions or bounded fragments for tractable analysis. Stream VII occupies a distinct position in the grammatical landscape of BPM. Unlike Streams I– IV, which use grammars primarily as generative or specification tools (to describe what a valid process looks like), Stream VII uses the grammar structure of process algebra terms as a basis for compositional behavioral semantics: the grammar defines not only the structure of process terms but also the behavioral meaning of each structural combination. Unlike Stream V, which focuses on the transformation of process model representations, Stream VII focuses on the behavioral equivalence and verification of process implementations. And unlike Stream VI, which is concerned with discovering a process model from observations, Stream VII is concerned with proving that a given implementation satisfies a given behavioral specification. Future work connecting Stream VII to the other streams would be particularly valuable. Specifically: (a) connecting the π-calculus semantics of workflow patterns to the attribute grammar-based process specifications of Stream IV, to obtain both an executable and a verifiable formal model; (b) using the trace semantics of process-algebraic models as the target language for grammatical inference in Stream VI, to ground process discovery in a well-defined semantic framework; and (c) investigating whether the graph grammar models of Stream V can be compiled into process-algebraic encodings, providing a connection between structural and behavioral analysis. 11. Discussion 11.1. Cross-Cutting Synthesis. Taken together, the seven streams reviewed in this paper demonstrate that formal grammars have influenced BPM at every phase of the process lifecycle, from the high-level organizational design of processes (Stream I) through formal process modeling and evaluation (Streams II and III), workflow specification and execution (Stream IV), model transformation and verification (Stream V), data-driven process discovery and monitoring (Stream VI), to compositional behavioral specification and formal verification (Stream VII). A first cross-cutting observation is the complementarity of grammatical formalisms with respect to BPM concerns. Regular and context-free string grammars provide natural representations of sequential and hierarchically structured control flows. Context-sensitive grammars add the ability

22

M.M. ZEKENG NDADJI

to express dependencies between non-adjacent parts of a process, relevant for capturing complex inter-activity constraints in variant management. Attribute grammars add a data-computation layer that is essential for integrating the informational model of processes with their behavioral model. Graph grammars match the graph-based nature of standard process modeling notations, enabling rigorous transformation and semantic analysis. Process algebras provide a term grammar with associated compositional operational semantics, enabling behavioral specification and bisimulationbased verification. Stochastic extensions of all these formalisms support the quantitative, data-driven analysis required in process mining. A second cross-cutting observation is the tension between expressiveness and tractability. The Chomsky hierarchy establishes that higher expressiveness comes at the cost of higher computational complexity. In BPM, this tension is well-known: the full expressive power of BPMN makes soundness checking undecidable [vdA96], while restricting to structured workflows ensures decidable analysis but sacrifices expressive power [KTHVDA03]. Grammatical approaches address this tension explicitly: the class of languages generated by a grammar directly determines the computational properties of the corresponding processes, enabling designers to make principled trade-offs. Stream VII makes this connection explicit at the semantic level: finite-state CCS/CSP processes have regular trace languages, while the name-mobility of the π-calculus enables non-regular behaviors, situating process algebras squarely within the Chomsky hierarchy framework. A third cross-cutting observation concerns the treatment of data, roles, and control flow. Traditional workflow languages, and many grammatical approaches in Streams I, II, and V, focus primarily on control flow, treating data and organizational roles as secondary concerns. The attribute grammar-based approaches in Stream IV represent a significant advance in this regard: by attaching data and role information as attributes to grammar symbols, they achieve a unified, formally grounded treatment of all three dimensions within a single framework. A fourth observation is the evolution from prescription to data-driven modeling. Streams I through VII are predominantly prescriptive: grammars are used to specify what processes should look like or how they should behave. Stream VI reverses this direction, using grammatical inference to discover process models from empirical execution data. The logical next step is to integrate both directions: use prescriptive grammar-based models as structural priors for grammar induction, and use inference to refine and adapt those models as process data accumulates.

11.2. Open Challenges and Future Research Directions. Despite the richness and diversity of the reviewed literature, several significant research gaps emerge directly from the evidence of the corpus. C1 — Towards a unified grammatical theory of BPM. Evidence from the corpus. The seven streams have developed largely in parallel. Stream I provides no formal data-flow semantics; Stream IV provides attribute-grammar data-flow but no organizationallevel design vocabulary; Stream VI operates on event logs without structural priors from Streams I–V. Notably, none of the 34 primary studies cites a work from more than two streams, confirming the absence of cross-stream synthesis. Research questions. (a) What is the formal language class characterization of each of the 20 workflow patterns of [VDATHKB03]? (b) Under what conditions can a GAG specification [BHK+ 15] be compiled into a graph transformation system amenable to model checking by the GROOVE tool [Ren04]? (c) What is the sample complexity of inferring a GMWf-class attribute grammar from a finite event log? Adjacent tools. Attribute grammar evaluation systems (JastAdd [EH07]) and hypergraph rewriting frameworks (AGG, GROOVE [Ren04]) provide partial infrastructure for such integration. C2 — Formal verification of grammatical process models.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

23

Evidence from the corpus. Among the six Stream IV works, none provides a decision procedure for soundness or deadlock-freedom in the general (recursive) case; correctness results are restricted to non-recursive, structured workflows [ZNNMTNTT23]. In Stream III, Ayari et al. [ABHBA19] couple a CFG specification with NuSMV model checking, but only for bounded refinement hierarchies. The only work in the entire corpus that provides a general, tool-supported verification procedure is Kräuter et al. [KRKL24] in Stream V. Research questions. (a) Is it possible to compile a GMWf [ZNTTTDP20] into a Petri net amenable to existing soundness checkers (WofBPEL, LoLA)? (b) Can the higher-order graph transformation approach of [KRKL24] be extended to verify liveness properties of attributed process models? Adjacent tools. The LoLA Petri net model checker, WofBPEL, and the CPN Tools platform for colored Petri nets all support behavioral verification and are compatible with graph-transformation-based BPM formalizations. C3 — Integrating process algebraic and grammatical semantics. Evidence from the corpus. Stream VII covers only two primary studies, both using the π-calculus exclusively. No primary study in the corpus connects a process-algebraic encoding to an attribute grammar specification or a graph grammar transformation. Puhlmann and Weske [PW05] note that their π-calculus encodings of workflow patterns are compositional but provide no formal connection to the grammars that generate those patterns structurally. Research questions. (a) Can a bisimulation equivalence result be proved between the π-calculus encoding of a workflow pattern and the language generated by its GMWf grammar? (b) Which subclass of π-calculus processes has a trace language that is a context-free language, enabling grammatical inference from execution data? Adjacent tools. The Mobility Workbench (MWB) and HAL model checkers for the π-calculus, and the mCRL2 toolset for process-algebraic verification, are directly applicable. C4 — Scalability and industrial adoption. Evidence from the corpus. Across all 34 primary studies, process instances used in case studies range from a few dozen to at most a few hundred activities. The largest evaluation is by Alkhammash et al. [APM24], who evaluate their ALERGIA-based discovery on real-world event logs from the 4TU repository, and by Kräuter et al. [KRKL24], whose web tool handles BPMN models of moderate size. No primary study reports a deployment in a production industrial environment. Research questions. (a) What is the computational complexity of GMWf scenario enumeration as a function of grammar size and recursion depth? (b) Can the ALERGIA inference algorithm be parallelized to handle event logs with millions of traces, as produced by enterprise BPM platforms (SAP, Camunda)? Adjacent tools. The ProM process mining framework, the Camunda BPM platform, and the PM4Py Python library provide industrial-grade event log processing infrastructure that grammar-based approaches could integrate with. C5 — Grammar-based management of process variability and evolution. Evidence from the corpus. Stream III addresses static variant management: Sarno et al. [SAWFA+ 15] handle composition of a fixed set of variants, while Montero et al. [MPRC08] derive a fixed process from a fixed feature model. No primary study addresses the dynamic evolution of a grammar as the process changes over time in response to regulatory or organizational changes. Research questions. (a) Can a CSG-based variant composition grammar be extended with a grammar transformation operator that captures the effect of a regulatory change? (b) Under what conditions does a sequence of grammar transformations preserve the soundness of the generated process variants? Adjacent tools. Software product line engineering frameworks (FeatureIDE, pure::variants) and model versioning tools (EMFStore, CDO) provide relevant infrastructure for managing evolving process family grammars.

24

M.M. ZEKENG NDADJI

12. Conclusion This paper has presented a systematic review of research at the intersection of formal grammars and Business Process Management (BPM). Starting from an initial corpus of 526 records and applying the SLR protocol of Kitchenham and Charters [KC07], we arrived at 34 primary studies spanning the mid-1990s to the mid-2020s. These studies were organized into seven research streams whose existence, taken together, establishes a central empirical finding: formal grammars have served as a productive conceptual and technical tool in BPM across every phase of the process lifecycle and across three decades of research. Reflecting on the trajectory of this field, two patterns stand out. First, there is a clear evolution of ambition: early work (Stream I) used grammars metaphorically, as a descriptive language for organizational behavior; subsequent work (Streams II– V) used grammars technically, as the formal basis for process specification, transformation, and verification; and the most recent work (Streams VI–VII) uses grammars analytically, either to mine models from data or to provide compositional behavioral semantics. This progression reflects a growing confidence in the formal apparatus of grammar theory as a substrate for BPM. Second, despite this confidence, the streams have developed largely in parallel, without cross-stream synthesis. None of the 34 primary studies synthesizes contributions from more than two streams. The most significant unresolved theoretical problem is the absence of a unifying framework that connects the structural specification power of attribute grammars (Stream IV), the transformation power of graph grammars (Stream V), the behavioral semantics of process algebras (Stream VII), and the inductive capabilities of grammatical inference (Stream VI). Building such a framework (one in which a process can be specified, transformed, verified, and discovered using a coherent grammatical substrate) is, we argue, the central open problem at the intersection of formal language theory and BPM. The five challenges articulated in Section 11 provide a structured research agenda toward this goal. Each challenge is grounded in a specific gap in the corpus, associated with concrete research questions, and connected to adjacent tools and methodologies that could serve as building blocks. We hope that this survey serves researchers entering this intersection not only as a map of where the field has been, but as a compass for where the most productive work remains to be done.

References [ABHBA19]

[APM24]

[BDLM07]

[BGH+ 07]

[BHK+ 15]

[BHKM14]

[BMDB16]

Salma Ayari, Yousra Bendali Hlaoui, and Leila Ben Ayed. A grammar based approach to BPMN model semantic preservation using refinement. In 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC), pages 202–207. IEEE, 2019. Hanan Alkhammash, Artem Polyvyanyy, and Alistair Moffat. Stochastic directly-follows process discovery using grammatical inference. In Advanced Information Systems Engineering – 36th International Conference, CAiSE 2024, volume 14663 of Lecture Notes in Computer Science, pages 86–102. Springer, 2024. Robin Bergenthum, Jörg Desel, Robert Lorenz, and Sebastian Mauser. Process mining based on regions of languages. In Business Process Management – 5th International Conference, BPM 2007, volume 4714 of Lecture Notes in Computer Science, pages 375–383. Springer, 2007. Kamal Bhattacharya, Cagdas E. Gerede, Richard Hull, Rong Liu, and Jianwen Su. Towards formal analysis of artifact-centric business process models. Business Process Management, 2007. Eric Badouel, Loı̈c Hélouët, Georges-Edouard Kouamou, Christophe Morvan, and Nsaibirni Robert Fondze Jr. Active workspaces: distributed collaborative systems based on guarded attribute grammars. ACM SIGAPP Applied Computing Review, 15(3):6–34, 2015. Eric Badouel, Loı̈c Hélouët, Georges-Edouard Kouamou, and Christophe Morvan. A grammatical approach to data-centric case management in a distributed collaborative environment. Technical Report RR-8528, INRIA, 2014. Dominic Breuker, Martin Matzner, Patrick Delfmann, and Jörg Becker. Comprehensible predictive models for business processes. MIS Quarterly, 40(4):1009–1034, 2016.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

[Bör12] [Cho59] [Coa99] [Dat98] [DDO08] [DLRMR18] [EH07]

[HMU07]

[Hoa85] [KC07]

[KK19]

[Knu68] [KRKL24]

[KTHVDA03] [LFvdA13]

[LGJS07]

[LM07] [LP03]

[LWP08] [MH11]

[Mil89] [MLT+ 09]

25

Egon Börger. Approaches to modeling business processes: a critical analysis of bpmn, workflow patterns and yawl. Software & Systems Modeling, 11(3):305–318, 2012. Noam Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137–167, 1959. Workflow Managment Coalition. Workflow management coalition terminology and glossary. Workflow Management Coalition, 1999. Anindya Datta. Automating the discovery of AS-IS business process models: Probabilistic and algorithmic approaches. Information Systems Research, 9(3):275–301, 1998. Remco M. Dijkman, Marlon Dumas, and Chun Ouyang. Semantics and analysis of business process models in BPMN. Inf. Softw. Technol., 50(12):1281–1294, 2008. Marlon Dumas, Marcello La Rosa, Jan Mendling, and Hajo A. Reijers. Fundamentals of Business Process Management, Second Edition. Springer, 2018. Torbjörn Ekman and Görel Hedin. The JastAdd extensible Java compiler. In Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA ’07), pages 1–18. ACM, 2007. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation, 3rd Edition. Pearson international edition. Addison-Wesley, 2007. Charles Antony Richard Hoare. Communicating Sequential Processes. Prentice-Hall, Englewood Cliffs, NJ, 1985. Barbara Kitchenham and Stuart Charters. Guidelines for performing systematic literature reviews in software engineering. Technical Report EBSE Technical Report EBSE-2007-01, Keele University and Durham University, 2007. Valeriia Kataeva and Anna A. Kalenkova. Applying graph grammars for the generation of process models and their logs. In Proceedings of the IEEE International Conference on Computer Science and Information Technologies. IEEE, 2019. Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127–145, 1968. Tim Kräuter, Adrian Rutle, Harald König, and Yngve Lamo. A higher-order transformation approach to the formalization and analysis of BPMN using graph transformation systems. Logical Methods in Computer Science, 20(4):4:1–4:31, 2024. Bartek Kiepuszewski, Arthur H. M. Ter Hofstede, and Wil M. P. Van Der Aalst. Fundamentals of control flow in workflows. Acta Informatica, 39(3):143–209, 2003. Sander J. J. Leemans, Dirk Fahland, and Wil M. P. van der Aalst. Discovering blockstructured process models from event logs — A constructive approach. In Application and Theory of Petri Nets and Concurrency (PETRI NETS 2013), volume 7927 of Lecture Notes in Computer Science, pages 311–329. Springer, 2013. Carsten Lohmann, Joel Greenyer, Juanjuan Jiang, and Tarja Systä. Applying triple graph grammars for pattern-based workflow model transformations. Journal of Object Technology, 6(9):253–273, 2007. Roberto Lucchi and Manuel Mazzara. A π-calculus based semantics for WS-BPEL. Journal of Logic and Algebraic Programming, 70(1):96–118, 2007. Jintae Lee and Brian T. Pentland. Exploring the process space: A grammatical approach to process design/redesign. Technical Report Working Paper 215, University of Colorado, 2003. Jintae Lee, George M. Wyner, and Brian T. Pentland. Process grammar as a tool for business process design. MIS Quarterly, 32(4):757–778, 2008. Steffen Mazanek and Michael Hanus. Constructing a bidirectional transformation between BPMN and BPEL with a functional logic programming language. Journal of Visual Languages and Computing, 22(1):66–89, 2011. Robin Milner. Communication and Concurrency. Prentice-Hall, Englewood Cliffs, NJ, 1989. David Moher, Alessandro Liberati, Jennifer Tetzlaff, Douglas G. Altman, and PRISMA Group. Preferred reporting items for systematic reviews and meta-analyses: The PRISMA statement. PLOS Medicine, 6(7):e1000097, 2009.

26

[MPRC08]

[MPW92] [NC03] [OG92]

[OMG13] [Pen94] [Pen95] [PR94] [PW05]

[Rec11]

[Rec12] [Rec13] [Ren04]

[RIRG10]

[Roz97] [RR10]

[RRGI11] [RRIG06]

[SAWFA+ 15]

[STA05]

[SZZ+ 16]

M.M. ZEKENG NDADJI

Ildefonso Montero, Joaquı́n Peña, and Antonio Ruiz-Cortés. From feature models to business processes. In Proceedings of the 2008 IEEE International Conference on Services Computing (SCC 2008), pages 617–620. IEEE, 2008. Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, I. Information and Computation, 100(1):1–40, 1992. Anil Nigam and Nathan S. Caswell. Business artifacts: An approach to operational specification. IBM Systems Journal, 42(3):428–445, 2003. José Oncina and Pedro Garcı́a. Inferring regular languages in polynomial update time. In Pattern Recognition and Image Analysis, volume 1 of Series in Machine Perception and Artificial Intelligence, pages 49–61. World Scientific, 1992. OMG. Business Process Model and Notation (BPMN), Version 2.0.2, December 2013. Version 2.0.2. Brian T. Pentland. Process grammars: A generative approach to process redesign. Technical Report CCS TR #178, Sloan WP #3722-94, MIT Center for Coordination Science, 1994. Brian T. Pentland. Grammatical models of organizational processes. Organization Science, 6(5):541–556, 1995. Brian T. Pentland and Henry H. Rueter. Organizational routines as grammars of action. Administrative Science Quarterly, 39(3):484–510, 1994. Frank Puhlmann and Mathias Weske. Using the π-calculus for formalizing workflow patterns. In Business Process Management – 3rd International Conference, BPM 2005, volume 3649 of Lecture Notes in Computer Science, pages 153–168. Springer, 2005. Jan Recker. Evaluations of Process Modeling Grammars: Ontological, Qualitative and Quantitative Analyses Using the Example of BPMN, volume 71 of Lecture Notes in Business Information Processing. Springer, 2011. Jan Recker. “Modeling with Tools is Easier, Believe Me”: The effects of tool functionality on modeling grammar usage beliefs. Information Systems, 37(3):213–226, 2012. Jan Recker. Empirical investigation of the usefulness of gateway constructs in process models. European Journal of Information Systems, 22(6):673–689, 2013. Arend Rensink. The GROOVE simulator: A tool for state space generation. In Applications of Graph Transformations with Industrial Relevance (AGTIVE), volume 3062 of Lecture Notes in Computer Science, pages 479–485. Springer, 2004. Jan Recker, Marta Indulska, Michael Rosemann, and Peter Green. The ontological deficiencies of process modeling in practice. European Journal of Information Systems, 19(5):501–525, 2010. Grzegorz Rozenberg, editor. Handbook of Graph Grammars and Computing by Graph Transformation, Volume 1: Foundations. World Scientific, 1997. Jan Recker and Michael Rosemann. A measurement instrument for process modeling research: Development, test and procedural model. Scandinavian Journal of Information Systems, 22(2):3–30, 2010. Jan Recker, Michael Rosemann, Peter Green, and Marta Indulska. Do ontological deficiencies in modeling grammars matter? MIS Quarterly, 35(1):57–79, 2011. Michael Rosemann, Jan Recker, Marta Indulska, and Peter Green. A study of the evolution of the representational capabilities of process modeling grammars. In Eric Dubois and Klaus Pohl, editors, Advanced Information Systems Engineering, pages 447–461, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Riyanarto Sarno, W. Ayu Widyasari, Nurul Fajrin Arif, Djauhar Manfaat, M. Sholikhan Arif, and Imam Baihaqi. Context sensitive grammar for composing business process model variants. In 2015 International Conference on Science in Information Technology (ICSITech), pages 138–143. IEEE, 2015. August-Wilhelm Scheer, Oliver Thomas, and Otmar Adam. Process-Aware Information Systems: Bridging People and Software through Process Technology, chapter Process modeling using event-driven process chains, pages 119–145. Wiley Online Library, 2005. Zhan Shi, Xiaoqin Zeng, Tingting Zhang, Song Huang, Zekun Qi, Hui Li, Bin Hu, Yi Yao, and Shuiming Zhong. Bidirectional transformation between BPMN and BPEL with graph grammar. Computers and Electrical Engineering, 53:139–154, 2016.

FORMAL GRAMMARS IN BPM: A SYSTEMATIC LITERATURE REVIEW

27

Maurice Tchoupé Tchendji, Milliam Maxime Zekeng Ndadji, and Didier Parigot. A grammatical approach for administrative workflow design and their distributed execution using structured and cooperatively edited mobile artifacts. SN Computer Science, 5(499), 2024. [vdA96] Wil M. P. van der Aalst. Structural characterizations of sound workflow nets. Technical Report Computing Science Reports 96/23, Eindhoven University of Technology, Department of Mathematics and Computing Science, 1996. [vdADCLR19] Han van der Aa, Claudio Di Ciccio, Henrik Leopold, and Hajo A. Reijers. Extracting declarative process models from natural language. In Advanced Information Systems Engineering – 31st International Conference, CAiSE 2019, volume 11483 of Lecture Notes in Computer Science, pages 365–382. Springer, 2019. [VDATH05] Wil M. P. Van Der Aalst and Arthur Harry Maria Ter Hofstede. Yawl: yet another workflow language. Information systems, 30(4):245–275, 2005. [VDATHKB03] Wil MP Van Der Aalst, Arthur HM Ter Hofstede, Bartek Kiepuszewski, and Alistair P Barros. Workflow patterns. Distributed and parallel databases, 14:5–51, 2003. [vdAtHW03] Wil M. P. van der Aalst, Arthur H. M. ter Hofstede, and Mathias Weske. Business process management: A survey. In Business Process Management – 1st International Conference, BPM 2003, volume 2678 of Lecture Notes in Computer Science, pages 1–12. Springer, 2003. [WTIM23] Akio Watanabe, Yousuke Takahashi, Hiroki Ikeuchi, and Kotaro Matsuda. Grammar-based process model representation for probabilistic conformance checking. In Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2023. Yair Wand and Ron Weber. On the ontological expressiveness of information systems [WW93] analysis and design grammars. Journal of Information Systems, 3(4):217–237, 1993. [ZNNMTNTT23] Milliam Maxime Zekeng Ndadji, Daniela Marionne Nguedia Momo, Franck Bruno Tonle Noumbo, and Maurice Tchoupé Tchendji. Non-recursive lsawfp models are structured workflows. ARIMA J., 38, 2023. Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni, [ZNTTTDP20] and Didier Parigot. A language and methodology based on scenarios, grammars and views, for administrative business processes modelling. ParadigmPlus, 1(3):1–22, 2020. [ZNTTTDP21] Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni, and Didier Parigot. A projection-stable grammatical model for the distributed execution of administrative processes with emphasis on actors’ views. Journal of King Saud University - Computer and Information Sciences, 2021. [TTZNP24]

This work is licensed under the Creative Commons Attribution License. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany