ISO/IEC 15909-1:2004

Systems and software engineering - High-level Petri nets - Part 1: Concepts, definitions and graphical notation

ISO/IEC 15909-1:2004 defines a semi-graphical modelling language for the specification, design and analysis of discrete event systems, including software and in particular distributed and parallel systems where concurrency is an important characteristic. The technique, High-level Petri Nets, is mathematically defined and may thus be used to provide unambiguous specifications and descriptions of applications. The graphical nature of the technique allows information, or resource flow, and control flow to be visualised, providing a powerful aid to understanding system behaviour. It is also an executable technique, allowing specification prototypes to be developed to test ideas at the earliest and cheapest opportunity. Specifications written in the technique may be subjected to analysis methods to prove properties about the specifications, before implementation commences, thus saving on testing and maintenance time. The field of application encompasses a wide range of systems from technical systems such as manufacturing, business processes, computer software and hardware, telecommunication networks and signalling systems, defence systems, mechatronics, postal services and avionics to biological and sociotechnical systems.

Ingénierie des systèmes et du logiciel — Réseaux de Petri de haut niveau — Partie 1: Concepts, définitions et notation graphique

General Information

• Status: Withdrawn
• Publication Date: 01-Dec-2004
• Withdrawal Date: 01-Dec-2004
• ICS: 35.080 - Software
• Technical Committee: ISO/IEC JTC 1/SC 7 - Software and systems engineering
• Drafting Committee: ISO/IEC JTC 1/SC 7/WG 19 - Techniques for Specifying IT Systems
• Current Stage: 9599 - Withdrawal of International Standard
• Start Date: 27-Aug-2019
• Completion Date: 30-Oct-2025

Relations

• Consolidated By: ISO 16925:2014 - Paints and varnishes - Determination of the resistance of coatings to pressure water-jetting
• Effective Date: 06-Jun-2022
• Amended By: ISO/IEC 15909-1:2004/Amd 1:2010 - Systems and software engineering - High-level Petri nets - Part 1: Concepts, definitions and graphical notation - Amendment 1: Symmetric Nets
• Effective Date: 06-Jun-2022
• Revised: ISO/IEC 15909-1:2019 - Systems and software engineering - High-level Petri nets - Part 1: Concepts, definitions and graphical notation
• Effective Date: 16-Aug-2014
• Parent: ISO/IEC 15909-1:2004/Amd 1:2010 - Systems and software engineering - High-level Petri nets - Part 1: Concepts, definitions and graphical notation - Amendment 1: Symmetric Nets
• Effective Date: 26-Jun-2008

Standards Content (Sample)

INTERNATIONAL ISO/IEC
STANDARD 15909-1
First edition
2004-12-01
Software and system engineering —
High-level Petri nets —
Part 1:
Concepts, definitions and graphical
notation
Ingénierie du logiciel et du système — Toiles de Petri de haut niveau —
Partie 1: Concepts, définitions et notation graphique

Reference number
©
ISO/IEC 2004
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.

©  ISO/IEC 2004
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail [e-mail]
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2004 – All rights reserved

Contents
Foreword                                                                  vi

Introduction                                                               vii

1 Scope 1
1.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Field of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Terms, Definitions, Abbreviations and Symbols 2
2.1 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Conventions and Notation 5
4 Semantic Model for High-level Petri Nets 6
4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 Marking of HLPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Enabling of Transition Modes . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.3.1 Enabling of a Single Transition Mode . . . . . . . . . . . . . . . . . . 7
4.3.2 Concurrent Enabling of Transition Modes . . . . . . . . . . . . . . . . 7
4.4 Transition Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Concepts Required for High-level Petri Net Graphs 8
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 High-level Petri Net Graph Components . . . . . . . . . . . . . . . . . . . . . 8
5.3 Net Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.3.1 Enabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3.2 Transition Rule for a Single Transition Mode . . . . . . . . . . . . . . 9
5.3.3 Step of Concurrently Enabled Transition Modes . . . . . . . . . . . . . 10
5.4 Graphical Concepts and Notation . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.5 Conditionals in Arc Expressions, and Parameters . . . . . . . . . . . . . . . . 11
6 Definition of High-level Petri Net Graphs 13
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
© ISO/IEC 2004 – All rights reserved iii

6.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3 Marking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.4 Enabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.4.1 Enabling of a Single Transition Mode . . . . . . . . . . . . . . . . . . 14
6.4.2 Concurrent Enabling of Transition Modes . . . . . . . . . . . . . . . . 15
6.5 Transition Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7 Notation for High-level Petri Net Graphs 16
7.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2 Places . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.3 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.4 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.5 Markings and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8 Semantics of High-level Petri Net Graphs 17
9 Conformance 18
9.1 PN Conformance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.1.1 Level 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.1.2 Level 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.2 HLPN Conformance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.2.1 Level 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.2.2 Level 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Annex A: Mathematical Conventions (normative) 20
A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A.2 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A.2.1 Sum Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A.2.2 Membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A.2.3 Empty Multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
A.2.4 Cardinality and Finite Multiset . . . . . . . . . . . . . . . . . . . . . . 21
A.2.5 Multiset Equality and Comparison . . . . . . . . . . . . . . . . . . . . 21
A.2.6 Multiset Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
A.3 Concepts from Algebraic Specification . . . . . . . . . . . . . . . . . . . . . . 21
A.3.1 Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
iv © ISO/IEC 2004 – All rights reserved

A.3.2 Boolean Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
A.3.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
A.3.4 Terms built from a Signature and Variables . . . . . . . . . . . . . . . 22
A.3.5 Many-sorted Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A.3.6 Assignment and Evaluation . . . . . . . . . . . . . . . . . . . . . . . 24
Annex B: Net Classes (normative) 25
B.1 Place/Transition Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Annex C: High-level Petri Net Schema (informative) 27
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
C.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Annex D: Tutorial (informative) 28
D.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.2 Net Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.2.1 Places and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.2.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
D.2.3 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.2.4 The Net Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.3 Transition Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
D.4 Net Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
D.5 Flow Control Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Annex E: Analysis Techniques (informative) 36
Bibliography 37
© ISO/IEC 2004 – All rights reserved v

Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are members of
ISO or IEC participate in the development of International Standards through technical committees
established by the respective organization to deal with particular fields of technical activity. ISO and IEC
technical committees collaborate in fields of mutual interest. Other international organizations, governmental
and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information
technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the national bodies casting a vote.
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights.
ISO/IEC 15909-1 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 7, Software and system engineering.
ISO/IEC 15909 consists of the following parts, under the general title Software and system engineering —
High-level Petri nets:
 Part 1: Concepts, definitions and graphical notation

vi © ISO/IEC 2004 – All rights reserved

Introduction
This International standard is Part 1 of a multi-part standard concerned with defining a mod-

elling language and its transfer format, known as High-level Petri Nets. Part 1 defines a semi-
graphical technique for the specification, design and analysis of discrete event systems.

The technique is mathematically defined and may thus be used to provide unambiguous spec-
ifications and descriptions of applications. It is also an executable technique, allowing specifi-
cation prototypes to be developed to test ideas at the earliest and cheapest opportunity. Specifi-
cations written in the technique may be subjected to analysis methods to prove properties about
the specifications, before implementation commences, thus saving on testing and maintenance
time and providing a high level of quality assurance.
Petri nets have been used to describe a wide range of systems since their invention in 1962. A
problem with Petri nets is the explosion of the number of elements of their graphical form when
they are used to describe complex systems. High-level Petri Nets were developed to overcome
this problem by introducing higher-level concepts, such as the use of complex structured data
as tokens, and using algebraic expressions to annotate net elements. The use of ‘high-level’
to describe these Petri nets is analogous to the use of ‘high-level’ in high-level programming
languages (as opposed to assembly languages), and is the usual term used in the Petri net com-
munity. Two of the early forms of high-level nets that this standard builds on are Predicate-
Transition Nets and Coloured Petri Nets, first introduced in 1979 and developed during the
1980s. It also uses some of the notions developed for Algebraic Petri nets, first introduced in
the mid 1980s. It is believed that this standard captures the spirit of these earlier developments
(see bibliography).
The technique promises to have multiple uses. For example, it may be used directly to specify
systems or to define the semantics of other less formal languages. It may also serve to integrate
techniques currently used independently such as state transition diagrams and data flow dia-
grams. The technique is particularly suited to parallel and distributed systems development as
it supports concurrency. The technique is able to specify systems at a level that is independent
of the choice of implementation (i.e. by software, hardware (electronic and/or mechanical) or
humans or a combination). This International Standard may be cited in contracts for the devel-
opment of systems (particularly distributed systems), or used by application developers or Petri
net tool vendors or users.
Part 1 of this International Standard provides an abstract mathematical syntax and a formal
semantics for the technique. Conformance to the standard is possible at several levels. The
level of conformance depends on the class of high-level net chosen and the degree to which the
syntax is supported. The basic level of conformance is to the semantic model.
Clause 1 describes the scope, areas of application and the intended audience of Part 1 of this
International Standard. Clause 2 provides a glossary of terms and defines abbreviations. The main
mathematical apparatus required for defining the semantic model and its graphical form is developed in
normative Annex A and referred to in clause 3. The basic semantic model for High-level Petri Nets
is given in clause 4, while the main concepts behind the graphical form are in formally introduced
in clause 5. Clause 6 defines the High-level Petri Net Graph, the form of the standard intended
for industrial use. Components of the graph are annotated. The annotations are defined at a
© ISO/IEC 2004 – All rights reserved vii

meta-level allowing many different concrete syntaxes to be used. Clause 7 describes several
syntactical conventions. Clause 8 maps the graphical form to the basic semantic model. The
conformance statement is given in clause 9. Normative Annex B defines Place/Transition nets
(without capacities) as a restriction of the definition of Clause 6. Place/Transition nets is often
what is meant when the term Petri nets is used. Three informative annexes are included: Annex C
defines a High-level Petri Net Schema, which allows classes of systems to be described at
a syntactic level; Annex D is a tutorial on the High-level Petri Net Graph; and Annex E pro-
vides pointers to analysis techniques for High-level Petri Nets. A bibliography concludes this
International Standard.
viii © ISO/IEC 2004 – All rights reserved

INTERNATIONAL STANDARD ISO/IEC 15909-1:2004(E)

Software and system engineering — High-level Petri nets —
Part 1:
Concepts, definitions and graphical notation
1 Scope
1.1 Purpose
This International Standard defines a Petri net technique, called High-level Petri Nets, includ-
ing its syntax and semantics. It provides a reference definition that can be used both within

and between organisations, to ensure a common understanding of the technique and of the
specifications written using the technique. This International Standard will also facilitate the
development and interoperability of Petri net computer support tools.
Part 1 of this International Standard defines a mathematical semantic model, an abstract math-
ematical syntax for annotations and a graphical notation for High-level Petri Nets, known as
the High-level Petri Net Graph. A mathematical mapping is provided that defines the graphical
form in terms of the semantic model. A transfer format for the High-level Petri Net Graph is the
subject of Part 2 of this International Standard, while Part 3 addresses techniques for modularity
(such as hierarchies) and the augmentation of High-level Petri Nets with time.
1.2 Field of Application
This International Standard is applicable to a wide variety of concurrent discrete event systems
and in particular distributed systems. Generic fields of application include:

requirements analysis;
development of specifications, designs and test suites;

descriptions of existing systems prior to re-engineering;

modelling business and software processes;

providing the semantics for concurrent languages;

simulation of systems to increase confidence;

formal analysis of the behaviour of systems; and

development of Petri net support tools.
This International Standard may be applied to the design of a broad range of systems and
processes, including aerospace, air traffic control, avionics, banking, biological and chemi-
cal processes, business processes, communication protocols, computer hardware architectures,
control systems, databases, defence command and control, distributed computing, electronic
commerce, fault-tolerant systems, hospital procedures, information systems, Internet protocols
and applications, legal processes, logistics, manufacturing systems, metabolic processes, mu-
sic, nuclear power systems, operating systems, transport systems (including railway control),
security systems, telecommunications and workflow.
(c) ISO/IEC 2004 - All rights reserved 1

1.3 Audience
Part 1 of this International Standard is written as a reference for systems analysts, designers,
developers, maintainers and procurers, and for Petri net tool designers and standards developers.
2 Terms, Definitions, Abbreviations and Symbols
For the purpose of this International Standard, the following definitions, abbreviations and sym-
bols apply. Any ambiguity in the definitions is resolved by the mathematically precise defini-
tions in the body of Part 1 of this International Standard.
2.1 Glossary
2.1.1 Arc: A directed edge of a net which may connect a place to a transition or a transition to
a place, normally represented by an arrow.
2.1.1.1 Input Arc (of a transition): An arc directed from a place to the transition.
2.1.1.2 Output Arc (of a transition): An arc directed from the transition to a place.
2.1.1.3 Arc Annotation: An expression that may involve constants, variables and operators
used to annotate an arc of a net. The expression must evaluate to a multiset over the type of the
arc’s associated place.
2.1.2 Arity: The input sorts and output sort for an operator.
2.1.3 Assignment: For a set of variables, the association of a value (of correct type) to each
variable.
2.1.4 Basis Set: The set of objects used to create a multiset.
2.1.5 Binding: See Assignment.
2.1.6 Carrier: A set of a many-sorted algebra.
2.1.7 Concurrency: The property of a system in which events may occur independently of each
other, and hence are not ordered (see also Step and Concurrent Enabling).
2.1.8 Declaration: A set of statements which define the sets, constants, parameter values, typed
variables and functions required for defining the annotations on a High-level Petri Net Graph.
2.1.9 Enabling (a transition): A transition is enabled in a particular mode and net marking,
when the following conditions are met:
The marking of each input place of the transition satisfies the demand imposed on it by its arc
annotation evaluated for the particular transition mode. The demand is satisfied when the place’s
marking contains (at least) the multiset of tokens indicated by the evaluated arc annotation.
NOTE: The determination of transition modes guarantees that the Transition Condition is satis-
fied (see Transition Mode).
2.1.10 Concurrent Enabling (of transition modes): A multiset of transition modes is concur-
rently enabled if all the involved input places contain enough tokens to satisfy the sum of all of
(c) ISO/IEC 2004 - All rights reserved 2

the demands imposed on them by each input arc annotation evaluated for each transition mode
in the multiset.
2.1.11 High-level Net (High-level Petri Net): An algebraic structure comprising: a set of
places; a set of transitions; a set of types; a function associating a type to each place, and a
set of modes (a type) to each transition; Pre function imposing token demands (multisets of
tokens) on places for each transition mode; Post function determining output tokens (multisets
of tokens) for places for each transition mode; and an initial marking.
2.1.12 High-level Petri Net Graph: A net graph and its associated annotations comprising
Place Types, Arc Annotations and Transition Conditions, and their corresponding definitions in
a set of Declarations, and an Initial Marking of the net.
2.1.13 Many-sorted Algebra: A mathematical structure comprising a set of sets and a set of
functions taking these sets as domains and co-domains.
2.1.14 Marking (of a net): The set of the place markings for all places of the net.
2.1.14.1 Initial Marking (of the net): The set of initial place markings given with the high-
level net definition.
2.1.14.2 Initial Marking of a place: A special marking of a place, defined with the high-level
net.
2.1.14.3 Marking of a place: A multiset of tokens associated with (‘residing in’) the place.
2.1.14.4 Reachable Marking: Any marking of the net that can be reached from the initial
marking by the occurrence of transitions.
2.1.14.5 Reachability Set: The set of reachable markings of the net, including the initial mark-
ing.
2.1.15 Multiset: A collection of items where repetition of items is allowed.
2.1.15.1 Multiplicity: A natural number (i.e., non-negative integer) which describes the number
of repetitions of an item in a multiset.
2.1.15.2 Multiset Cardinality (cardinality of a multiset): The sum of the multiplicities of
each of the members of the multiset.
2.1.16 Net: A general term used to describe all classes of Petri nets.
2.1.16.1 Net Graph: A directed graph comprising a set of nodes of two different kinds, called
places and transitions, and their interconnection by directed edges, called arcs, such that only
places can be connected to transitions, and transitions to places, but never transitions to transi-
tions, nor places to places.
2.1.16.2 Node (of a net): A vertex of a net graph (i.e., a place or a transition).
2.1.16.3 Petri Net: An algebraic structure with two sets, one called places and the other called
transitions, together with their associated relations and functions, and named after their inventor,
Carl Adam Petri.
2.1.16.4 Place/Transition Net: A Petri net comprising a net graph with positive integers asso-
ciated with arcs and an initial marking function which associates a natural number of simple
tokens (‘black dots’) with places.
(c) ISO/IEC 2004 - All rights reserved 3

2.1.17 Operator: A symbol representing the name of a function.
2.1.18 Parameter: A symbol that can take a range of values defined by a set. It is defined as a
constant in the signature.
2.1.19 Parameterized High-level Net Graph: A high-level net graph that contains parameters
in its definition.
2.1.20 Place: A node of a net, taken from the place kind, normally represented by an ellipse in
the net graph. A place is typed.
2.1.20.1 Input Place (of a transition): A place connected to the transition by an input arc.
2.1.20.2 Output Place (of a transition): A place connected to the transition by an output arc.
2.1.20.3 Place Type: A non-empty set of data items associated with a place. (This set can
describe an arbitrarily complex data structure.)
2.1.21 Reachability Graph: A directed graph of nodes and edges, where the nodes correspond
to reachable markings, and the edges correspond to transition occurrences.
2.1.22 Signature/Many-sorted signature: A mathematical structure comprising a set of sorts
and a set of operators.
2.1.22.1 Boolean signature: A signature where one of the sorts is , corresponding to the
carrier Boolean in any associated algebra, and one of the constants iscorresponding to
the value true in the algebra.
2.1.23 Sort: A symbol representing the name of a set.
2.1.23.1 Argument Sort: The sort of an argument of an operator.
2.1.23.2 Input Sort: The same as an argument sort.
2.1.23.3 Output Sort: The sort of an output of an operator.
2.1.23.4 Range Sort: The same as an output sort.
2.1.24 Term: An expression comprising constants, variables and operators built from a signa-
ture and a set of sorted variables.
2.1.24.1 Closed Term: A term comprising constants and operators but no variables. Also
known as a Ground Term.
2.1.24.2 Term Evaluation: The result obtained after the binding of variables in the term, the
computation of the results of the associated functions, and any simplifications performed (such
as gathering like terms to obtain the symbolic sum representation of a multiset).
2.1.25 Token: A data item associated with a place and chosen from the place’s type.
2.1.25.1 Enabling Tokens: The multiset of values obtained when an input arc annotation is
evaluated for a particular binding to variables.
2.1.25.2 Simple Token: A valueless token, normally represented by a black dot, and used in
Place/Transition nets (as opposed to high-level nets).
2.1.26 Transition: A node of a net, taken from the transition kind, and represented by a rectan-
gle in the net graph.
(c) ISO/IEC 2004 - All rights reserved 4

2.1.26.1 Transition Condition: A boolean expression (one that evaluates to true or false) asso-
ciated with a transition.
2.1.26.2 Transition Mode: A pair comprising the transition and a mode.
2.1.26.2.1 Mode: A value taken from the transition’s type. When considering a High-level Petri
Net Graph, a mode may be derived from an assignment of values to the transition’s variables
that satisfies the transition condition.
2.1.26.3 Transition Occurrence (Transition Rule): If a transition is enabled in a mode, it may
occur in that mode. On the occurrence of the transition, the following actions occur indivisibly:
1. For each input place of the transition: the enabling tokens of the input arc with respect to that
mode are subtracted from the input place’s marking, and
2. For each output place of the transition: the multiset of tokens of the evaluated output arc
expression is added to the marking of the output place.
NOTE: A place may be both an input place and an output place of the same transition.
2.1.26.4 Step: The simultaneous occurrence of a finite multiset of transition modes that are
concurrently enabled in a marking.
2.1.26.5 Transition Variables: All the variables that occur in the expressions associated with
the transition. These are the transition condition, and the annotations of arcs surrounding the
transition.
2.1.27 Type: A set.
2.2 Abbreviations
2.2.1 HLPN: High-level Petri Net
2.2.2 HLPNG: High-level Petri Net Graph
2.2.3 HLPNS: High-level Petri Net Schema
2.2.4 iff: if and only if
2.2.5 PN: Petri Net
2.2.6 PTNG: Place/Transition Net Graph.
3 Conventions and Notation
This International Standard uses the notation for sets, multisets and universal algebra defined in
Annex A. Annex A also defines the concept of multiset addition, (using the ‘’ symbol), which
should not be confused with arithmetic addition. The notion of multisets is required for clauses
4, 5, 6, 7 and 8. An understanding of many-sorted signatures, sorted variables and many-sorted
algebras provided in Annex A is required for clauses 6 and 8 and Annexes B and C.
Wherever possible standard mathematical notation has been used. An instance of notation spe-
cific to Petri nets is when a marking of the net is transformed to a new marking.

is used to denote that a new marking, , is created on the occurrence of a multiset

of transition modes, , when in the marking .
(c) ISO/IEC 2004 - All rights reserved 5

This notation is defined in clause 4, and similar notation is used in clause 6.
In High-level Petri Nets, an arc may be annotated by a variable or constant (or combination)
of the same type as the arc’s place. The evaluation of the arc expression is thus an element
of the place’s type. By convention, if an arc expression evaluates to an element of the place’s
type, this is interpreted as the corresponding singleton multiset over the place’s type. This is
necessary as an arc annotation when evaluated must be a multiset over the associated place’s
type. A similar convention applies when an arc expression evaluates to a set, which may be a
subset of the associated place’s type. This is interpreted as a multiset over the place’s type, with
corresponding multiplicities of zero and one.
The graphical notation used in clause 5 is that defined in clause 7.
4 Semantic Model for High-level Petri Nets
4.1 Definition
A High-level Petri Net is the structure: HLPN = where

is a finite set of elements called Places.
"!
is a finite set of elements called Transitions disjoint from (i.e. ).
$##
is a non-empty finite set of non-empty domains where each element of is called a
type.
+-,#
%’&(*)is a function used to assign a type to each place and to each
transition. (For transitions, the type defines the set of modes of the transition.)
+-,87
.&/10325456:912<;>=are the pre and post mappings with
@?GFIH
10325456%AB5C3DAEDJKL
N?HHGFHH
:9M2<;>=POGCDQRPOSDJ%L
TUD:9M2<;>=is a multiset called the initial marking of the net.
NOTE:V912<;>=is the set of multisets over the set,:912<;>=(see Annex A, section A.2).
4.2 Marking of HLPN
A Marking of the HLPN is a multiset,DV912<;>=.
(c) ISO/IEC 2004 - All rights reserved 6

4.3 Enabling of Transition Modes
4.3.1 Enabling of a Single Transition Mode

A transition mode,D10325456, is enabled at a marking if and only if (iff)

4.3.2 Concurrent Enabling of Transition Modes
A finite multiset of transition modes,D103246, is enabled at a marking iff

where the linear extension ofis given by

K
All transition modes in are said to be concurrently enabled if is enabled, i.e. there are
enough tokens on the input places to satisfy the linear combination of the pre mappings for each

transition mode in .
CCThis definition allows a transition mode to be concurrently enabled with itself. Also if ,
then this reduces to the definition in the previous subclause.
4.4 Transition Rule
Given that a finite multiset of transition modes, , is enabled at a marking , then a step may

occur resulting in a new marking given by
+
where the linear extension ofis used.
+,
A step is denoted by or .
NOTE: A step may comprise the occurrence of: a single transition mode; or any number of
concurrently enabled transition modes.
(c) ISO/IEC 2004 - All rights reserved 7

5 Concepts Required for High-level Petri Net Graphs
5.1 Introduction
High-level Petri Nets can be defined in a number of ways. Clause 4 provides the definition
of the basic mathematical semantic model. The basic semantic model is not what is used by
practitioners. High-level Petri Nets are normally represented using a graphical form which
allows visualisation of system dynamics (flows of data and control). This approach is taken,
as it is the graphical form of HLPNs that is most appropriate for industrial use. The graphical
form is referred to as a High-level Petri Net Graph (HLPNG). It provides a graphical notation
for places and transitions and their relationships, and determines the annotations of the graphical
elements.
This clause introduces the concepts that are needed in the definition of the High-level Petri Net
Graph. The concepts of enabling and transition rule are also introduced for the graphical form
to demonstrate how the net may be executed to show system dynamics. Readers interested in a
tutorial exposition on High-level Petri Net Graphs are referred to Annex D.
5.2 High-level Petri Net Graph Components
A High-level Petri Net Graph (HLPNG) comprises:

A Net Graph, consisting of sets of nodes of two different kinds, called places and transi-
tions, and arcs connecting places to transitions, and transitions to places.

Place Types. These are non-empty sets. One type is associated with each place.

Place Marking. A collection of elements (data items) chosen from the place’s type and
associated with the place. Repetition of items is allowed. The items associated with
places are called tokens.
Arc Annotations: Arcs are annotated with expressions which may comprise constants,
F
variables (e.g.,) and function images (e.g.,-). The variables are typed. The
expressions are evaluated by assigning values to each of the variables. When an arc’s
expression is evaluated, it must result in a collection of items taken from the type of the
arc’s place. The collection may have repetitions and is thus a multiset.
F
Transition Condition: A boolean expression (e.g.,) associated with a transition.

Declarations: comprising definitions of place types, typing of variables and definitions
of functions.
5.3 Net Execution
HLPNGs are executable, allowing the flow of tokens around the net to be visualised. This can
illustrate flow of control and flow of data within the same model. Key concepts governing this
(c) ISO/IEC 2004 - All rights reserved 8

execution are enabling of transitions and the occurrence of transitions defined by the Transition
Rule.
5.3.1 Enabling
A transition is enabled with respect to a net marking. A net marking comprises the set of all
place markings of the net.
A transition is also enabled in a particular transition mode. A transition mode is an assignment
of values to the transition’s variables, that satisfies the transition condition (i.e., the transition
condition is true). The transition’s variables are all those variables that occur in the expressions
associated with the transition. These are the transition condition, and the annotations of arcs
involving the transition.
Enabling a transition involves the marking of its input places. An input place of a transition is
a place which is connected to the transition by an arc leading from that place to the transition.
An arc that leads from an input place to a transition is called an input arc of the transition.
A transition is enabled in a specific mode, for a particular net marking. Each input arc expres-
sion is evaluated for the transition mode, resulting in a multiset of tokens of the same type as
that of the input place. If each input place’s marking contains at least its input arc’s multiset of
tokens (resulting from the evaluation of the input arc’s expression in the specific mode), then
the transition is enabled in that mode. An example is given in subclause 5.4.
The input arc’s multiset of tokens resulting from the evaluation of the input arc’s expression in
a specific mode is called the input arc’s enabling tokens, with respect to that mode.
Two transition modes are concurrently enabled for a particular marking, if for the associated
transitions, each input place’s marking contains at least the sum of the enabling tokens (with
respect to both modes) of each input arc associated with that input place.
5.3.2 Transition Rule for a Single Transition Mode
Enabled transitions can occur. When a transition occurs, tokens are removed from its input
places, and tokens are added to its output places. An output place of a transition is a place
which is connected to the transition by an arc directed from the transition to the place. An arc
that leads from a transition to a place (an output place of the transition) is called an output arc
of the transition.
If a transition is enabled in a mode, it may occur in that mode. On the occurrence of the
transition in a specific mode, the following actions occur atomically:
1. For each input place of the transition: the enabling tokens of the input arc with respect to that
mode are subtracted from the input place’s marking, and
2. For each output place of the transition: the multiset of tokens, resulting from the evaluation
of the output arc expression for the mode, is added to the marking of the output place.
NOTE: A place may be both an input place and an output place of the same transition.
(c) ISO/IEC 2004 - All rights reserved 9

5.3.3 Step of Concurrently Enabled Transition Modes
Several concurrently enabled transition modes may occur in one step, that is in one atomic
action. The change to the marking of the net when a step occurs is given by the sum of all
the changes that occur for each transition mode, as described above. An example is given in
subclause 5.4.
5.4 Graphical Concepts and Notation
The graphical representation of the net graph is introduced by the simple example of a HLPNG
given in figure 1.
A B
x x y
PSfrag replacements
p1 t1 p2
?
L
?
L
,
&arithmetic ‘less than’
x: , y:
Figure 1: HLPNG with a Transition Condition.
This example comprises two places, named p1 and p2, one transition, t1, and arcs from p1 to
t1, and t1 to p2. The places are represented by ellipses (in this case, circles), the transition by a
rectangle (in this example, a square), and the arcs by arrows.

The declarations define two types, and , that are different subsets of the positive integers.

Variable x is of type , and variable y is of type . The transition is annotated with the boolean
expression xy, where the less than operator is defined in the declarations. Arc (p1,t1) is
annotated with the variable x, while arc (t1,p2) is annotated with y.

Place p1 is typed by and has an initial marking (p1), using the sum represen-

tation of multisets of clause A.2.1. This states that associated with the place p1 are the value

and two instances of the value . Place p2 is typed by , and is empty representing the empty
"!
multiset, (p2) .
A convention adopted in high-level nets is that arcs may be annotated by variables or constants
of the same type as the arc’s place. The evaluation of the arc expression is thus an element of
the place’s type. By convention, this is interpreted as the corresponding singleton multiset over

the place’s type. For example, for x bound to , and y bound to , the value associated with

arc (p1,t1) is , which is interpreted to mean the multiset , and similarly the value associated

with arc (t1,p2) is , which is interpreted to mean the multiset . Where there is any possibility

of ambiguity, the multiset conversion operator ‘ ’ should be used. For example, more formally,

the annotation on the arc (p1,t1) would be x, rather than x.
In the initial marking, t1 can be enabled in the following modes
(c) ISO/IEC 2004 - All rights reserved 10

?
I%IIJ%I%I%L
where the first element of each pair represents a binding for x, and the second, a binding for y
which satisfies xy.
It can be seen that the multiset of modes,, is concurrently enabled. Another

example of the concurrent enabling of modes is the multisetand yet another

is.
If transition t1 occurred in mode, then the resultant marking would be:

(p1)
(p2).
Alternatively, if the multiset of modesoccurred concurrently, the resultant
marking would be
!
(p1)
(p2) .
5.5 Conditionals in Arc Expressions, and Parameters
The HLPNG of figure 2 uses a variant of the readers/writers problem to illustrate many of the
features of a HLPNG including the use of parameters and conditionals in arc expressions.
A number (N) of agents (processes) wish to access a shared resource (such as a file). Access
can be in one of two modes: shared (s), where up to L agents may have access at the same
time (e.g., reading); and exclusive (e), where only one agent may have access (e.g., writing).
No assumptions are made regarding scheduling. A HLPNG model of figure 2 illustrates the
use of two parameters, L and N, both of which are positive integer constants. This is there-
fore a parameterized HLPNG, which represents infinitely many readers/writers systems. Each
instantiation of N and L would produce a HLPNG, which could then be executed.
It has been assumed that the initial state is when all the agents are waiting to gain access to the
shared resource (with no queueing discipline assumed). In this example, the initial markings
are given in the declaration. Place Wait is marked with all agents; the Control place contains L

simple tokens (represented by a black dot ) and Access is empty. The marking of place Wait is

given by the set , which is interpreted to be a multiset over , where each of the multiplicities

of the agents is one. In a similar convention, the marking of Control is given by L , which is

interpreted as the multiset L . (That is the separator ‘ ’ is dropped where there is no ambiguity.)
An agent can obtain access in one of two modes: if shared (m=s), then a single token is removed

from Control (as m=e is false, and m e , and thus the arc expression evaluates to ,

interpreted as ) when Enter occurs in a single transition mode; if exclusive (m=e), then all L
tokens are removed preventing further access until the resource is released (transition Leave).
Shared access is limited to a maximum of L agents as transition Enter is disabled when Control
is empty.
,?
Outfix notation has been used for the function&L. This is the notation
for conditionals in arc expressions. It is assumed that multiset addition, integer subtraction,
the equality predicate and a tupling operator are primitive and do not need to be defined in the
declaration.
(c) ISO/IEC 2004 - All rights reserved 11

Enter
+
x (x,m)m eL
A C
AM
Wait Control
Access
+
x (x,m)m eL
PSfrag replacements
Leave
?
Set of Agents:A = aaL
?
Set of Access Modes: M = s,eL
?
Control: C =L
Positive integer constants: N, L
Variables x: A; m: M
,?
Function&Lwhere
and
WaitA
ControlL
!
Access
Figure 2: HLPNG of Resource Management.
(c) ISO/IEC 2004 - All rights reserved 12

6 Definition of High-level Petri Net Graphs
6.1 Introduction
This clause provides a formal definition for the graphical form of high-level nets. It provides an
abstract mathematical syntax for annotating the graphical elements. The concepts of marking,
enabling and transition rule are also formally defined for the graphical form.
6.2 Definition
A High-level Petri Net Graph is the structure HLPNG =46<24where

4Uis called a net graph, with
–a finite set of nodes, called Places;
!
– a finite set of nodes, called Transitions, disjoint from(i.e.’); and

–)Ua set of directed edges called arcs, known as the flow
relation.
66.is a Boolean signature defined in Annex A.

is an-indexed set of variables, disjoint from.

Gis a many-sorted algebra for the signature6, defined in Annex A.
,
%&is a function which assigns types to places.

2542(V;is a pair of net annotations.
,HH
–&1=:0G )such that for allKD, for all bindings
! 2U#"PK! 2$"K1P.DJM.1=:0N’)%(and& are de-

fined in Annex A. is a function that annotates each arc with a term that when
evaluated (for any binding) results in a multiset over the associated place’s type.
,
–V;N&/1=V0)%$’)((+*is a function that annotates transitions with Boolean
expressions.
,,.-7H7
0/TU&1such that1D,J13D%1, is the initial marking
function. It associates a multiset of tokens (of the correct type) which each place.
A HLPNG comprises an annotated net graph. The annotations are derived from a many sorted
signature, a set of sorted variables, and an associated many sorted algebra. A typing function
associates a set of the many-sorted algebra with each place, known as its type. Terms are built
from the signature and variables. Arcs are annotated by terms, which must evaluate to a multiset
over the associated place’s type. Transitions are annotated by Boolean terms. A place can only
hold tokens of the same type as the place and hence the initial marking is a multiset over the
place’s type.
(c) ISO/IEC 2004 - All rights reserved 13

NOTE 1: When defin
...