Modelling Workflow Patterns

Petri net data model, Petri net processing model and syntaxes for Topic Maps and OWL

Version 0.2 R 1.0

Last update: 20.06.2006 14:31:15

Authors:

Lutz Maicher (maicher@informatik.uni-leipzig.de)

Martin Böttcher (boettcher@informatik.uni-leipzig.de)

Introduction

This document defines a Petri net data model (PNDM) derived from the formal specification of Petri nets in [Aa98] and based on the same metamodel as [infoset]. Interpreter has to process these Petri nets according to application specific constraints. These constraints are defined by Petri net processing models (PNPM). This document defines one of many possible PNPMs. This is intended to be used for the definition of Modelling Workflow Patterns (MWP) [MB06a, MB06b].

Furthermore, syntaxes (constraints) for Topic Maps and OWL are introduced. The PNDM and PNPM allow to properly represent any kind of Workflows with these syntaxes, including MWPs.

Summarised, this document defines:

A. Terminological specifications of workflow definitions based on Petri nets,

B. the Petri net data model (PNDM) based on the same metamodel as [infoset],

C. Definition of MWPs as a Petri net processing model (PNPM)

D. Topic Maps syntax for Petri nets including a mapping from TMDM to PNDM

E. OWL syntax syntax for Petri nets including a mapping to the PNDM and

F. Some Operator Specifications in the appendix

This document is not an official standard.

A Terminological Specifications

In the following the terminological specifications of workflow definitions based on Petri nets are introduced. These definitions base on [Aa98].

Definition Petri net. A Petri net is a triple :

· is a finite set of places,

· is a finite set of transitions and

· is a set of arcs (flow relationships).

A transition bears two kinds of information: a set of conditions and one operator which has to be executed. The operator can only be executed in the case all conditions hold.

Note: In colored Petri nets arcs between transitions and places might have weights and transitions and places might have capacities. The following data model implements nets with unlimited capacity and un-weighted arcs.

A place is called an input place of a transition iff there exists a directed arc from to . A place is called an output place of a transition iff there exists a directed arc from to . The set of input places of a transition is denoted as . The same notation is used for input transitions. Similar to output transitions, the set of output places of _{are denoted as .}

Definition Workflow net. A Petri net is a Workflow net (WF-net) if and only if:

· has two special places: and . Place is a source place: . Place is a sink place: .

· If we add a transition to which connects place with (i.e. and ), then the resulting Petri net is strongly connected.

Note: A Petri net is strongly connected iff for every pair of nodes (i.e. places and transitions) and , there is a path leading from to .

A workflow net can be interpreted as a view on a Petri net. An executed workflow is called case.

Definition workflow. A workflow is defined as a tuple of:

· a workflow net and

· a set of cases (the execution instances of the workflow net).

At any time a place contains zero or more tokens.

Definition token. A token is defined as a set of characteristics. A token can be contained in max. one place and belongs exactly to one case.

Definition characteristic. A characteristic is defined as a tupel _of:

_·_{a key and}

_·_{a value .}

A case is defined by the set of all tokens belonging to the case. The state, often referred to as marking, of a case is the distribution of all tokens belonging to the case over places.

Definition case. A case _{is defined by the set of tokens belonging to
the case.}

Transitions are the active components of a Petri net: they change the state of cases according to the following firing rule:

· A transition is said to be enabled in case iff each input place of contains at least one token of . A set of tokens fulfilling this requirement is called the enabling set in .

· A transition enabled in may fire. The transition fires, iff the information represented by an enabling set fulfils all conditions of and the operator represented by can be executed successfully. If transition fires in case , then consumes all tokens of belonging to from and produces one token of in each place of .

Note: If after the execution not all tokens from s can’t be consumed from , a rollback has to be executed and a new enabling set has to be created.

Note: In the following, only pre-conditions will be considered because post-conditions can always be modelled using pre-conditions (at least by introducing new transitions).

B Petri Net Data Model (PNDM)

In the following the Petri net data model is defined. The deserialisation of workflow syntaxes (see D for Topic Maps and E for OWL) results in a PNDM instance. PNDM instances have to be interpreted according to the governing Petri net processing model. The processing model in C defines, how a PNDM instance should be interpreted and processed as a MWP.

Figure 1: Inheritance diagramm

Figure 2: Dependency diagramm

B-1.1 Metamodel of the PNDM

The metamodel of the PNDM is the same as that used by the XML Information Set [Infoset]. An instance of this data model consists of a number of information items, each one of which is an abstract representation of a Petri net construct (see B-1.3). Every information item is an instance of some information item type, which specifies a number of named properties which the information item of the given type shall have.

Note: A formal navigation and constraint language is defined by [DNB06].

B-1.2 The fundamental types

The values of information item properties may be either other information items, or values of one of the types defined below (see [TMDM]):

String

Strings are sequences of Unicode scalar values (see [Unicode] and [ISO 10646]). Strings are equal if they consist of the exact same sequence of Unicode scalar values.

Set

Sets are collections of zero or more unordered elements that contain no elements that are equal to each other. In this data model the elements of a set are always information items or strings. Two sets are equal unless there exists an element in one set for which no equal element can be found in the other.

Null

Null is a type of exactly one value, used to indicate that a property has no value; it does not necessarily indicate that the value of the property is unknown. Specifically, null has the same semantics as No Value in [Infoset]. In this model null can never be contained in a set. Null is distinct from all other values (including the empty set and the empty string); it is only equal to itself.

Locator

Locators are strings conforming to some locator notation. Locators are equal if they consist of the exact same sequence of Unicode scalar values.

B-1.3 Petri Net Construct

A Petri net construct is an information item which is an abstract super class of all information items defined by this data model. A Petri net construct is: a Petri net, a workflow, a case, a transition, a place, a token, a condition, a characteristic. This class should simplify the definition of general properties of information items.

[item identifiers] A set of locators. The item identifiers of the Petri net construct.

Note: An item identifier is a locator assigned to an information item in order to allow it to be referred to.

Constraint: It is an error for two different Petri net constructs to have strings that are equal in their [item identifiers] properties.

[characteristics] A set of characteristic items or null. Represents the characteristics of the Petri net construct.

Note: The label of an information item is a special characteristic with the pre-defined key: http://psi.semports.org/pndm/label.

B-1.4 Petri Net Item

A Petri net is a set of places and transitions connected by arcs. A Petri net item is a Petri net construct with the following properties:

[transitions] A set of transition items. Represents all transitions in the Petri net.
[places] A set of place items. Represents all places in the Petri net.
[workflows] A set of workflow items or null. Represents all workflows which are defined on top of the Petri net.

B-1.5 Workflow Item

A workflow is a specific view on a Petri net. It is defined by a start place and an end place. An instance of this process is called case and represented by a case item (see B-1.6). A workflow item is a Petri net construct with the following properties:

Note: In the current version of the data model it is not possible to specify start states of cases. A start state might be represented by a set of token classes. Instantiating a case implies instantiating these tokens in the start place.

[start place] A place item. Represents the start place of the workflow.
[end place] A place item. Represents the end place of the workflow.
[cases] A set of case items or null. Represents all cases of the workflow.

Note: In the case the value of the property [cases] is null, none instances of the workflow exist at the moment.

[parent] A petri net item. The Petri net the workflow is a view about.

Computed value: The Petri net item which is the value of the property [parent] of the place item in [start place].

Constraint: The Petri net item which is the value of the property [parent] of the place item in [end place] must be eq[LM1] ual to the value of the property [parent].

Note: The definition of equality of Petri net constructs is left to the processing models.

Constraint: A workflow item does only represent a valid workflow of the Petri net specified by the property [parent] iff the minimal requirements of the workflow definition in part A are fulfilled.

B-1.6 Case Item

A case is an instance of a specific workflow. The state of a case is defined by the location and the state of all tokens belonging to the case. A case item is a Petri net construct with the following properties:

[tokens] A set of token items. Represents all tokens belonging to the case.
[parent] A workflow item. Represents the workflow the case is an instance of.

Computed value: The workflow item the property [cases] contains this item

B-1.7 Transition Item

A transition represents an operator. In the case a transition is enabled (all incoming places host at least one token of the same case and all pre-conditions are fulfilled), the operator has to be executed and the transition fires. A transition item is a Petri net construct with the following properties:

Note: Operators are represented by characteristic items with specific keys. The definition of the keys is left to the processing model.

[successors] A set of place items. Represents all outgoing places of the transition.
[predecessors] A set of place items. Represents all ingoing places of the transition.

Computed value: The place items the property [successors] contains this item.

[conditions] A set of condition items or null. Represents all pre-conditions of the transition.

Note: Conditions are represented in the condition items as strings. The interpretation of conditions is completely left to the processing models.

[parent] A Petri net item. The Petri net the transition belongs to.

Computed value: The Petri net items the property [transitions] contains this item.

B-1.8 Place Item

A place holds tokens. A place item is a Petri net construct with the following properties:

[successors] A set of transition items or null. Represents all outgoing transitions of the place.
[predecessors] A set of transition items or null. Represents all ingoing transitions of the place.

Computed value: The transition items the property [predecessors] contains this item.

[tokens] A set of token items or null. Represents all tokens a place currently holds.
[parent] A Petri net item. Represents the Petri net the place belongs to.

Computed value: The Petri net item the property [places] contains this item.

B-1.9 Condition Item

A condition is a string. The interpretation of a condition is governed by the applied processing model. According to the applied interpretation, it is decidable whether a condition holds in a given state of a case, or not. A condition item is a Petri net construct with the following properties:

[condition] A string. Represents the condition.
[parent] A transition item. Represents the transition the condition belongs to.

Computed value: The transition item the property [conditions] contains this item.

B-1.10 Token Item

Tokens flow through a Petri net. A case is represented by a set of tokens. The state of a case is represented by the position and the state of these tokens.

[case] A case item. Represents the case the token belongs to.

Computed value: The case item the property [tokens] contains this item.

[place] A place item or null. Represents the place currently holding the token.

Computed value: The place item the property [tokens] contains this item.

Note: In the case the value of the property [place] is null, the current token item might be a working copy which can be used for any purposes. A token item is always assigned to a case.

B-1.11 Characteristic Item

A characteristic is a key/value-pair for generic representation of properties. Characteristics will be used by different processing models in different ways. Their interpretation depends on the applied processing model. A characteristic item is a Petri net construct with the following properties:

Note: The property [characteristics] of the characteristic Item should be always null.

[key] A string. Represents the key of the property.

Note: Constraints about the uniqueness of the value of the property [key] are left to the processing models.

[value] A string or null. Represents the value of the property.
[parent] An Petri net construct. The Petri net construct the property belongs to.

Computed value: The Petri net construct the property [characteristics] contains this item.

C MWP Petri net processing model (PNPM)

A Petri net processing model (PNPM) defines how cases defined in the instances of the PNDM should be processed (see C-C.1), including application specific constraints which have to hold.

C.1 Processing a Case

For each transition which is not enabled in the current case try to create an enabling set (see C-1.1).

Note: A transition is enabled in the current case if it has a characteristic item in its property [characterisitics] which has “PSI_enabled set” as value of the property [key] and an item identifier of the case item as value of the property [value].

The enabled transition t is labeld as enabled transition by adding a new characteristic item in the property [characteristics] of t with the string ”PSI_enabled” as value of the property [key] and an item identifier of the case item c as value of the property [value].

The operator of the enabled transition has to be executed. A reference of the operator is given by a characteristic item in the property [characteristics] which has the string “PSI_operator” as value of the property [key]. The reference of the operator is given by the value of the property [value] of this characteristic item. The PSI mechanism [PS03] is used for referencing the operators.

In the appendix some operator definitions are given.

Results of the operators are always stored as characteristics of the token item representing the enabling set. The operator definitions disclose how the results are stored exactly (key schema).

The operands of the operator are given by other characterstic items. The operator definitions define the keys of the according operands. The values of the property [value] of the according characteristic items are the according operands. The operand strings have to be instantiated according (see C-1.2).

The results of the operator have to be stored as characteristic items of the merged token item which represents the enabling set. The specification how the result has to be stored is completely left to the operator definitions which has to be implemented by interpreters.

In the case the operator has been executed successfully, it has to be tested, whether the enabling set is still a valid enabling set. (It is possible, that in the time the operator has been executed a cocurrent transition has been consumed some tokens belonging to the enabling set[Ma2] .)

If the enabling set is still a valid enabling set, all token items of the enabling set has to be deleted in the predecessors of the current transition and a copy of the token item representing the enabling set has to be set to the property [tokens] of all place items which are value of the property [successors] of the current transitions.

The end of the case has been reached, if one of the place items in the property [successors] is the same place item as the value of the property [end place] in the workflow item the current case belongs to.

C-1.1 Creating an enabling set

If for a transition item t for all place items p in the property [predecessors] can be found a token item to in the property p.[tokens] where the value of the property to.[case] is always the same case item, an enabling set of all to has to be created.

In this processing model an enabling set is represented as a merged token item of all token items in the enabling set. Merging of token items is defined in C-1.4.

C-1.2 Instantiation of strings

A string is always instantiated in the context of a token item. A part of a string matching the pattern “%[^%]+” represents the value of a characteristic of this token item.

Example: Given a query “instance-of($INSTANCE, %id24.type%)?” the part of the string “%id24.value%” should be replaced by the value of a characteristic item of the token item. It should be taken the value of the property [value] of the characteristic item where the value of the property [key] is the string “id24.value”.

The string matching the “[^.^%]+” is the value of the property [key] of a characteristic item c which is in the property [characteristics] of the given token item t. If there is no such characteristic item available, an error occurred.

The part of the string matching the whole pattern has to be replaced by the value of the property [value] of the characteristic item c.

If the value of the property [value] of the characteristic item c is null, the part of the string matching the whole pattern has to be replaced by http://psi.semports.org/pndm/null

C-1.3 Deciding conditions

A condition is a string which has to be evaluated to a Boolean value. A condition is the valiue of the property [condition] of a condition item. Conditions are clauses: disjunctions of literals.

Note: All condition items which are value of the same property [conditions] of a transition items are a conjunction. But this is not in the focus of this section.

A string is a valid condition if it matches the following pattern “($.$[:space:OR:space:]*)+”. If a string is the value of the property [conditions] of a condition item and it does not match the defined patter, an error occurred.

“OR”, “TRUE” and “FALSE” are not case sensitive.

Note: Conditions always base on string equivalence, comparison of numerical values is not possible. Such interpretations are left to the operators.

In a first step the condition has to be instantiated according (see C-1.2).

In a second step each pattern “TRUE” has to be replaced by “http://psi.semports.org/pndm/TRUE”.

In a third step each pattern “FALSE” has to be replaced by “http://psi.semports.org/pndm/FALSE”.

In a fourth step each literal has to be decided. Each part of the string separated by OR is a postive literal if it matches the following pattern: “$[.^=]+\=[.^=]+($”.Each part of the string separated by OR is a negative literal if it matches the following pattern: “$[.^=]+\\\=[.^=]+($”.

If the part of the string is a positive literal it is evaluated to true if the part left of the symbol “=” is equal to the right part. Otherwise it is evaluated to false.

If the part of the string is a negative literal it is evaluated to true if the part left of the sequence “\=” is not equal to the right part. Otherwise it is evaluated to false.

If one literal of a condition is evaluated to true, the whole condition is evaluated to true. Otherwise the condition is evaluated to false.

C-1.4 Merging Token Items[Ma3]

To merge a token item A into a token item B the following procedure has to be applied:

Add all characteristic items of the property [characteristics] of A to the property [characteristics] of B. Because the value of the property [characteristics] is a set, equal characteristic items will be eliminated (not added from A to B). Equality of characteristic items is defined in C-1.5.

Constraint: Two token items A and B can only be merged if the values of the property [case] in A and B are identical.

Constraint: Two token items A and B can only be merged if the values of the property [place] in A and B are identical.

C-1.5 Equality of characteristic items

Two characteristic items A and B are equal if:

The values of the property [key] in A and B are identical strings.
The values of the property [value] in A and B are identical strings.
If the values of the property [parent] in A and B are token items, the value of the property [case] of the token items must be the same case item.
If the values of the property [parent] in A and B are other Petri net constructs, these Petri net constructs must be identical.
The values of the property [characteristics] in A and B are identical.

D MWP Topic Maps Syntax

This section introduces constraints for MWP Topic Maps Syntaxes. There exist several exchange formats for Topic Maps (XTM 1.0, XTM 2.0, LTM, CTM, AsTMa=), so it is left to the Topic Maps author to choose one of them. The only requirement to the used syntax is that the deserialisation into TMDM instances (and vice versa) should be properly defined and implemented.

The appendix of this section provides an informative OSL schema. A XTM topic map which is valid against this schema represents a MWP.

D-1.1 General Remarks

In the following only constraints are defined which specify Topic and Association Classes. Topic Map constructs which fulfil the specified constraints represent the defined Petri net constructs.

For the topic classes transition and places and for the association class dependency mappings are defined. These mappings specify how TMDM instances valid to the defined constraints have to be mapped to PNDM instances.

The phrase “In the PNDM topic map construct A requires petri net construct B” means, that the Petri net construct of the indicated type has to be created and an unique locator (within the context of the current PNDM instance) has to be added to the property [item identifiers] of the created item. The property [characteristics] of the created item has to be set to null.

D-1.2 Petri Net

Creating a PNDM instance requires a Petri net item PN.

D-1.3 Topic Class: Transition

A transition is represented by a topic with the following characteristics:

It might have a base name in the unconstraint scope. This name describes the transition in detail.
It has to play the role instance in an instance-of relationship (see D-1.11). The role class has to play a Topic with a subject identifier http://psi.semports.org/pndm/transition.
It has to play the role successor in at least one arc relationship (see D-1.10). The role predecessor has to be played by a Topic representing a place (see D-1.4).
It has to play the role predecessor in at least one arc relationship (see D-1.10). The role successor has to be played by a Topic representing a place (see D-1.4).
It might have one or zero internal occurrences typed as label (see D-1.5).
It might have several internal occurrences typed as operand (see D-1.7).
It must have an internal occurrence typed as operator (see D-1.6)
It might have internal occurrences typed as condition (see D-1.8).

In the following the mapping from the TMDM to the PNDM is defined (the mapping of the arc relationship is defined in D-1.10):

Transition. In the PNDM instance, each topic item T fulfilling the defined constraints requires a transition item T. All values of T.[subject identifiers] and T.[item identifiers] are set to T.[item identifiers]. This transition item is added to PN.[transitions].

Description. The topic item T might have a topic name item TN in it its property [topic names], where TN.[scope] is null (unconstrained scope). In the PNDM instance, this topic name item requires a characteristic item C. The value of the property C.[key] is set to http://psi.semports.org/pndm/description. The value of the property C.[value] is set to TN.[value]. This characteristic item C is added to T.[characteristics].

Operator. The topic item T has an occurrence item O in its property [occurrences], where O.[type] contains a topic item with http://psi.semports.org/pndm/operator in its property [subject identifiers]. In the PNDM instance, this occurrence item O requires a characteristic item C. The value of the property C.[key] is set to http://psi.semports.org/pndm/operator. The value of the property C.[value] is set to O.[value]. This characteristic item C is added to T.[characteristics].

Operand. The topic item T may have different occurrence items O in its property [occurrences], where O.[type] contains a topic item OT and the property OT.[types] contains a topic item with http://psi.semports.org/pndm/operand as value of its property [subject identifiers]. In the PNDM instance, each occurrence item O requires a characteristic item C. The value of the property C.[key] is set to one value of OT.[subject identifiers]. The value of the property C.[value] is set to O.[value]. The characteristic items C are added to T.[characteristics].

Condition. The topic item T might have occurrence items O in its property [occurrences], where O.[type] contains a topic item with http://psi.semports.org/pndm/condition in its property [subject identifiers]. In the PNDM instance, each occurrence item O requires a condition item C where C.[condition] is set to O.[value]. The condition items C are added to T.[conditions].

Label. The topic item T might have an occurrence item O in its property [occurrences], where O.[type] contains a topic item with http://psi.semports.org/pndm/label in its property [subject identifiers]. In the PNDM instance, this occurrence item O requires a characteristics item C where C.[key] is set to http://psi.semports.org/pndm/label and C.[value] is set to O.[value]. The characteristic item C is added to T.[characteristics]. Additionally, C.[item identifiers] is set to O.[value].

D-1.4 Topic Class: Place

A place is represented by a topic with the following characteristics:

It might have a base name in the unconstraint scope. This name describes the place in detail.
It has to play the role instance in an instance-of relationship (see D-1.11). The role class has to play a Topic with a subject identifier http://psi.semports.org/atm#t_place.
It might play the role successor in an arc relationship (see D-1.10). The role predecessor has to play a topic representing a transition (see D-1.1).
It might play the role predecessor in an arc relationship (see D-1.10). The role successor has to play a Topic representing a transition (see D-1.1).
It might have an internal occurrence typed as label (see D-1.5).

In the following the mapping from the TMDM to the PNDM is defined (the mapping of the arc relationship is defined in D-1.10):

Place. In the PNDM instance, each topic item T fulfilling the defined constraints requires a place item P. All values of T.[subject identifiers] and T.[item identifiers] are set to P.[item identifiers]. This place item is added to PN.[places].

Label. The topic item T might have an occurrence item O in its property [occurrences], where O.[type] contains a topic item with http://psi.semports.org/pndm/label in its property [subject identifiers]. In the PNDM instance, this occurrence item O requires a characteristics item C where C.[key] is set to http://psi.semports.org/pndm/label and C.[value] is set to O.[value]. The characteristic item C is added to P.[characteristics]. Additionally, C.[item identifiers] is set to O.[value].

D-1.5 Topic Class: Label Type

Being a label of a Petri net element is represented by a Topic with the following constraints:

It has a subject identifier http://psi.semports.org/pndm/label

D-1.6 Topic Class: Operator Type

Being an operator of a transition is represented by a Topic with the following constraints:

It has a subject identifier http://psi.semports.org/pndm/operator

D-1.7 Topic Class: Operand Type

Being an operand of a transition is represented by a Topic with the following constraints:

It has at least one subject identifier. (This subject identifier is used to determine the kind of the operand in the operator specification.)

Note: To avoid naming conflicts, it is recommended, that the used subject identifiers are in the namespace http://psi.semports.org/pndm/operand/

It has to play the role instance in an instance-of relationship (see D-1.11). The role class has to play a Topic with a subject identifier http://psi.semports.org/pndm/operand.

D-1.8 Topic Class: Condition Type

Being a condition is represented by a Topic with the following constraints:

It has a subject identifier http://psi.semports.org/pndm/condition

D-1.9 Association Class: Workflow

Being a workflow between a start and a end place is represented by an association with the following constraints:

It has to play the role instance in an instance-of relationship. The role class has to play a Topic with a subject identifier http://psi.semports.org/pndm/workflow.
There exist exactly two association roles.

The first represents the role start place and is itself an instance of a topic with the subject identifier http://psi.semports.org/pndm/start_place. This role can only be cast by a topic representing a place (D-1.4).
The second represents the role end place and is itself an instance of a topic with the subject identifier http://psi.semports.org/pndm/end_place. This role can only be cast by topics representing a place (D-1.4).

In the following the mapping from the TMDM to the PNDM is defined:

Workflow: In the PNDM, each association item A fulfilling the defined constraints requires a workflow item W. This workflow item is added to PN.[workflows].

Start place. The topic item S plays the role start place in the association. If there exist in the PNDM instance a place item P where P.[item identifiers] contains a value from S.[item identifiers], W.[start place] is set to this place item P.

End place. The topic item E plays the role end place in the association. If there exist in the PNDM instance a place item P where P.[item identifiers] contains a value from E.[item identifiers], W.[end place] is set to this place item P.

D-1.10 Association Class: Arc

Being a directed arc between places and transitions is represented by an association with the following constraints:

It has to play the role instance in an instance-of relationship. The role class has to play a Topic with a subject identifier http://psi.semports.org/pndm/arc.
There exist exactly two association roles.

The first represents the role predecessor and is itself an instance of a topic with the subject identifier http://psi.semports.org/pndm/arc_predecessor. This role can only be cast by topics representing places (D-1.4) or transitions (D-1.3). In the case the role is cast by a place, the role successor has to be cast by a transition.
The second represents the role successor and is itself an instance of a topic with the subject identifier http://psi.semports.org/pndm/arc_successor. This role can only be cast by topics representing places (D-1.4) or transitions (D-1.1). In the case the role is cast by a place, the role predecessor has to be cast by a transition.

In the following the mapping from the TMDM to the PNDM is defined:

The topic item P plays the role predecessor in the association. There should exist in the PNDM instance a Petri net construct PP where PP.[item identifiers] contains a value from P.[item identifiers].

The topic item S plays the role successor in the association. There should exist in the PNDM instance a Petri net construct PS where PS.[item identifiers] contains a value from S.[item identifiers].

Successor. PS is added to PP.[successors].

D-1.11 Association Class: Instance of

Being an instance-of relationship is represented by an association with the following constraints [see TMDM]:

It has to play the role instance in an instance-of relationship. The role class has to play a Topic with a subject identifier http://psi.topicmaps.org/iso13250/model/type-instance.
There exist exactly two association roles.

The first represents the role instance and is itself an instance of a topic with the subject identifier http://psi.topicmaps.org/iso13250/model/instance. There are no constraints in respect to the role players of this role.
The second represents the role class and is itself an instance of a topic with the subject identifier http://psi.topicmaps.org/iso13250/model/type. There are no constraints in respect to the role players of this role.

OSL-schema (informative)

To be done.

E MWP OWL Syntax

For the first implementation OWL Lite is adequate. For further implementation, especially if consistency checks of the defined Petri nets should be integrated other versions of OWL (OWL DL or OWL Full) might be required.

For representing Petri nets in OWL five classes are defined. The class MWP serves as a parent class for the other classes that are needed for describing Petri nets with OWL. The other classes are MWP_Petrinet, MWP_Transition, MWP_Place and MWP_Workflow. For implementing a Petri net instances of these classes must be build.

E.1 MWP_Petrinet

A Petri net is represented by an instance of the class MWP_Petrinet that has the following properties:

It has a unique identification.
It might have individuals of transitions, places and workflows as object properties.

In OWL a Petri net class and the corresponding properties are represented as follows:

class definition:

<owl:Class rdf:ID="MWP_Petrinet">

object properties:

- <owl:ObjectProperty rdf:ID="MWP_has_place">
<rdfs:domain rdf:resource="#MWP_Petrinet"/>
<rdfs:range rdf:resource="#MWP_Place"/>

- <owl:inverseOf>
<owl:ObjectProperty rdf:ID="MWP_place_belongs_to_petrinet"/>
</owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:ID="MWP_has_transition">
<rdfs:domain rdf:resource="#MWP_Petrinet"/>

- <rdfs:range rdf:resource="#MWP_Transition"/>

- <owl:inverseOf>
<owl:ObjectProperty rdf:ID="MWP_transition_belongs_to_petrinet"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:ID="MWP_has_workflow">

- <rdfs:domain rdf:resource="#MWP_Petrinet"/>

- <rdfs:range rdf:resource="#MWP_Workflow"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_workflow_belongs_to_petrinet"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

In the following the mapping from the OWL Data Model (ODM) to the PNDM is defined:

Transition. In the PNDM instance, each individual T fulfilling the defined constraints requires* a Petri net item PN. The value of rfd:ID of T is set to PN.[item identifiers].

(* “requires” means that an object of the Petri net item will be created within the PNDM)

E.2 MWP_Transition

A transition is represented by an instance of the class MWP_Transition, which has the following properties.

It has a unique identification.
It belongs to one or many Petri net individuals.
It might have preceding Places.
It might have succeeding Places.
It might have several operands.
It might have several operators.
It might have several preconditions.

The class for a Transition is represented in OWL as follows:

class definition:

<owl:Class rdf:ID="MWP_Transition">

object properties:

- <owl:ObjectProperty rdf:ID="MWP_has_predecessor_place">

- <rdfs:domain rdf:resource="#MWP_Transition"/>

- <rdfs:range rdf:resource="#MWP_Place"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_has_successor_transition"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:ID="MWP_has_successor_place">

- <rdfs:domain rdf:resource="#MWP_Transition"/>

- <rdfs:range rdf:resource="#MWP_Place"/>

- <owl:inverseOf>
<owl:ObjectProperty rdf:ID="MWP_has_predecessor_transition">
</owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:ID="MWP_transition_belongs_to_petrinet">

- <rdfs:domain rdf:resource="#MWP_Transition"/>

- <rdfs:range rdf:resource="#MWP_Petrinet"/>

- <owl:inverseOf>
<owl:ObjectProperty rdf:ID=”MWP_has_transition">
</owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:ID="MWP_has_operand">

- <rdfs:domain rdf:resource="#MWP_Transition"/>

- <rdfs:range rdf:resource="#MWP_Operand"/>

-</owl:ObjectProperty>

datatype properties:

- <owl:FunctionalProperty rdf:ID="MWP_has_operator">
<rdfs:domain rdf:resource="#MWP_Transition"/>
<rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>
</owl:DatatypeProperty>

- <owl:DatatypeProperty rdf:ID="MWP_has_precondition">

- <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>

- <rdfs:domain rdf:resource="#MWP_Transition"/>

-</owl:DatatypeProperty>

In the following the mapping from the ODM to the PNDM is defined (the mapping of the arcs between places and transitions is defined in E-6):

Transition. In the PNDM instance, each individual T fulfilling the defined constraints requires a transition item T. The value of rfd:ID of T is set to T.[item identifiers]. This transition item is added to PN.[transitions].

Operator. The individual item T may have a datatype property with the id MWP_has_operator of the type string. For an operator a characteristic item C will be defined. The value of the property C.[key] is set to http://psi.semports.org/pndm/operator. The value of the property C.[value] is set to the value of MWP_has_operator. This characteristic item C is added to T.[characteristics].

Operand. The individual item T may have an object property with the id MWP_has_operand of the type MWP_operand. In the PNDM instance a characteristic item C will be defined. The value of the property C.[key] is set to the datatype property MWP_has_operand_id of the individual of MWP_operand. The value of the property C.[value] is set to the value of the property MWP_has_operand_value that is defined within the MWP_operand. The characteristic item C is added to T.[characteristics].

Condition. The individual item T might have several datatype property with the id MWP_has_precondition of the type string. In the PNDM instance, every precondition string requires a condition item C where C.[condition] is set to the value of the corresponding string of the property MWP_has_precondition. The condition items C are added to T.[conditions].

E.3 MWP_Place

A place is represented by an instance of the class MWP_Place, which has the following properties.

It has a unique identification.
It belongs to one or many Petri net individuals.
It might have preceding Transitions.
It might have succeeding Transitions.

The class for a place is represented in OWL as follows:

class definition:

<owl:Class rdf:ID="MWP_Place">

object properties:

- <owl:ObjectProperty rdf:ID="MWP_has_predecessor_transition">

- <rdfs:domain rdf:resource="#MWP_Place"/>

- <rdfs:range rdf:resource="#MWP_Transition"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_has_successor_place"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:about="#MWP_has_successor_transition">

- <rdfs:domain rdf:resource="#MWP_Place"/>

- <rdfs:range rdf:resource="#MWP_Transition"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_has_predecessor_place"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

- <owl:ObjectProperty rdf:about="#MWP_place_belongs_to_petrinet">

- <rdfs:domain rdf:resource="#MWP_Place"/>

- <rdfs:range rdf:resource="#MWP_Petrinet"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_has_place "/>

- </owl:inverseOf>

-</owl:ObjectProperty>

In the following the mapping from the ODM to the PNDM is defined (the mapping of the arcs between places and transitions is defined in E-6):

Place. In the PNDM instance, each individual item T fulfilling the defined constraints requires a place item P. The value of rfd:ID of T is set to P.[item identifiers]. This place item is added to PN.[places].

E.4 MWP_Workflow

A workflow is represented by a class named MWP_Workflow that has the following properties.

It has a unique identification.
It refers to exactly one place defining the start place.
It refers to exactly one place defining the end place.
It belongs to exactly one Petri net.
It might have a description.

The class for the workflow is represented in OWL as follows:

class definition:

<owl:Class rdf:ID="MWP_Workflow">

object properties:

- <owl:FunctionalProperty rdf:ID="MWP_has_startplace">

- <rdfs:domain rdf:resource="#MWP_Workflow"/>

- <rdfs:range rdf:resource="#MWP_Place"/>

- <rdf:type rdf:resource="http://www.w3.org/2002/07/owl#ObjectProperty"/>

-</owl:FunctionalProperty>

- <owl:FunctionalProperty rdf:ID="MWP_has_endplace">

- <rdfs:domain rdf:resource="#MWP_Workflow"/>

- <rdfs:range rdf:resource="#MWP_Place"/>

- <rdf:type rdf:resource="http://www.w3.org/2002/07/owl#ObjectProperty"/>

-</owl:FunctionalProperty>

- <owl:ObjectProperty rdf:about="#MWP_workflow_belongs_to_petrinet">

- <rdfs:domain rdf:resource="#MWP_Workflow"/>

- <rdfs:range rdf:resource="#MWP_Petrinet"/>

- <owl:inverseOf>

- <owl:ObjectProperty rdf:ID="MWP_has_workflow"/>

- </owl:inverseOf>

-</owl:ObjectProperty>

datatype properties:

- <owl:DatatypeProperty rdf:ID="MWP_has_description">

- <rdfs:domain rdf:resource="#MWP_Workflow"/>

- <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>

-</owl:DatatypeProperty>

In the following the mapping from the ODM to the PNDM is defined:

Workflow: In the PNDM, an individual item T that fulfils the defined constraints requires a workflow item W. The value of rfd:ID of T is set to W.[item identifiers]. This workflow item is added to PN.[workflows].

Start place. The rdf:ID of the place that is referred to by the object property MWP_has_startplace is used to find the place item P (due to P.[item identifiers]) from the set of created place items (see E.3). W.[start place] is set to this place item P.

End place. The rdf:ID of the place that is referred to by the object property MWP_has_endplace is used to find the place item P (due to P.[item identifiers]) from the set of created place items (see E.3). W.[end place] is set to this place item P.

E.5 MWP_Operand

An operand is represented by an instance of the class MWP_Operand, which has the following properties.

It has a unique identification.
It has a value.

The class for an operand is represented in OWL as follows:

class definition:

<owl:Class rdf:ID="MWP_Operand">

datatype properties:

- <owl:FunctionalProperty rdf:ID="MWP_has_operand_value">

- <rdfs:domain rdf:resource="#MWP_Operand"/>

- <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>

-</owl:DatatypeProperty>

- <owl:FunctionalProperty rdf:ID="MWP_has_operand_id">

- <rdfs:domain rdf:resource="#MWP_Operand"/>

- <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>

-</owl:DatatypeProperty>

E.6 Creating the connections between places and transitions

Having used the transitions, places and workflows to create a valid PNDM, connections between places and transitions need to be instantiated. For that the object properties MWP_has_predecessor_transition and MWP_has_successor_transition of the class MWP_Place are used.

For every individual P of the class MWP_Place the rdf:ID of the transition that is referred to by the object property MWP_has_predecessor_transition is used to find the transition item T (due to T.[item identifiers]) from the set of created transition items (see E.2). T.[successors] is set to the place item P that corresponds to P (due to P.[item identifiers]).

For every individual P of the class MWP_Place the rdf:ID of the transition that is referred to by the object property MWP_has_successor_transition is used to find the transition item T (due to T.[item identifiers]) from the set of created transition items (see E.2). P is the place item that corresponds to P (due to P.[item identifiers) P.[successors] is set to the transition item T.

References

[Aa98] van der Aalst, W. M. P.: The Application of Petri Nets to Workflow Management. In: The Journal of Circuits, Systems and Computers, 8(1):21-66, (1998).

[DNB06] Durusau, P.; Newcomb, S. R.: Topic Maps Topic Maps Reference Model, 13250-5.

[Infoset] Cowan, John; Tobin, Richard: XML Information Set (Second Edition). W3C Recommendation. Available at: Verfügbar unter: http://www.w3.org/TR/xml-infoset/.

[ISO 10646] ISO 10646:2003: Information technology — Universal Multiple-Octet Coded Character Set (UCS), ISO, 2003

[MB06] Maicher, L.; Böttcher, M.: Closing the Semantic Gap in Topic Maps and OWL Ontologies with Modelling Workflow Patterns. Submitted to: I-Know 2006, Graz. (2006).

[PS03] Pepper, S.; Schwab, S.: Curing the Web’s Identity Crisis. Subject Indicators for RDF. In Proceedings of: XML Europe 2003.

[TMDM] ISO/IEC: Topic Maps – Part 2: Data Model. Latest version available at: http://www.isotopicmaps.org/sam

[Unicode] The Unicode Standard, Version 4.0, The Unicode Consortium, Reading, Massachusetts, USA, Addison-Wesley, 2003, ISBN 0-321-18578-1

Appendix

In the following some operators are defined. It is left to everybody to specify own operators. These specifications are normative for interpreters implementing the operators.

If an interpreter is forced to process a workflow with unknown operators it is completely left to the interpreter to solve this problem.

Generic Operators

Operator: Get string from human

Operator	PSI	http://psi.semports.org/mwp/human_string
	PNPM context	MWP
	Description	The interpreter has to request from the user a string. The according question is specified by the operator. One string gained from the users is stored as result of the operator.
*Operand* 1	PSI	http://www.lutzmaicher.de/pndm/operand/operand1
	Description	The question which has to be exposed to the user.
*Result*	Key-Rule	One item identifier of the current transition item + “.value”
	Example	id24.value
	Value	The string delivered by the user.

Operator: Give an information to the human

Operator	PSI	http://psi.semports.org/mwp/human_information
	PNPM context	MWP
	Description	The interpreter has to give an informative output to the human depending on the value of the operand.
*Operand* 1	PSI	http://www.lutzmaicher.de/pndm/operand/operand1
	Description	The information which has to be exposed to the user.

Operator: Get binary decision from human

Operator	PSI	http://psi.semports.org/mwp/human_binary
	PNPM context	MWP
	Description	The interpreter has to request from the user a binary decision. The according question is specified by the operator. The response gained from the users (using the PSIs for true and false) is stored as the result of the operator.
*Operand* 1	PSI	http://www.lutzmaicher.de/pndm/operand/operand1
	Description	The question which has to be exposed to the user.
*Result*	Key-Rule	One item identifier of the current transition item + “.value”
	Example	id24.value
	Value	If the user has responded with “yes”: http://psi.semports.org/pndm/TRUE If the user has responded with “no”: http://psi.semports.org/pndm/FALSE

Topic Map Specific Operators

Operator: Update Topic Map

Operator	PSI	http://psi.semports.org/mwp/mergeInTopicMap
	PNPM context	MWP
	Description	The interpreter has to merge a LTM statement into the data source of the given case. This operator does not store any results in the current token item.
*Operand* 1	PSI	http://www.lutzmaicher.de/pndm/operand/operand1
	Description	The LTM statement which has to be merged into the data source of the given case. The LTM statement has to be instantiated according C-C-1.2 using the current token item.

OWL Specific Operators

Operator: Ontology Request

Operator	PSI	http://psi.semports.org/mwp/ontology_request
	PNPM context	MWP
	Description	The interpreter has to request an OWL ontology. Due to the operands it has to request an OWL ontology whether a certain value exists or it has to insert a specific value.
*Operand* 1	PSI	http://www.lutzmaicher.de/pndm/operand/operand1
	Description	The value of this operand corresponds to the value that has to be requested from the ontology. The string of the value consists of two parts divided by the character “%”: The first part contains the name of the individual that is requested. The second part contains the name of the class that is requested. Example: “Michael%Human”
*Operand 2*	PSI	http://www.lutzmaicher.de/pndm/operand/operand2
	Description	The value of this operand corresponds to the value that has to be added to the ontology. The string of the value consists of two parts divided by the character “%”: The first part contains the name of the individual that has to be added. The second part contains the name of the class the individual has to be added to. Example: “Michael%Human”
*Result*	Key-Rule	One item identifier of the current transition item + “.value”
	Example	id24.value
	Value	The string delivered by the request or a String corresponding to the existence of a requested value. If the value exists within the ontology: http://psi.semports.org/pndm/TRUE If the value does not exist within the ontology: http://psi.semports.org/pndm/FALSE