2.1 Petri nets

Petri nets have been around since 1962 (Petri, Reference Petri1962) as a graphical and mathematical technique suitable for modeling and analyzing information processing systems that are characterized as being concurrent, asynchronous, distributed, parallel, non-deterministic and/or stochastic. The Petri net model has a powerful capability to model events and states in a distributed system and to capture sequential, concurrency and event-based control. As a graphical technique, Petri nets can be used as a visual aid for communicating between different communities (for instance, between business analysts and systems different designers), while, as a mathematical technique, Petri nets provide a means for setting up state equations, algebraic equations and other models governing the behavior of systems (Murata, Reference Murata1989).

A Petri net is a directed graph together with an initial state called the initial marking. The underlying graph of a Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called places and transitions, which are connected via arcs. Graphically, each place is represented by a circle, while transitions are marked as a rectangle. The flow relation of the Petri net is represented by arcs form places to transitions or from transitions to places. A marking assigns to each place a non-negative integer k, meaning that the place is marked with k tokens, which are represented as black dots. Places have a finite place capacity restricting the maximum number of tokens they can hold. A transition has a certain number of input and output places representing pre- and post-conditions for the firing of the transition. Sometimes, k tokens are put in a place to indicate that k data items or resources are available. In order to understand the Petri net, a formal definition of a Petri net is given as follows (Liu, Reference Liu2006):

The behavior of many systems can be described in terms of system states and their changes. In order to simulate the dynamic behavior of a system, a state or marking in a Petri net is changed according to the following firing rules (Recker & Indulska, Reference Recker and Indulska2007):

• ∙ a transition is enabled if each of its input places is marked with as many tokens as the weight of the arc leading to the transition described;

• ∙ an enabled transition may or may not fire; and

• ∙ a firing of an enabled transition removes the tokens from the input places in accordance to the arc weight and adds tokens to each output place in accordance to the weight of the arc leading from the transition to its output places.

Let us begin with an illustration to introduce the Petri nets. The producer–consumer problem is a very common example in computer science, which includes two processes: (i) a process of producer creates objects, which are put into the buffer; (ii) a process of consumer waits until an object has been put in the buffer, removes it, and consumes it. The Petri net shown in Figure 1 represents the well-known producer–consumer system, where the place buffer can be used to connect the producing process including place P1, P2, transition produce, put into buffer and the consuming process consisting of place P4, P5 and transition remove from buffer, consume. Each token represents an item, and the consumer can consume as long as the place buffer has items (tokens).

Figure 1

An illustration of Petri nets of a producer–consumer system

Petri nets have been proposed for a very wide variety of applications (Petri, Reference Petri1962; Murata, Reference Murata1989; Li & Lara-Rosano, Reference Li and Lara-Rosano2000; Guo-Yan, Reference Guo-Yan2006; Liu, Reference Liu2006; Shen, Reference Shen2006; Yen, Reference Yen2006; Recker & Indulska, Reference Recker and Indulska2007; Araujo & Roque, Reference Araujo and Roque2009). In the following statements, we mainly introduce the application areas of Petri nets. Owing to the generality and permissiveness inherent, Petri nets can be informally applied to any area or system that needs some means of representing parallel or concurrent activities. Methods of analysis for Petri net models can be mainly classified into the following three groups:

• ∙ the coverability tree;

• ∙ the incidence matrix; and

• ∙ reduction or decomposition techniques.

Thus, because of the analysis capability, Petri nets are used widely in some application areas, including distributed software systems, distributed database systems, concurrent and parallel programs, flexible manufacturing/industrial control systems, formal languages, logic inference and decision models. Additionally, performance evaluation and communication protocols are considered to be the successful application areas. Formal methods of protocol engineering, for instance, are based on the analysis of the Petri net model. Generally speaking, the formal methods of protocol engineering mainly provide a standardized guideline for the design state of the whole protocols, which include specification, verification, implementation and testing. For each state, it has a corresponding method and technique. The entire system can be described and analyzed by place/transition net model.

In general, Petri nets are divided into elementary nets, place/transition nets and HLPNs. In order to meet the needs of different applications, some modifications and extensions have been made to the Petri net model. According to ISO/IEC 15909-1 (2002), colored Petri nets (CPN), algebraic Petri nets and predicate/transition nets (PrT-nets), as three subclasses of HLPNs, are widely used in some applications. Additionally, Petri nets have several new variants, including time Petri nets, which are used for performance evaluation and scheduling problems of dynamic systems, and stochastic nets for discrete systems.

2.2 Ontologies

Being a formal knowledge representation method describing a conceptualization of some domain, ontologies can capture both the structure and semantics of information environment. Ontologies describe the nature of the world, and attempt to organize and describe what exists in reality in terms of the properties of, the structure of and the interactions between real-world things. Ontologies have a number of advantages, including adding semantics to data, maintaining knowledge, integrating information, as well as reusing or sharing components (Shanks et al., Reference Shanks, Tansley and Weber2003). Ontologies have been used in diverse application domains such as education, business service, Semantic Web, communications, media, financial services and so on (Cardoso, Reference Cardoso2007).

The first definition proposed by Neches, Fikes & Finin (1991) is that ‘an ontology defines the basic terms and relations comprising the vocabulary of a topic area as well as rules for combining terms and relations to define extension to the vocabulary’. The most widely cited definition in the literature is provided by Gruber (Reference Grube1993), who defined an ontology as ‘an explicit specification of conceptualization’. Guarino and Giaretta defined an ontology as ‘a logical theory which gives an explicit, partial account of conceptualization’ (Reference Guarino and Giaretta1995). Borst slightly altered Guarino’s definition and thought that an ontology is ‘a formal specification of a shared conceptualization’ (Reference Borst1997). According to the study of the definition, Studer et al. (Reference Studer, Benjamins and Fensel1998) defined an ontology as ‘a formal and explicit specification of a shared conceptualization model’. And they interpreted this definition in four levels: (i) conceptualization refers to an abstract model of some phenomenon in the world by having identified the relevant concepts of that phenomenon; (ii) explicit means that the type of concepts used, and the constraints on their use are explicitly defined; (iii) formal refers to the fact that the ontology should be machine-readable; and (vi) shared reflects the notion that an ontology captures consensual knowledge, that is, it is not private of some individual, but accepted by a group.

In general, the knowledge in ontologies is formalized using six kinds of elements: classes, relations, functions, axioms, attributes and instances.

• ∙ Classes also called concepts. A concept is a collection of objects of the domain, representing the basic ideas in the real world. Typically, an ontology can be viewed as a taxonomic hierarchy where some concepts are explained by using others.

• ∙ Relations represent a type of interaction between concepts of the domain and determine the ontology structure. Formally, an n-ary relation R is defined as a subset of a product of n classes C ₁, …, C _n , that is

  $$R\,\subseteq\,C_{1} {\times}C_{2} {\times}\,\ldots\,{\times}C_{n} $$

• ∙ Functions constitute a special case of relations in which the nth element of the relationship is unique for the n−1 preceding elements. Formally, a function F is defined as

  $$F\,\colon\,C_{1} {\times}C_{2} {\times}\,\ldots\,{\times}C_{{n{\minus}1}} \to C_{n} $$

• ∙ Instances are used to represent particular elements of a given class.

• ∙ Attributes describe properties of the individuals of a class. They are usually called data types or concrete domains.

• ∙ Axioms are used to model sentences that are always true and express conditions to be verified by the elements of the ontologies in order to guarantee its correctness. In addition, axioms allow inferring new knowledge, which is not explicitly represented in the ontology.

Ontologies can be represented by extensible markup language (XML), resource description framework (RDF), RDF Schema (RDF(S)) and OWL. But, OWL, as a World Wide Web Consortium (W3C) recommendation standard, is widely used in the description of ontologies. OWL comprises three sublanguages of increasing expressive power: OWL Lite, OWL description logic (DL) and OWL Full. Compared with XML, RDF and RDF(S), OWL has more mechanisms to express the semantics. OWL defines different properties such as Object Properties (link an individual to an individual), Data Properties (link an individual to an XML Schema data type value), Domains and Ranges (properties link individuals from one domain to individuals from another domain), Data types and Restriction Types (Quantifier Restrictions, has Value Restrictions and Cardinality Restrictions) to build an ontology.

Ontologies are becoming more and more popular nowadays. Popular applications of ontologies include knowledge management, natural language generation, enterprise modeling, knowledge-based systems, ontology-based brokers and interoperability between systems (Shanks et al., Reference Shanks, Tansley and Weber2003; Cardoso, Reference Cardoso2007). Since their applications, ontology engineering has attracted an important attention and has been the objects of a lot of study in the field of AI (Staab & Studer, Reference Staab and Studer2004).

3.1 Construction of metamodel from Petri net

A metamodel is a model of the language that captures its essential properties and features (Clark et al., Reference Clark, Sammut and Willans2004). These include the language concepts it supports, its textual and/or graphical syntax, and its semantics (what the models and programs written in the language mean and how they behave). And it is widely believed that the idea of a metamodel is strongly related to the idea of an ontology, which can capture the shared domain knowledge and represent this knowledge. Moreover, a metamodel is considered as an ontology in the field software engineering (Bezivin, Reference Bezivin1998).

In order to share the knowledge of a Petri net, much effort has been spent to construct metamodels from Petri nets. Breton and Bezivin (Reference Breton and Bezivin2001) proposed an explanatory and very exhaustive Petri net metamodel in the context of the Object Management Group’sFootnote ¹ model-driven architecture (MDA) initiative, where a set of concepts and relations of Petri net were defined, such as a series of assertions and the terminology. The Petri net metamodel is made up of three layers, which are listed in the following (Gasevic & Devedzic, Reference Gasevic and Devedzic2006):

• ∙ The first layer mainly defines Petri net metamodel structure, including place, transition, arc, Petri nets itself and mutual relationships between places. It is important to note that the whole Petri net metamodel utilizes Object Constraint Language (OCL) to explain the source and destination of each arc.

• ∙ The second layer is the Petri net situation metamodel, which defines a particular situation of Petri nets, especially making full use of the marking and token concepts.

• ∙ The purpose of Petri nets is to describe the process. In order to present the execution of Petri net, the third layer defines Petri net execution metamodel. In fact, a sequence of particular situation is provided by using a new Petri net concept called move.

With regard to the execution semantics of Petri net metamodel, the action semantics for unified modeling language (UML) was defined by Object Management Group (1998) in order to specify action semantics, but some constraints in OCL were not defined because the constraints alone in OCL do not specify the whole execution semantics.

Based on the extension of the metamodel, the UML profiles were defined by Kogut et al. (Reference Kogut, Cranefield and Hart2002), where the authors supplemented some concepts such as tagged values and constraints on the basis of the UML metamodel. In order to represent Petri net models, Hansen (Reference Hansen2001) proposed a CPN UML profiles. In more detail, the author extended the previous UML metamodel by adding one important concept called stereotypes, which had a major role in Petri net nodes, transition, places and arcs. Further, Gasevic and Devedzic (Reference Gasevic and Devedzic2006) used a UML profile to represent the development of UML-based Petri net ontology, in which some constraints of concepts were the same as previous Petri net metamodels, using the OCL language to specify the semantics.

In addition, a Petri net metamodel, namely Petri Net Markup Language (PNML for short) (Billington et al., Reference Billington, Christensen and vanHee2003; Weber & Kindler, Reference Weber and Kindler2003) is described in the ISO/IEC 15909 standard (ISO/IEC 15909-1, 2002; ISO/IEC 15909-2, 2005). This standard defines an open Petri net metamodel and the PNML aims at facilitating the interchange of any kind of Petri nets between different tools or applications. Moreover, the standard focuses on the representation issues of the Petri net components (such as place, transitions, arc, terms, etc.) and graphical components (colors, labels, etc.). More important, the Petri net metamodel uses OCL to represent constraints between concepts of Petri nets.

Various approaches to construct metamodel from Petri nets are listed in Table 2 with respect to the issues of the expressive power and the reasoning ability of metamodel.

Table 2

Construction of metamodel from Petri net

OCL=Object Constraint Language.

3.2 Construction of ontology from Petri net

A metamodel gives the useful representation of Petri net concepts, but it cannot show how a Petri net model can be used by the Semantic Web directly (Gasevic & Devedzic, Reference Gasevic and Devedzic2006). In order that an ontology can enable sharing knowledge represented by Petri nets on the Semantic Web (Koschmider and Oberweis, Reference Koschmider and Oberweis2005; Gasevic & Devedzic, Reference Gasevic and Devedzic2006, Reference Gasevic and Devedzic2007), new research on how to construct ontology from Petri net has emerged and some researchers have tried to construct a Petri net ontology to share Petri nets on the Semantic Web. Gasevic and Devedzic (Reference Gasevic and Devedzic2006, Reference Gasevic and Devedzic2007) proposed a Petri net ontology with the aim of enabling an effective sharing of Petri nets, solving the drawbacks of the XML-based syntactic approaches. It is interesting to note that this ontology consists of two submodels: one is about core Petri net concepts, and another is Petri net properties. Moreover, two kinds of structuring mechanisms, called pages and modules, are introduced in the core Petri net concepts in order to make Petri net models easy to maintain. Specially, the Petri net ontology utilizes OCL to constrain some concepts such as PlaceReference and TransitionReference. Compared with the above Petri net ontology, Koschmider and Oberweis (Reference Koschmider and Oberweis2005) presented a novel ontology for Petri nets to facilitate the semantic interconnectivity of business processes. Many constructs of core Petri net concepts presented in Koschmider and Oberweis (Reference Koschmider and Oberweis2005) were different from those by Gasevic and Devedzic (Reference Gasevic and Devedzic2006, Reference Gasevic and Devedzic2007), which used the OWL elements Classes, together with the taxonomic construct SubClassesOf and Properties to describe Petri net elements. In this ontology, the classes of fromPlace and toPlace replace the arc and derive subclasses of delete and insert, respectively. Similarly, the class of place has three subclasses: number, indistinguishable that can distinguish arcs between two types of arcs and individualDataItem. Especially, according to the hasMarking property values in class place, the ontology can describe different kinds of Petri nets. For instance, if place contains several tokens and a capacity limit, the Petri net belongs to place/transition net and if place has one or zero tokens, the Petri net is a condition/event net. Moreover, the class of transition is the class logicalConcept with the properties hasOperation and hasAttribute.

However, the Petri net ontology, as mentioned above, can only describe static Petri net models and not fully share all knowledge that Petri nets represent. There are a few new proposals that have emerged relating to ontology construction from Petri net which can describe the static structure and dynamic behavior of Petri net. A HLPN ontology was presented by Vidal et al. (2006), where the static structure and the dynamic behavior of a HLPN were described semantically and declaratively. In more detail, the static model of a HLPN ontology is only a graph, which describes some concepts such as nodes, arcs, transition, algebra, variable and signature and relationships between those concepts. It should be noted that algebra mainly defines the arc explanations and transition guard in order to describe other concepts at a syntactic level. In addition, in order to describe the dynamic behavior of a HLPN, the authors defined a HLPN ontology dynamic model, where HLPNExecution and Firing concepts were mainly defined to represent dynamic processes. For example, HLPNExecution shows an initial status, current status and the status changes between them. And the Firing concept is responsible for the status changes from initial status to current status, and directly contacts with the transition fired. When a transition fires, it must remove tokens from the input places and add new ones to output places. In addition, this ontology is composed of two taxonomies:

• ∙ a taxonomy that describes the main components of a HLPN, capturing the vocabulary and semantics based on the ISO/IEC 15909-1 (2002) standard, including static model and dynamic model;

• ∙ a set of axioms that constrain the creation of the instances of the taxonomy, restricting the range and domain of the relations, and the values of attributes in order to ensure that a HLPN is correctly constructed, avoid the definition of incorrect HLPN, and define how a dynamic model should be executed.

Similarly, based on the International Standard ISO/IEC 15909-1, HLPN ontologies (Vidal & Lama, Reference Vidal and Lama2009; Vidal et al., Reference Vidal, Lama and Bugarin2010) are described, which axiomatize all the aspects of HLPN definition and execution models, including static model, situation model and execution model. In contrast with the early studies of Vidal et al. (Reference Vidal, Lama and Bugarin2006), the HLPN ontologies defined by Vidal and Lama (Reference Vidal and Lama2009) and Vidal et al. (Reference Vidal, Lama and Bugarin2010) give a set of rules that enable both the management of the HLPN static model and its execution and represent the semantics of the execution model.

In Lu et al., (Reference Lu, Sun and Ma2007), a HLPN ontology is divided into Structure-ontology and Algebra-ontology from a modeling perspective for reuse and easy analysis. The Structure-ontology called the static model of a Petri net ontology mainly represents some concepts, relationships between concepts and axioms, where concepts are comprised of place, transition and arc. The Algebra-ontology called the dynamic model of a Petri net ontology mainly contains several important concepts:

• ∙ sort, representing the resource of Petri net, like the token described in Gasevic and Devedzic (Reference Gasevic and Devedzic2006);

• ∙ variables, which are some annotations assigned by arcs;

• ∙ operators, including >, <,=and so on for using the condition judgment;

• ∙ terms, describing the conditions, which are composed of variables and operators.

The values of those concepts change along with the development of a HLPN. It should be noted that HLPN ontologies and common ontologies can be described by DLs. To connect these two kinds of ontologies, some link properties described by e-connection have been defined in the literature. In (Lu et al., Reference Lu, Sun and Ma2007) DLs are applied to indicate the static and dynamic models of Petri nets, representing the semantics of Petri nets and to share knowledge between Petri nets and ontologies. HLPN ontologies enable the reuse of the Petri net because the net graph can be described independently by the algebra that annotates it.

In addition, other efforts in this direction were presented by Takai-Igarashi (Reference Takai-Igarashi2005) and Feng et al. (Reference Feng, Wang and Yin2008). In more detail, Takai-Igarashi (Reference Takai-Igarashi2005) constructed a Cell Signaling Networks Ontology (CSNO) to prevent the Petri net graphs, which represents biological pathways, from being too complicated and unmanageable as well as from being inconsistent. Especially, a HOOPN modeling method based on ontology was presented by Feng et al. (Reference Feng, Wang and Yin2008), in which this method was composed by object identification place that can identify a class, internal object net that can depict the behaviors of a class, and data dictionary that can declare the attributes of a class. The main advantage is to extend Petri nets with object-oriented concepts and provide excellent concepts to model real-world problems. Particularly, compared with Petri net ontologies with graphical representation, as mentioned above, the formal definition of HOOPN can describe accurately and semantically the knowledge that Petri nets represent.

In order to verify the effectiveness of process models, many researchers have proposed methods which model process models with Petri nets and evaluate process models by mapping Petri nets into ontologies for checking completed process models for structure and behavioral properties. For example, Soffer et al. (Reference Soffer, Kaner and Wand2008) demonstrated the use of ontological semantics for Petri nets based on process models. Moreover, the formal definition of Generic Process Models (GPM for short) which provides a process specification semantics based on ontological concepts, is given, and some definitions of Petri nets and their properties are also provided. To verify the completed models, a translation from Petri nets to GPM is established by assigning the semantics to places, transitions and arcs. Besides, Thomas et al. (Reference Thomas, Yessad and Labat2011) proposed an approach of the use of Petri nets to model the accurate behavior of the game player in serious games and the mapping from Petri nets to ontologies to analyze and diagnose learner’s mistakes.

Various approaches that constructing ontology from Petri net are listed in Table 3, which includes corresponding reference, source, target, semantics constraints, mainly models and formal definition. It should be noted that, by the formal definition of Petri net model and ontologies, we can find out the relationships between Petri nets and ontologies.

Table 3

Construction of ontology from Petri net

3.3 Representation of Petri net with ontology description language

In order to reuse and share knowledge of Petri nets, there are other approaches proposed in the literature, which use ontology description languages to represent Petri net concepts and their relationships. Here we summarize these approaches in Table 4.

Table 4

Representation of Petri nets with ontologies description language

F-Logic=Frame-Logic; DL=description logic; FOL=first-order logic; OWL=Web ontology language; FLORA-2=F-Logic tRAnslator .

F-Logic (Frame-Logic) is considered as an ontology language as well as a language for building applications that use ontologies. As an ontology modeling language for knowledge representation, F-Logic accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages (Angele et al., Reference Angele, Kifer and Lausen2009). Furthermore, F-Logic has a model-theoretic semantics and a complete and sound resolution-based proof theory (Kiefer et al., Reference Kiefer, Lausen and Wu1995). Vidal et al. (Reference Vidal, Lama and Bugarin2006) proposed a formal approach of mapping HLPN mathematical specification into an F-Logic language. It is important to note that the F-Logic language is a machine-readable formulation. On one hand, the concepts and relations in the HLPN are represented by means of F-Logic, and on the other hand, a set of axioms that guarantee that HLPNs are correctly created and its execution are formalized in F-Logic. Through a general reasoner, called F-Logic tRAnslator (FLORA-2), it is easy to check whether the axioms are verified or not.

In addition to F-Logic, first-order logic (FOL for short) can also represent and reason Petri net models. FOL, also called first-order predicate calculus, determines a domain of discourse that specifies the range of the quantifiers. Vidal and Lama (Reference Vidal and Lama2009) and Vidal et al. (Reference Vidal, Lama and Bugarin2010) proposed two approaches for representing static and dynamic HLPN models with FOL, where the purpose of FOL is to constrain the axioms of HLPN. Based on the FOL, FLORA-2 (Yang et al., Reference Yang, Kifer and Zhao2003) reasoner is established to provide the sentences and rules to create, modify and delete the instances of the HLPN ontology and a set of queries for reasoning with the Petri net. Besides, Tan (2010) gave a formal approach for describing Petri nets called situation calculus ontologies of petri nets (SCOPE) with FOL, which makes the full use of the strong correspondence between the situation in situation calculus and the marking in Petri nets. Moreover, a set of FOL axioms can support concrete reasoning in Petri nets.

Although FOL is a knowledge representation and ontology language, DL (a subset of FOL) is more popular and accepted because of its powerful expressive ability. DLs are a logical reconstruction of the so-called frame-based knowledge representation languages, with the aim of providing a simple well-established Tarski-style declarative semantics to capture the meaning of the most popular features of structured representations of knowledge (Baader et al., Reference Baader, Calvanese, McGuinness, Nardi and Patel-Schneider2002).

Nowadays, DLs have gained even more popularity due to their applications in the context of the Semantic Web (Baader et al., Reference Baader, Calvanese, McGuinness, Nardi and Patel-Schneider2002; Angele et al., Reference Angele, Kifer and Lausen2009). As the logical foundation of the Semantic Web, DLs have good syntax rules and reasoning ability. Hence, a new method was proposed by Lu et al. (Reference Lu, Sun and Ma2007) in order to translate an information model represented by a Petri net into a knowledge base represented by DL, where the reasoning of the Petri net can be done through the reasoning mechanism of DL. In more detail, Lu et al. (Reference Lu, Sun and Ma2007) defined a DL knowledge base to capture the characteristics of HLPN, where the base consists of an ABox that describes concepts of HLPN, and a TBox that presents axioms that constrain the semantics of concepts in the structure of HLPN. It is important to note that the purpose of the knowledge base is to formalize and analyze the HLPN. In addition, the reasoning of HLPN is implemented through the reasoning of DL.

As an extension of RDF or RDFS, OWL is formed based on DARPA Agent Markup Language (DAML)+ontology inference layer or ontology interchange language (OIL). So far, OWL (Dean et al., Reference Dean, Schreiber, Bechhofer, van Harmelen, Helena and Horrocks2004), a W3C recommendation, has been an ontology description language standard and is the fundamental support for the Semantic Web. Moreover, the main advantage of OWL is to provide more primitives to support richer semantic representation and reasoning. Therefore, in order to implement the representation of and reasoning about Petri nets, several approaches based on OWL have been proposed as will be introduced in the following.

In order to enable semantic information exchange between two semantic business models, Brockmans et al. (Reference Brockmans, Ehrig, Oberweis and Sduder2006) proposed an approach for representing Petri nets with OWL. Moreover, Gasevic and Devedzic (Reference Gasevic and Devedzic2006, Reference Gasevic and Devedzic2007) gave the OWL definition of the concepts for the core Petri net ontology and the ontologies of upgraded Petri nets (Strbac, Reference Strbac2002). Further, the OWL ontologies attached to the Petri net model were defined by Wang et al. (Reference Wang, Bai, Li and Huang2007), where test data of Petri nets can be generated by OWL reasoning. Besides, Ma and Xu (Reference Ma and Xu2009a, Reference Ma and Xu2009b) discussed a novel approach for describing Petri nets with PNML in combination with OWL. Specifically, a Petri net structure is described with PNML, and place elements have their semantic specification with OWL. In addition, the ontology reasoner can smoothly achieve the automatic sharing composition operation of Petri nets. Here, the Petri net is applied to model and analyze dynamic behavior relationships on the Semantic Web.

OWL DL, as the sublanguage of OWL, is equivalent to DL SHOIN (D) (Hustadt et al., Reference Hustadt, Motik and Sattler2004), which provides a good balance of expressive and reasoning power. For example, Zhang et al. (Reference Zhang, Ma and Ribaric2011) gave the formal definition of Petri nets and OWL DL ontologies, and represented Petri nets with OWL DL ontologies by mapping some key features of Petri nets into classes, properties and axioms of OWL DL ontologies.

As information imprecision and uncertainty exist in many real-world applications such as manufacturing and information systems, the Petri net model is extended to a fuzzy Petri net (FPN) model to represent uncertainties. In order to share and reuse the FPNs, Zhang et al. (Reference Zhang, Ma and Yan2012) proposed a fuzzy OWL ontology approach for representing FPNs, where they map the key features of FPNs into fuzzy classes, fuzzy properties, fuzzy individuals and fuzzy axioms of fuzzy OWL ontologies. By means of the existing fuzzy ontology reasoner DeLoean (Bobillo & Delgado, Reference Bobillo and Delgado2007), reasoning on FPNs is implemented.

4.1 Mapping ontologies into Petri nets

Mapping ontologies into Petri nets means the use of Petri nets to model knowledge that ontologies represent to share knowledge between them. On one hand, Petri nets can dynamically describe ontology knowledge, and on the other, they provide some techniques to analyze the ontology models. To enhance knowledge reusability and sharability over different applications, Liu (Reference Liu2006) proposed a framework, called TTIPP (Task analysis, Task ontology, IDEF0, Petri net, PNML), in which Petri nets are used to completely model a task ontology (Guarino, Reference Guarino1998) and formally specify the terminology associated with a problem type. By means of an intermediate model, namely the IDEF0 model (Feldmann, Reference Feldmann1998), the task ontology is converted into a Petri net model. Compared with the IDEF0 model, the greatest advantage of the Petri net model is the use of its time-based function, including cumbersomeness, ambiguity in activity specification and its static nature.

As a popular process modeling technique, the use of Petri nets can provide an abundance of analysis techniques to evaluate process modeling languages. However, an analysis of the strengths and weaknesses of Petri nets for modeling business processes cannot be conducted. An approach to map ontologies into Petri nets is proposed, which can evaluate the representational capability of Petri nets. The representation mapping from the BWW ontology (Bunge, Reference Bunge1977; Wang & Weber, Reference Wang and Weber1993) to a Petri net model is built by Recker and Indulska (Reference Recker and Indulska2007) in order to establish a comprehensive understanding of the ontological completeness and clarity that Petri nets exhibit. In more detail, the mapping is implemented by converting BWW real-world concepts such as thing, class, state law, lawful state space, event, transformation, stability condition, acts-on, unstable state, internal event and well-defined event into Petri net concepts. Based on the representation mapping, the evaluation shows that there are a number of representational limitations of Petri nets including construct deficit, construct redundancy and construct overload.

Recognition of semantics and information extraction are two important issues in the process of service composition. In order to solve these issues, a Petri net model of ontology-based semantics service composition is proposed by Yang and Zhou (Reference Yang and Zhou2009). In their paper, the formal definitions of ontology, service, semantic service composition and Petri net of service composition are given. By designing grammar detection and semantics authentication, a Petri net model of service composition is implemented to improve search speed of service composition. In particular, a greedy genetic algorithm is applied to optimize Petri net models.

4.2 Mapping ontology description languages into Petri nets

Information on the Semantic Web is described with ontology description languages, such as OWL, RDF and OWL-S. Since Petri nets have a powerful capability to model events and states in information processing systems and to formally analyze the processes (Nielsen & Sassone, Reference Nielsen and Sassone1988), the aim of mapping ontology description languages into Petri nets is to use the formal analysis of Petri nets to supplement the functions of ontologies. Nowadays, OWL-S and DAML-S (DAML-Service) are used to specify the process of Web service application. Thus, the representation of the OWL-S and DAML-S with Petri nets has been the focus of a great deal of research.

A formal approach for modeling OWL-S service choreography with HLPNs is discussed by Vidal et al. (Reference Vidal, Lama and Bugarin2007), in which each OWL-S is transformed into a Petri net. As consequence of this approach, the Petri net can be used to check the correctness of the OWL-S choreography model by verifying some Petri net properties and can interact with services. Moreover, Wang et al. (Reference Wang, Bai, Li and Huang2007) proposed a transformation from OWL-S processes to Petri net models:

1. i. one perform action is mapped to a transition;

2. ii. inputs and preconditions of the perform action are mapped to the places holding tokens pointing to the transition;

3. iii. outputs and effects of the perform action are mapped to output arcs and places of the transition.

Based on the Petri net model of OWL-S process and ontology reasoning, a test case (test process and test data) generation approach is presented. In particular, the correctness of a Petri nets is guaranteed by defining the marking reachability and construct inclusion, and a prototype system TCGen4WS is implemented. Besides, Brogi et al. (Reference Brogi, Corfini and Iardella2007) developed a tool – named OWLS2PNML – that translates OWL-S descriptions into Petri nets described by a PNML (Weber & Kindler, Reference Weber and Kindler2003) file. The main contribution of OWLS2PNML is to make it possible to analyze and verify OWL-S and reason with heterogeneous services.

In order to automatically describe, simulate and verify Web services, Narayanan and McIlraith (Reference Narayanan and McIlraith2002) proposed Petri net models for describing the operational semantics of DAML-S, a logic language describing Web services. In addition, they defined the semantics of atomic processes by situation calculus axioms, map the situation calculus axioms into the corresponding Petri net structure, and describe the net structures for various control constructs defining composite processes. Specifically, this approach extends the basic Petri net formalism with typed arcs, hierarchical control, durative transitions, parameterization, typed (individual) tokens and stochasticity. Moreover, a tool that maps a DAML-S description of a Web service into a Petri net is implemented to support the various verification and performance analysis. Moldt and Ortmann (Reference Moldt and Ortmann2004) implemented the Petri net semantics of DAML-S by means of a tool called DaGen, in which a DAML-S description is automatically translated into a HLPN. As a plug-in for reference net workshop (RENEW) (Kummer et al., Reference Kummer, Wienberg and Duvigneau2003), DaGen provides a Petri net simulator that allows for different views, including control flow, data and execution.

DL only expresses and reasons with static knowledge, and does not meet the demand of processing dynamic knowledge. Faced with the deficiency, many researchers proposed dynamic DL (DDL), which extends the traditional DL with dynamic aspects and combines representation of and reasoning with static knowledge and dynamic knowledge (Shi et al., Reference Shi, Dong, Jiang and Zhang2005). Since DDL does not describe and analyze relationships among actions, especially concurrent relationships, and Petri nets have powerful capabilities to describe these relationships, the use of Petri nets to model DDL can achieve knowledge sharing between Petri nets and DDL. Ma and Xu (Reference Ma and Xu2009a, Reference Ma and Xu2009b) proposed a method for modeling and analyzing DDL action relationships with Petri net models, which supplements the function of description and analysis of DDL action theory. In more detail, the transformation from DDL actions to the Petri net model includes four steps:

• ∙ considering each atomic action and its condition descriptions as a transition and places of Petri nets, respectively;

• ∙ obtaining the Petri net incidence matrix corresponding to the DDL description;

• ∙ using DL reasoning technology to find equivalent condition descriptions of atomic actions;

• ∙ executing sharing synthesis operation of Petri nets among actions with their Petri nets incidence matrixes and then getting the Petri net model of DDL actions.

Basically, in the mapping of DDL actions to Petri net model, the actions and the relationships among actions are transformed to an equivalent Petri net model.

In addition, Yim et al. (Reference Yim, Joo and Lee2011) proposed a method for translating the RDF model into a CPN, which represents the semantics of the RDF model in the CPN by mapping the classes, resources, literals, statements and properties of the RDF model onto CPN places and representing the relationships between those classes and properties as token transitions in CPN. Based on the proposed method, an application can draw an inference with a CPN model and answer RDF queries, verify the correctness of transformation by CPN tools. In particular, a prototype database system for demonstrating the method is also implemented.

Logic programming defined by FOL, is also applied to knowledge representation, and PrT-nets can provide a uniform mathematical formalization of knowledge presentation and control implementation for inference. The combination of logic programming and PrT-nets was described by Murata and Zhang (Reference Murata and Zhang1988), where a PrT-net is proposed to represent and analyze a logic program. The syntax, transformation procedure and semantics are also discussed. Through the transformation, a Horn clause program can be automatically translated into a PrT-net and various inference problems in the program are also converted to problems in the corresponding Petri net model. Similarly, Chuang et al. (1993) proposed a method for modeling Horn clauses and first-order predicate logic with Petri nets, where the logical inference was implemented by computing T-invariants. In particular, Liu et al. (1994) addressed the topic of modeling the semantics of logic program with PrT-nets in order to realize the feature of non-monotonic inference.

Petri nets not only have the powerful capability to model logic programs defined by FOL, but can also describe OWL DL ontologies and semantic web rule language (SWRL) rules to realize knowledge sharing between ontologies and Petri nets. For example, a novel approach for reasoning with SWRL rules and OWL ontologies based on PrT-nets was presented by Zhang et al. (Reference Zhang, Meng, Jiang and Pang2006). This work was implemented by transforming OWL DL and SWRL rules into PrT-nets, which requires four steps:

• ∙ mapping OWL axioms such as constants, class and property to PrT-net model consisting of a transition between two places with the free variables universally quantified at the arc;

• ∙ mapping OWL class constructors including conjunction, disjunction, universal restriction, existential restriction, complementof and cardinality restrictions to PrT-net models;

• ∙ translating SWRL rules to PrT-net models;

• ∙ computing T-invariants to realize rule inference.

Based on the discussions above, the approaches that map ontology description languages to Petri nets are summarized in Table 6, which contains corresponding references, sources (ontology description languages), targets (Petri nets), verification, implementation and inference. In the next section, we elaborate the applications of knowledge sharing between Petri nets and ontologies.

Table 6

Mapping ontology description language into Petri net

DAML-S=DARPA Agent Markup Language-Service; HLPN=high-level Petri net; OWL-S=Web ontology language for Web Service; DDL=dynamic description logic; RDF=Resource Description Framework; CPN=colored Petri net; PrT-net= predicate/transition net; FOL=first-order logic.

5.1 Applications in business process management

In BPM, building business process capabilities is seen as a major challenge for senior executives. Due to the rapid growth of electronic market activities, it is needed to establish interconnectivity of business processes in order to reduce communication efforts. An approach for representing Petri nets with OWL was described by Brockmans et al. (Reference Brockmans, Ehrig, Oberweis and Sduder2006), where the aim of these approaches is to enable semantic information exchange. Also a background ontology is modeled in UML for improving the semantic alignment of business process, and the alignment of Petri nets by making use of existing technology for ontology alignment was described for solving ambiguity issues of Petri nets. Similarly, Koschmider and Oberweis (Reference Koschmider and Oberweis2005) addressed semantic representation of distributed business processes, in which semantic metadata for business processes modeled with Petri nets is defined by mapping structured data in Petri nets into the ontology elements described in OWL. In addition, the process data contained in places was reasoned about using OWL DL.

In addition, Recker and Indulska (Reference Recker and Indulska2007) proposed an evaluation of business process modeling by mapping BWW constructs based on an ontology into Petri net constructs, which facilities a deeper understanding of the capabilities and weaknesses of process modeling technique and ultimately leads to an increased quality of process models. The mapping from Petri net constructs into GPM interpretation based on ontological constructs was proposed by Soffer et al. (Reference Soffer, Kaner and Wand2008), which, in turn, can provide modeling rules for developing process modeling, and avoid process modeling problems by the verification of the process models.

5.2 Applications in Web service

Web services in the Semantic Web (Berners-Lee et al., Reference Berners-Lee, Hendler and Lassila2001), called Semantic Web services, are described through ontologies (Gomez-Perez et al., Reference Gomez-Perez, Fernandez-Lopez and Corcho2003), which formally represent service features by using a semantic markup language that follows a logical paradigm (such as a DL). This description will allow agents to understand what the service is and facilitate its discovery, composition and invocation.

One of the most often used ontologies to specify Semantic Web services is OWL-S (Martin, Reference Martin2004), which uses the OWL (Dean et al., Reference Dean, Schreiber, Bechhofer, van Harmelen, Helena and Horrocks2004) language capabilities to represent the property and function of services and enables agents to make inferences about it. OWL-S is defined as a W3C standard to provide a computer-interpretable description of the services, service access and service composition.

Currently, Petri nets are widely applied in the field of Web services because Petri nets have the ability to model Web services and execute and analyze the process of services. For example, Petri nets can solve the problem of semantics recognition and information extraction in the process of service composition. Some researchers utilize Petri nets to model Web services, which are mainly applied in Web service testing and Web service composition. In the following, we briefly introduce these applications.

5.3 Applications in some particular domains

While there is a lot of research on sharing knowledge between Petri nets and ontologies, little research exists that incorporates Petri nets and ontologies in emerging applications. Several such applications are presented as follows.

In biological networks, Petri nets are widely used because they offer a concise graphical representation of biological concepts and the quantitative analysis of dynamical behaviors of biological entities. But some inconsistencies appear in existing Petri net modeling of cellular networks. Thus, it is necessary to use other methods to semantically describe Petri net models to develop an ontology and then share Petri net domain knowledge. In order to standardize Petri net representations, in this area, the CSNOs was proposed by Takai-Igarashi (Reference Takai-Igarashi2005), which gave the definition of the process of signaling. Based on the ontology, a Petri net can represent a signaling network without ambiguity by using a denotation, consisting of names of reactant, external states of reactant and components of a complex.

In the Incident or Hazard Command System’s knowledge management, a large amount of poor, incomplete and inconsistent knowledge exists in the entire system, resulting in reducing the system performance. In order to reduce the brittle nature of traditional knowledge-based system and enhance the knowledge reusability and sharability, Liu (Reference Liu2006) proposed a methodology, called TTIPP, which built up a task ontology to represent task analysis and then systemically analyzed the process with IDEF0 and Petri nets.

A serious game, designed for the purpose of solving some problems, is actually a simulation of real-world events or processes, used in business training, education, health care, public policy and so on. For the purpose of evaluating the effectiveness of serious games, an approach for tracking a player’s actions was described by Thomas et al. (Reference Thomas, Yessad and Labat2011), which utilized Petri nets to model and evaluate serious games. In addition, a domain and game action ontology, as a complement to Petri nets, was constructed to specify the actions of the learner, giving satisfactory results.