Search

The Petri net formalism is widely applied in both theoretical and practical settings. For the sake of performance analysis, the original Petri net model has been extended with the notion of time. This paper addresses the different issues involved with this extension. Also, it provides a stateof-the-art overview of different analysis techniques for timed Petri nets. A new analysis technique is presented, which combines the freedom of choosing arbitrary time distributions within a Petri net model on the one hand and efficient computation means on the other. [ABSTRACT FROM AUTHOR]

Workflow nets, a particular class of Petri nets, have become one of the standard ways to model and analyze workflows. Typically, they are used as an abstraction of the workflow that is used to check the so-called soundness property. This property guarantees the absence of livelocks, deadlocks, and other anomalies that can be detected without domain knowledge. Several authors have proposed alternative notions of soundness and have suggested to use more expressive languages, e.g., models with cancellations or priorities. This paper provides an overview of the different notions of soundness and investigates these in the presence of different extensions of workflow nets. We will show that the eight soundness notions described in the literature are decidable for workflow nets. However, most extensions will make all of these notions undecidable. These new results show the theoretical limits of workflow verification. Moreover, we discuss some of the analysis approaches described in the literature. [ABSTRACT FROM AUTHOR]

Background: Petri nets are a formal specification technique for modelling of control processes and modern flexible manufacturing systems. Interpreted Petri nets take into account input and output signals, allowing to apply them in any control system or even in control part of a cyber-physical system. Due to the fact that Petri nets are not used in the industrial practice, the students sometimes lack motivation to learn them. Contributions: In the paper we propose how to help students learn interpreted Petri nets with Minecraft (as a game-based learning). We show how interpreted Petri nets can be modelled in Minecraft and how they communicate with the surrounding environment via input and output signals to visualize control processes. The proposed approach has been validated experimentally among university students. Hypotheses: (1) Creating interpreted Petri net models with Minecraft helps to understand the basic principles; (2) Minecraft makes the course more attractive. Methodology: Students were divided into an experimental group (with game-based learning) and a control group (with traditional learning). The experimental group filled in a knowledge test twice (on the entry and on the exit) and a questionnaire. The control group filled in the same knowledge test at the end of the course. Findings: The observations confirm that the Minecraft-based teaching of interpreted Petri nets allows to gain better results in final tests, making at the same time the course more attractive and enjoyable. [ABSTRACT FROM AUTHOR]

In the post-cloud computing era, edge computing as a distributed computing paradigm, integrating the core capabilities of computing, storage, network, and application, provides EIS (edge intelligence service), such as real-time business, data optimization, intelligent application, security, and privacy protection. The EIS has become the core value driver to promote the IoE (Internet of Everything), to dig deeply into data value and create a new ecology of application scenarios. With the emergence of new business processes, EIS orchestration has also become a hot topic in academic research. A design methodology based on a complete "describe-synthesize-verify-evaluate" process was established to explore executable design specifications for EIS by means of model validation and running instances. As proof of concept, a CPN (colored Petri net) prototype was simulated and its operational processes were discovered by process mining from event data available in EIS for behavior verification. The instances running on WISE-PaaS demonstrate the feasibility of the research methodology, which aims to optimize EIS through service orchestration. [ABSTRACT FROM AUTHOR]

Real‐time systems are complex and composed of time‐bounded events that must satisfy the real‐time constraints for their proper functioning. To cope with the complexity of real‐time systems, model‐driven approaches such as model‐driven architecture (MDA) can be followed, which uses the conceptual models for system representation. This paper presents an MDA‐based automated approach for an early stage performance evaluation and verification of a real‐time system using the Unified Modeling Language (UML)/Modeling and Analysis of Real‐Time and Embedded systems (MARTE) sequence diagram. A metamodel‐based model‐to‐model transformation technique is used for mapping the UML/MARTE sequence diagram into the generalized Petri Net Markup Language (PNML) representation of the timed Petri net model using Atlas Transformation Language (ATL). The derived PNML representation has the advantage to support the interoperability between different Petri net tools when compared over the existing methods that produce tool‐specific representation. The proposed approach enables the system designers to create and evaluate alternate system designs and predict their behavior, contributing to improving the system quality. The contribution of the proposed technique for identifying the optimal system design is analyzed using a real‐time embedded sensor application. The proposed transformation approach is also validated using a real‐time system from the manufacturing domain. [ABSTRACT FROM AUTHOR]

The paper proposes an algorithm for safeness verification of a Petri net-based specification of the control part of cyber-physical systems. The method involves a linear algebra technique and is based on the computation of the state machine cover of a Petri net. Contrary to the well-known methods, the presented idea does not require obtaining all sequential components, nor the computation of all reachable states in the system. The efficiency and effectiveness of the proposed method have been verified experimentally with a set of 243 test modules (Petri net-based systems). The results of experiments show high efficiency of the proposed method since a solution has been found even for such nets where popular techniques are not able to analyze the safeness of the system. Finally, the presented algorithm is explained in detail using a real-life case-study example of the control part of a cyber-physical system. [ABSTRACT FROM AUTHOR]

Purpose: The purpose of this paper is to identify the relationships between process modeling and Industry 4.0, the strategic themes and the most used process modeling language in smart factories. The study also presents the growth of the field of study worldwide, the perspectives, main challenges, trends and suggestions for future works. Design/methodology/approach: To do this, a science mapping was performed using the software SciMAT, supported by VOS viewer. Findings: The results show that the Business Process Model and Notation (BPMN), Unified Modelling Language (UML) and Petri Net are the most relevant languages to smart manufacturing. The authors also highlighted the need to develop new languages or extensions capable of representing the dynamism, interoperability and multiple technologies of smart factories. Originality/value: It was possible to identify the most used process modeling languages in smart environments and understand how these languages assist control and manage smart processes. Besides, the authors highlighted challenges, new perspectives and the need for future works in the field. [ABSTRACT FROM AUTHOR]

Featured Application: An analysis method to assess and respond to the impact of resource failures on deadline of orders in Cyber-Physical Systems based on transformation of discrete timed Petri nets. Advancement of IoT and ICT provide infrastructure to manage, monitor and control Cyber-Physical Systems (CPS) through timely provision of real-time information from the shop floor. Although real-time information in CPS such as resource failures can be detected based on IoT and ICT, improper response to resource failures may cripple CPS and degrade performance. Effective operations of CPS relies on an effective scheme to evaluate the impact of resource failures, support decision making needed and take proper actions to respond to resource failures. This motivates us to develop a methodology to assess the impact of resource failures on operations of CPS and provide the decision support as needed. The goal of this study is to propose solution algorithms to analyze robustness of CPS with respect to resource failures in terms of the impact on temporal properties. Given CPS modeled by a class of discrete timed Petri nets (DTPNs), we develop theory to analyze robustness of CPS by transforming the models to residual spatial-temporal network (RSTN) models in which capacity loss due to resources is reflected. We formulate an optimization problem to determine the influence of resource failures on CPS based on RSTNs and analyze the feasibility to meet the order deadline. To study the feasibility to solve a real problem, we analyze the computational complexity of the proposed algorithms. We illustrate the proposed method by application scenarios. We conduct experiments to study efficiency and verify computational feasibility of the proposed method to solve a real problem. [ABSTRACT FROM AUTHOR]

A marked Petri net is lucent if there are no two different reachable markings enabling the same set of transitions, i.e., states are fully characterized by the transitions they enable. Characterizing the class of systems that are lucent is a foundational and also challenging question. However, little research has been done on the topic. In this paper, it is shown that all free-choice nets having a home cluster are lucent. These nets have a so-called home marking such that it is always possible to reach this marking again. Such a home marking can serve as a regeneration point or as an end-point. The result is highly relevant because in many applications, we want the system to be lucent and many "well-behaved" process models fall into the class identified in this paper. Unlike previous work, we do not require the marked Petri net to be live and stronglyconnected. Most of the analysis techniques for free-choice nets are tailored towards well-formed nets. The approach presented in this paper provides a novel perspective enabling new analysis techniques for free-choice nets that do not need to be well-formed. Therefore, we can also model systems and processes that are terminating and/or have an initialization phase. [ABSTRACT FROM AUTHOR]

In this paper, we provide a non‐Markovian Stochastic Petri Net (SPN) model for DevOpsworkflow specification, and we determine how business processes are carried out. After describing our model semantics, we show how general properties related to liveness and safety can be checked. After that, we provide several extensions on SPNs (SPN) the notation and expressivity to check some specific properties related to actors' (Developers and Operators) availability, interactions between the actors, and execution failures detection linked to the DevOps steps. Next, we validate the proposed model relevance with MATLAB simulation through a specific DevOps case study. Finally, we propose a truncated density function to anticipate the delays related to the DevOps business process overall steps. [ABSTRACT FROM AUTHOR]

Featured Application: This study provides a model driven approach in multi-agent systems to generate contextual information to guide workers/resources based on the Cyber World models in Cyber-Physical Systems. Although Cyber-Physical Systems (CPS) provides a paradigm to accommodate frequent changes in manufacturing sector, modeling and managing operations of CPS are challenging issues due to the complex interactions between entities in the system. Development of an effective context-aware workflow management system to guide the entities in the system is a critical factor to attain the potential benefits of CPS. In this paper, we will address the issue on the design of context-aware workflow management systems for CPS in IoT-enabled manufacturing environment. A CPS consists two parts, the Physical World and the Cyber World. To achieve the goal to design a context-aware information system for CPS, the Cyber World models of the entities in the system are constructed based on discrete timed Petri nets (DTPN) and a multi-agent system architecture in which each entity in the system is modeled as an agent to capture the interactions of entities in CPS. To develop context-aware workflow management systems for CPS, a Configuration/Scheduling Feasibility Problem and a Context Generation Problem in CPS are formulated. A condition for configuration/scheduling feasibility based on transformation of the Cyber World Models is established to develop an algorithm to generate contextual information to guide the operation of CPS. The proposed method is illustrated by examples. A series of experiments have been conducted to demonstrate the practicality of the proposed method in terms of computation time and response time. The results indicate that the computation time and total response time increase polynomially with respect to problem size parameters and show that the proposed method is effective in solving real problems. [ABSTRACT FROM AUTHOR]

Automated manufacturing systems have been studied widely in terms of scheduling. As technology evolves, the behaviour of tools in automated manufacturing systems has become complicated. Therefore, mathematical approaches to the analysis of complex schedules no longer reflect reality. In this paper, we propose a systematic way of conducting simulation experiments to evaluate the complex operating schedules of automated manufacturing systems. A simulation model is based on a timed Petri net to take advantage of its mathematical strength. Since a Petri net cannot itself have token firing rules, we introduce additional states called operational states. Operational states are not directly related to a Petri net, and are only used for decision making. In addition, a decision function that is responsible for the conflict resolution of a Petri net model and an operational state transition function are introduced. The parallel simulation concept is also suggested by dividing a Petri net into several independent decision sub-nets. A multi-cluster tool system for semiconductor manufacturing is analysed as an application. [ABSTRACT FROM PUBLISHER]

Various space missions, including the Russian and Chinese interplanetary exploration collaboration in 2011 and the Phobos-Grunt space project to be relaunched by the Chinese in 2025, carry a soil preparation system (SOPSYS), which is an instrument used for scientific experiments. The design and manufacture of this precision instrument require stringent manufacturing processes and workflow of the highest quality, with every process in the project carefully monitored and controlled. All processes should be completed within the deadline so that the space project can be launched at the scheduled time. The colored Petri net (CPN) modeling method can describe a variety of resource types and execution logic, and it can be formally verified. Based on these advantages, we clearly describe the complex structure of the SPOSYS unit production process. In addition, we use critical time and the 6 sigma system to evaluate the availability and reliability of workflows, and we use elimination and simplification (ECRS) methods and constraint theory to improve the manufacturing process of the SOPSYS unit. We further provide optimization theories, methods, and insights for workflow management in time-sensitive and independent manufacturing systems. [ABSTRACT FROM AUTHOR]

Usually, a Petri net is applied as an RFID model tool. This paper, otherwise, presents another approach to the Petri net concerning RFID systems. This approach, called elementary Petri net inside an RFID distributed database, or PNRD, is the first step to improve RFID and control systems integration, based on a formal data structure to identify and update the product state in real-time process execution, allowing automatic discovery of unexpected events during tag data capture. There are two main features in this approach: to use RFID tags as the object process expected database and last product state identification; and to apply Petri net analysis to automatically update the last product state registry during reader data capture. RFID reader data capture can be viewed, in Petri nets, as a direct analysis of locality for a specific transition that holds in a specific workflow. Following this direction, RFID readers storage Petri net control vector list related to each tag id is expected to be perceived. This paper presents PNRD cornerstones and a PNRD implementation example in software called DEMIS-Distributed Environment in Manufacturing Information Systems. [ABSTRACT FROM AUTHOR]

A process model is lucent if no two reachable states are enabling the same set of activities. An event log is translucent if each event carries information about the set of activities enabled when the event occurred (normally one only sees the activity performed). Both lucency and translucency focus on the set of enabled activities and are therefore related. Surprisingly, these notions have not been investigated before. This paper aims to (1) characterize process models that are lucent, (2) provide a discovery approach to learn process models from translucent event logs, and (3) relate lucency and translucency. Lucency is defined both in terms of automata and Petri nets. A marked Petri net is lucent if there are no two different reachable markings enabling the same set of transitions, i.e., states are fully characterized by the transitions they enable. We will also provide a novel process discovery technique starting from a translucent event log. It turns out that information about the set of activities is extremely valuable for process discovery. We will provide sufficient conditions to ensure that the discovered model is lucent and show that a translucent event log sampled from a lucent process model can be used to rediscover the original model. We anticipate new analysis techniques exploiting lucency. Moreover, as shown in this paper, translucent event logs provide valuable information that can be exploited by a new breed to process mining techniques. [ABSTRACT FROM AUTHOR]

Web applications are now used in every aspect of our lives to manage work, provide products and services, read email, and provide entertainment. The software technologies used to build web applications provide features that help designers provide flexible functionality, but that are challenging to model and test. In particular, the network-based request-response model of programming means that web applications are inherently "stateless" and implicitly concurrent. They are stateless because a new network connection is made for each request (for example, when a user clicks a submit button). Thus, the server does not, by default, recognize multiple requests from the same user. Web applications are also concurrent because multiple users can use the same web application at the same time, creating contention for the same resources. Unfortunately, most web application testing does not adequately evaluate these aspects of web applications, leaving many software faults in deployed web applications. Part of this problem is because most traditional software modeling tools (such as UML) do not have built-in support for the stateless and concurrent aspects of web applications. This research project uses a novel model that is based on Petri nets to describe certain aspects of the behavior of web applications. This paper makes several contributions. We present a novel technique to design tests from this model that explicitly tests concurrency in web applications. We present novel coverage criteria that are defined on the Petri net model. We present results from an empirical study of 18 web applications with 343 components and 30,186 lines of code, followed by a case study on a large industrial web application. The tests found significantly more faults than traditional requirements-based tests, with fewer tests. [ABSTRACT FROM AUTHOR]

This paper describes a synthesis procedure dedicated to the construction of choice-free Petri nets from finite persistent transition systems, whenever possible. Taking advantage of the properties of choice-free Petri nets, a two-step approach is proposed. A pre-synthesis step checks necessary structural properties of the transition system and constructs some data structures needed for the second step. Then, a minimised set of simplified systems of linear inequalities is distilled from a general region-theoretic approach. This leads to a substantial narrowing of the sets of states for which linear inequalities must be solved, and allows an early detection of failures, supported by constructive error messages. The performance of the resulting algorithm is measured and compared numerically with existing synthesis tools. [ABSTRACT FROM AUTHOR]

In the actual business world, companies rely more and more on workflows to model the core of their business processes. In this context, the focus of workflow analysts is made on the verification of workflows specifications, in particular of modal specifications that allow the description of necessary or admissible behaviors. The design and the analysis of business processes commonly relies on workflow nets, a suited class of Petri nets. The goal of this paper is to evaluate and compare in a deep way two resolution methods—satisfiability modulo theory and constraint logic programming—applied to the verification of modal specifications over workflow nets. Firstly, it provides a concise description of the verification methods based on constraint solving. Secondly, it introduces the toolchain developed to automate the full verification process. Thirdly, it describes the experimental protocol designed to evaluate and compare the scalability and efficiency of both resolution approaches and reports on the obtained results. Finally, these obtained results are discussed in detail, lessons learned from these experiments are given, and, on the basis of experiments feedback, directions for improvement and future work are suggested. [ABSTRACT FROM AUTHOR]

In this paper, we treat the control problem of timed discrete event systems under temporal constraints. This type of constraint is very frequent in production systems, transportation network and in networked automation systems. Precisely, we are interested in the validation of strict temporal constraints imposed on the paths in a timed event graph (TEG) by using Max-Plus algebra. Not all the transitions of the considered TEG model are controllable, i.e. only the input transitions are controllable. An analytical approach for computing state feedback controllers is developed. Sufficient condition is given for the existence of causal control laws satisfying the temporal constraints. In the first, a TEG with observable transitions is considered. Then, the proposed approach is extended to the partially observable TEG. The synthesised feedback can be interpreted by places of control connected to the TEG to guarantee the respect of the time constraints. The proposed method is illustrated in the assembly system example. [ABSTRACT FROM AUTHOR]

The main purpose of the paper is presentation of new opportunities for process modelling. In the literature review section, Petri nets as one of the formal modelling notation of processes is highlighted and introduction of relatively young research discipline - process mining - is presented. One of the process mining tasks is process model discovery from event logs gathered in informatics systems in enterprise. In the article practical example of process model discovery with ProM software is given with use of real event log from Volvo IT Belgium. In conclusions further opportunities of process mining techniques in process management are emphasized. [ABSTRACT FROM AUTHOR]

Scheduling patients in a hospital is a challenging issue due to distributed organizational structure, dynamic medical workflows, variability of resources and the computational complexity involved. It calls for a sustainable architecture and a flexible scheduling scheme that can dynamically allocate available resources to promptly react to patients in a hospital and deliver healthcare services timely. The objectives of this paper are to propose a viable and systematic approach to develop a scalable and sustainable scheduling system based on multi-agent system (MAS) to shorten patient stay in a hospital and plan schedules based on the medical workflows and available resources. To develop a patient scheduling system, we combine MAS architecture, contract net protocol (CNP), workflow specification models based on Petri nets and the cooperative distributed problem solving concept. To achieve interoperability and sustainability, Petri Net Markup Language (PNML) and XML are used to specify precedence constraints of operations in medical workflows and capabilities of resource agents, respectively. Agent communication language (ACL) and CNP are used to achieve communication and negotiation/mutual selection of agents. A collaborative algorithm is invoked by individual agents to optimize the schedules locally based on a problem formulation automatically obtained by Petri net models. We have developed a scheduling system based on a FIPA compliant MAS platform to solve the dynamic patient scheduling problem. To illustrate the benefit of our approach, we compare the performance of our method with a heuristic rule commonly used in practice. In addition, we also analyze and verify scalability of our approach by experiments. [ABSTRACT FROM AUTHOR]

This paper presents a notion of reduction where a WF net is transformed into a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more of such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantic properties such as soundness, can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that follow good hierarchical design principles. It is shown that the reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net. [ABSTRACT FROM AUTHOR]

Formal verification plays a crucial role when dealing with correctness of systems. In a previous work, the authors proposed a class of models, the Unary Resource Description Framework Petri Nets (U-RDF-PN), which integrated Petri nets and (RDF-based) semantic information. The work also proposed a model checking approach for the analysis of system behavioural properties that made use of the net reachability graph. Computing such a graph, specially when dealing with high-level structures as RDF graphs, is a very expensive task that must be considered. This paper describes the development of a parallel solution for the computation of the reachability graph of U-RDF-PN models. Besides that, the paper presents some experimental results when the tool was deployed in cluster and cloud frameworks. The results not only show the improvement in the total time required for computing the graph, but also the high scalability of the solution, which make it very useful thanks to the current (and future) availability of cloud infrastructures. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents a novel analytical method for soundness verification of workflow nets and reset workflow nets, using the well-known stability results of Lyapunov for Petri nets. We also prove that the soundness property is decidable for workflow nets and reset workflow nets. In addition, we provide evidence of several outcomes related with properties such as boundedness, liveness, reversibility and blocking using stability. Our approach is validated theoretically and by a numerical example related to traffic signal-control synchronisation. [ABSTRACT FROM AUTHOR]

Multi-level multi-agent systems (MASs) with dynamic structure are widely used in solving important applied problems in telecommunication, transportation, social, and other systems. Therefore, ensuring correct behavior of such systems is an actual and important task. One of the most error-prone stages of system development in the framework of model-oriented approach is the implementation stage, in the course of which a program code is constructed based on the model developed. This paper presents an algorithm for automated translation of MAS models represented as nested Petri nets into systems of distributed components. Nested Petri nets are the extension of Petri nets in the framework of the nets-within-nets approach, which assumes that tokens in a Petri net may themselves be Petri nets, possess autonomous behavior, and interact with other tokens of the net. This makes it possible to model MASs with dynamic structure in a natural way. The translation presented in this paper preserves distribution level and important behavioral properties (safety, liveness, and conditional liveness) of the original model and ensures fairness of the target system execution. The use of such translation makes it possible to automate construction of distributed MASs by models of nested Petri nets. As a test example, translation of nested Petri nets into systems of distributed components was implemented on the basis of the EJB component technology. [ABSTRACT FROM AUTHOR]

With rapid development and application of mobile internet, geographic information in the field of business process is now more widely used. There are more and more researches in the field of the relationships between geographic information and workflow modeling. According to the workflow with geospatial constraints, this paper first discusses the geospatial constraints theory deeply, proposes a new concept of geospatial constraints unit, and then designs a geospatial constraint net model (GCNet). Secondly, this paper designs a new workflow model with geospatial constraints (GCWF-net) based on GCNet and workflow net (WF-net), and then analyzes some properties of the model. Finally, this paper discusses how to put GCWF-net into application practice from three aspects: extending PNML (Petri Net Markup Language) labels for GCWF-net, converting PNML to BPEL (Business Process Execution Language) and implementing BPEL. [ABSTRACT FROM AUTHOR]

Weighted Petri nets as a kind of formal language are widely used to model and verify discrete event systems related to resource allocation like flexible manufacturing systems. System of Simple Sequential Processes with Multi-Resources (S3PMR, a subclass of weighted Petri nets and an important extension to the well-known System of Simple Sequential Processes with Resources, can model many discrete event systems in which (1) multiple processes may run in parallel and (2) each execution step of each process may use multiple units from multiple resource types. This paper gives a necessary and sufficient condition for the liveness of S3PMR. A new structural concept called Structurally Circular Wait (SCW) is proposed for S3PMR. Blocking Marking (BM) associated with an SCW is defined. It is proven that a marked S3PMR is live if and only if each SCW has no BM. We use an example of multi-processor system-on-chip to show that SCW and BM can precisely characterise the (partial) deadlocks for S3PMR. Simultaneously, two examples are used to show the advantages of SCW in preventing deadlocks of S3PMR. These results are significant for the further research on dealing with the deadlock problem. [ABSTRACT FROM PUBLISHER]

Petri nets are a simple formalism for modeling concurrent computation. They are also an interesting tool for modeling and analysing biochemical reaction systems, bridging the gap between purely qualitative and quantitative models. Biological networks can indeed be complex, large, and with many unknown kinetic parameters, which makes the development of quantitative models difficult. In this paper, we focus on the Petri net representation of biochemical reactions and on two structural properties of Petri nets, siphons and traps, that bring us information about the persistence of some molecular species, independently of the kinetics. We first study the theoretical time complexity of minimal siphon decision problems in general Petri nets, and present three new complexity results: first, we show that the existence of a siphon of a given cardinality is NP-complete; second, we prove that deciding the Siphon-Trap property is co-NP-complete; third, we prove that deciding the existence of a minimal siphon containing a given set of places, deciding the existence of a siphon of a given cardinality and deciding the Siphon-Trap property can be done in linear time in Petri nets of bounded tree-width. Then, we present a Boolean model of siphons and traps, and two method for enumerating all minimal siphons and traps of a Petri net, by using a SAT solver and a Constraint Logic Program (CLP) respectively. On a benchmark of 345 Petri nets of hundreds of places and transitions, extracted from biological models from the BioModels repository, as well as on a benchmark composed of 80 Petri nets from the Petriweb database of industrial processes, we show that both the SAT and CLP methods are overall faster by one or two orders of magnitude compared to the state-of-the-art algorithm from the Petri net community, and are in fact able to solve all the enumeration problems of our practical benchmarks. We investigate why these programs perform so well in practice, and provide some elements of explanation related to our theoretical complexity results. [ABSTRACT FROM AUTHOR]

Business processes, operational environment, variability of resources and user needs may change from time to time. An effective workflow management software system must be able to accommodate these changes. The ability to dynamically adapt to changes is a key success factor for workflow management systems. Holonic multi-agent systems (HMS) provide a flexible and reconfigurable architecture to accommodate changes based on dynamic organization and collaboration of autonomous agents. Although HMS provides a potential architecture to accommodate changes, the dynamic organization formed in HMS poses a challenge in the development of a new software development methodology to dynamically compose the services and adapt to changes as needed. This motivates us to study and propose a methodology to design self-adaptive software systems based on the HMS architecture. In this paper, we formulate a workflow adaptation problem (WAP) and propose an interaction mechanism based on contract net protocol (CNP) to find a solution to WAP to compose the services based on HMS. The interaction mechanism relies on a service publication and discovery scheme to find a set of task agents and a set of actor agents to compose the required services in HMS. We propose a viable self-adaptation scheme to reconfigure the agents and the composed services based on cooperation of agents in HMS to accommodate the changes in workflow and capabilities of actors. We propose architecture for our design methodology and present an application scenario to illustrate our idea. [ABSTRACT FROM AUTHOR]

Nondeterministic firing of concurrent transitions in Petri nets (PNs) may lead to the disappearance of conflicts. The disappearance implies that the partial conflicting transitions in a conflict become disabled before the resolution of the conflict. The phenomenon is called confusions that are caused by the interlacement of conflicting and concurrent transitions in PNs, which generates incomplete and faulty system conflicting behavior such that conflicts cannot be correctly resolved. In this paper, conflict-increasing confusions (CICs) and conflict-decreasing confusions (CDCs) in a PN are investigated. The relation graph of conflicts and confusions (RGC²) in a PN is proposed to detect the structure of confusions. To avoid the occurrence of confusions in a PN, an algorithm based on generalized mutual exclusion constraints (GMECs) is proposed, which can generate confusion-avoidance supervisors such that the occurrence of conflicts can be ensured in a PN. Finally, an example of confusion detection and avoidance in a flexible assembly system is presented. [ABSTRACT FROM AUTHOR]

In this paper we contrast the application of two different methods for verifying soundness of workflow. The first approach considers the structure of the workflow net and proposes an analytical process that takes into account the incidence matrix and a strict positive vector to prove soundness. The second method is based on decision process Petri nets theory showing that the problem of finding an optimum trajectory for validation of well-formed workflow is solvable. The advantage of both solutions is that to tackle the soundness verification problem use the Lyapunov stability theory which corresponds to an analytical method for Petri nets. We validate our statement theoretically and by an application example. [ABSTRACT FROM PUBLISHER]

For designing and analyzing complex workflow nets the notion of hierarchical decomposition can be essential for keeping the structure of the workflow comprehensible. In this paper we study two classes of nets: hierarchical nets and extended hierarchical nets. The first have a simple hierarchical structure and can be defined in terms of five simple refinement rules. We show that for arbitrary nets it can be easily verified if they can be constructed this way, thus confirming their good design and the properties following from it. As we prove, this can be done by performing the refinements in reverse, i.e., by contracting subnets into single nodes. It is shown that the choice of the contracted subnet does not change the final result of the process, and therefore this procedure for checking the hierarchical structure requires no back-tracking. The second class, extended hierarchical nets, is an extension of the first class where two types of extra refinements are introduced that allow to indicate (1) the synchronization between two parallel running subworkflows or (2) the transfer of a thread from one subworkflow to another one. These refinements come with natural and necessary preconditions that ensure that result is still a sound workflow net. In case (1) where we want to synchronize two actions in two subworkflows, we should convince ourselves that the subworkflows represent parallel threads which always execute together, otherwise a deadlock could easily arise. Dually, in case (2), if after the moment that a choice was made between two subworkflows we at a later point in the workflow want to allow a transfer between them, this can be done safely provided that we did not enter any thread fork in the meantime. We show that the class of extended hierarchical nets, which is defined by adding these two additional types of refinement, is a proper superset of the hierarchical nets, but still all such nets exhibit the correctness property of *-soundness. We do this by showing that the class is a proper subset of the AND-OR nets which were in earlier work shown to have this property. [ABSTRACT FROM AUTHOR]

Analysis of workflow processes with quantitative aspects like timing is of interest in numerous time-critical applications. We suggest a workflow model based on timed-arc Petri nets and study the foundational problems of soundness and strong (time-bounded) soundness. We first consider the discrete-time semantics (integer delays) and explore the decidability of the soundness problems and show, among others, that soundness is decidable for monotonic workflow nets while reachability is undecidable. For general timed-arc workflow nets soundness and strong soundness become undecidable, though we can design efficient verification algorithms for the subclass of bounded nets. We also discuss the soundness problem in the continuous-time semantics (real-number delays) and show that for nets with nonstrict guards (where the reachability question coincides for both semantics) the soundness checking problem does not in general follow the approach for the discrete semantics and different zone-based techniques are needed for introducing its decidability in the bounded case. Finally, we demonstrate the usability of our theory on the case studies of a Brake System Control Unit used in aircraft certification, the MPEG2 encoding algorithm, and a blood transfusion workflow. The implementation of the algorithms is freely available as a part of the model checker TAPAAL (www.tapaal.net). [ABSTRACT FROM AUTHOR]

Since their inception in 1962, Petri nets have been used in a wide variety of application domains. Although Petri nets are graphical and easy to understand, they have formal semantics and allow for analysis techniques ranging from model checking and structural analysis to process mining and performance analysis. Over time Petri nets emerged as a solid foundation for Business Process Management (BPM) research. The BPM discipline develops methods, techniques, and tools to support the design, enactment, management, and analysis of operational business processes. Mainstream business process modeling notations and workflow management systems are using token-based semantics borrowed from Petri nets. Moreover, state-of-the-art BPM analysis techniques are using Petri nets as an internal representation. Users of BPM methods and tools are often not aware of this. This paper aims to unveil the seminal role of Petri nets in BPM. [ABSTRACT FROM AUTHOR]

In this paper we consider workflow nets as dynamical systems governed by ordinary difference equations described by a particular class of Petri nets. Workflow nets are a formal model of business processes. Well-formed business processes correspond to sound workflow nets. Even if it seems necessary to require the soundness of workflow nets, there exist business processes with conditional behavior that will not necessarily satisfy the soundness property. In this sense, we propose an analytical method for showing that a workflow net satisfies the classical soundness property using a Petri net. To present our statement, we use Lyapunov stability theory to tackle the classical soundness verification problem for a class of dynamical systems described by Petri nets. This class of Petri nets allows a dynamical model representation that can be expressed in terms of difference equations. As a result, by applying Lyapunov theory, the classical soundness property for workflow nets is solved proving that the Petri net representation is stable. We show that a finite and non-blocking workflow net satisfies the sound property if and only if its corresponding PN is stable, i.e., given the incidence matrix A of the corresponding PN, there exists a Φ strictly positive m vector such that AΦ ≤ 0. The key contribution of the paper is the analytical method itself that satisfies part of the definition of the classical soundness requirements. The method is designed for practical applications, guarantees that anomalies can be detected without domain knowledge, and can be easily implemented into existing commercial systems that do not support the verification of workflows. The validity of the proposed method is successfully demonstrated by application examples. [ABSTRACT FROM AUTHOR]

Elementary object systems (EOS for short) are Petri nets in which tokens may be Petri nets again. Originally proposed by Valk for a two levelled structure, the formalism was later generalised for arbitrary nesting structures. However, even if restricted to a nesting depth of two, EOS are Turing-complete and thus many problems like reachability and liveness are undecidable for them. Nonetheless, since they are useful to model many practical applications a natural question is how to restrict the formalism in such a way, that the resulting restricted formalism is still helpful in a modelling context, but so that important verification problems like reachability become quickly decidable. In the last years several structural and dynamic restrictions for EOS have therefore been investigated. These investigations have been central to the first author's recent PhD thesis and have been published in past editions of this journal and on conferences. In this paper we add several new results and present them together with the old in a unified fashion highlighting the central message of these investigations. [ABSTRACT FROM AUTHOR]

Although virtual enterprises (VE) make it possible for small flexible enterprises to form a collaborative network to respond to business opportunities through dynamic coalition and sharing of the core competencies and resources, they also pose new challenges and issues. Creation of VE involves dynamically established partnerships between the partners and relies on a flexible coordination scheme. The dynamic organizations formed in VE present a challenge in the development of a new methodology to dynamically allocate re-sources and deliver the relevant information to the right people at the right time. A key issue is the development of an effective workflow management scheme for VE. Multi-agent systems (MAS) provide a flexible architecture to deal with changes based on dynamic organization and collaboration of autonomous agents. Despite the extensive studies and research results on MAS, development of a design methodology to support coordination and operations is critical to the success and adoption of VE. The objectives of this research are to propose a design methodology to facilitate coordination and development of context-aware workflow management systems and achieve effective resource allocation for VE based on MAS architecture. To achieve these objectives, a scheme for coordination of agents is proposed. Petri net models are used in the coordination scheme to describe workflows and capture resource activities in VE. The interactions between agents lead to a dynamic workflow model for VE. Based on the aforementioned model, we propose architecture to dynamically generate context-aware graphical user interface to guide the users and control resource allocation based on the state of VE. An order management example is used throughout this paper to illustrate the proposed design methodology. [ABSTRACT FROM AUTHOR]

We extend workflow Petri nets (wf-nets) with discrete prices, by associating a price to the execution of a transition and to the storage of tokens. We first define the safety and the soundness problems for priced wf-nets. A priced wf-net is safe if no execution costs more than a given budget. The soundness problem is that of deciding whether the workflow can always terminate properly, where in the priced setting 'properly' also means that the execution does not cost more than a given threshold. Then, we study safety and soundness of resource-constrained workflow nets (rcwf-nets), an extension of wf-nets for the modeling of concurrent executions of a workflow, sharing some global resources. We develop a framework in which to study safety and soundness for priced rcwf-nets, that is parametric on the cost model. Then, that framework is instantiated, obtaining the cases in which the sum, the maximum, the average and the discounted sum of the prices of all instances are considered. We study the decidability and the complexity of these properties, together with their relation. [ABSTRACT FROM AUTHOR]

Classical workflow nets (WF-nets for short) are an important subclass of Petri nets that are widely used to model and analyze workflow systems. Soundness is a crucial property of workflow systems and guarantees that these systems are deadlock-free and bounded. Aalst et al. proved that the soundness problem is decidable for WF-nets and can be polynomially solvable for free-choice WF-nets. This paper proves that the soundness problem is PSPACE-hard for WF-nets. Furthermore, it is proven that the soundness problem is PSPACE-complete for bounded WF-nets. Based on the above conclusion, it is derived that the soundness problem is also PSPACE-complete for bounded WF-nets with reset or inhibitor arcs (ReWF-nets and InWF-nets for short, resp.). ReWF- and InWF-nets are two extensions to WF-nets and their soundness problems were proven by Aalst et al. to be undecidable. Additionally, we prove that the soundness problem is co-NP-hard for asymmetric-choice WF-nets that are a larger class and can model more cases of interaction and resource allocation than free-choice ones. [ABSTRACT FROM AUTHOR]

This contribution presents recent results on Elementary Object Systems (EOS). Object nets are Petri nets which have Petri nets as tokens - an approach known as the nets-within-nets paradigm. In this work we study the relationship of EOS to existing Petri net formalisms. It turns out that EOS are equivalent to counter programs. But even for the restricted subclass of conservative EOS reachability and liveness are undecidable problems. On the other hand for other properties like boundedness are still decidable for conservative EOS. We also study the sub-class of generalised state machines, which is worth mentioning since it combines decidability of many theoretically interesting properties with a quite rich practical modelling expressiveness. [ABSTRACT FROM AUTHOR]

The practical relevance of process mining is increasing as more and more event data become available. Process mining techniques aim to discover, monitor and improve real processes by extracting knowledge from event logs. The two most prominent process mining tasks are: (i) process discovery: learning a process model from example behavior recorded in an event log, and (ii) conformance checking: diagnosing and quantifying discrepancies between observed behavior and modeled behavior. The increasing volume of event data provides both opportunities and challenges for process mining. Existing process mining techniques have problems dealing with large event logs referring to many different activities. Therefore, we propose a generic approach to decompose process mining problems. The decomposition approach is generic and can be combined with different existing process discovery and conformance checking techniques. It is possible to split computationally challenging process mining problems into many smaller problems that can be analyzed easily and whose results can be combined into solutions for the original problems. [ABSTRACT FROM AUTHOR]

Pervasive computing, the new computing paradigm aiming at providing services anywhere at anytime, poses great challenges on dynamic service composition. Existing service composition methods can hardly meet the requirements of dynamism and performance for pervasive computing. This paper proposes a Petri net based service model to formally describe the function of services and employs a parameter based service description to represent both semantic and syntactic of services. And services are pre-aggregated in a two-layered graph according to the input and output parameters of the service description. Furthermore, we design a novel service composition scheme to achieve the user requirement through a tree search algorithm. The theoretical analysis and comprehensive simulation experiments show that both service model and composition scheme are correct and efficient. [ABSTRACT FROM AUTHOR]

This contribution presents decidability results for the formalism of Elementary Object Systems (EOS). Object nets are Petri nets which have Petri nets as tokens - an approach known as the nets-within-nets paradigm. In this paper we study the relationship of the reachability and the liveness problem. We prove that both problems are undecidable for EOS (even for the subclass of conservative EOS) while it is well known that both are decidable for classical p/t nets. Despite these undecidability results, boundedness can be decided for conservative EOS using a monotonicity argument similar to that for p/t nets. [ABSTRACT FROM AUTHOR]

A central problem in the area of Process Mining is to obtain a formal model that represents selected behavior of a system. The theory of regions has been applied to address this problem, enabling the derivation of a Petri net whose language includes a set of traces. However, when dealing with real-life systems, the available tool support for performing such a task is unsatisfactory, due to the complex algorithms that are required. In this paper, the theory of regions is revisited to devise a novel technique that explores the space of regions by combining the elements of a region basis. Due to its light space requirements, the approach can represent an important step for bridging the gap between the theory of regions and its industrial application. Experimental results show that there is improvement in orders of magnitude in comparison with state-of-the-art tools for the same task. [ABSTRACT FROM AUTHOR]

In this paper we study the complexity of the liveness problem for safe Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens. They are called elementary if the net system has a two levelled structure. The concept of safeness bounds the number of tokens which may reside on a place. PSPACE-hardness of the liveness problem for safe EOS directly follows from the related result for safe p/t nets. We then devise a polynomial space algorithm for this problem and indeed for every property that can be expressed in the temporal logic CTL. [ABSTRACT FROM AUTHOR]