Aarhus University Seal / Aarhus Universitets segl

Volume 1, Basic Concepts

Review (from Computing Reviews)

K. Jensen: Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Volume 1, Basic Concepts. Monographs in Theoretical Computer Science, Springer-Verlag, 2nd corrected printing 1997. ISBN: 3-540-60943-1.

  • Keywords: Introduction to CP-nets, Formal definition, Hierarchical nets, Modularity, Dynamic and static properties, Verification methods, State spaces, Invariants, Computer tools, Industrial applications, General.
  • Comments: Textbook. An in-depth description of the basic concepts of CP-nets.

Coloured Petri nets (2nd ed.): basic concepts, analysis methods and practical use: volume 1.

Springer-Verlag, London, UK, 1996, 234 pp., $64.95, ISBN 3-540-60943-1. [EATCS monographs on theoretical computer science.]

Coloured Petri nets (CPNs) are probably the most used high-level Petri net model. This book is well focused, complete self-contained, easy to read, of a perfect length, and never tedious despite the topic. It should be on the shelves of all computer scientists and software engineers, be they practitioners or theoreticians.

The book can be understood with a standard mathematical background. CPNs can be studied without previous knowledge of Petri nets, but some basics of Petri nets would help the reader appreciate the power of CPN models and understand the book. The interested reader can find a good guide to books on Petri nets in the bibliographical remarks included in chapter 1.

CPNs are presented incrementally: the basic model (chapters 1 and 2), hierarchical CPNs (chapter 3), properties and analysis (chapters 4 and 5), and tools and industrial applications (chapters 6 and 7). Chapter 1 gives a quick overview of place/transition nets, before informally describing colored Petri nets. CPNs are illustrated through a few useful examples.

Chapter 2 completes the presentation of CPNs by presenting their formal definition. The choice of first presenting CPNs and then their hierarchical extensions, as well as the careful discussions, make the presentation clear and interesting even for practitioners, despite the mathematical details. Chapter 3 introduces hierarchical CPNs. It starts with an informal description, which is well supported by examples and ends with formal definitions, which are clear and well discussed. Chapter 4 discusses the properties of CPNs. Each property is described first informally with adequate examples and then formally, with the usual clarity. Chapter 5 presents the occurrence graph, shows how to use it to prove properties, and illustrates reduction techniques that can reduce the size of the occurrence graph, such as symmetry, stubborn sets, and invariants. Chapter 5 is only a first look at the complex world of formal analysis of CPNs. The topic is further addressed in a second volume by the same author [1]. Chapter 6 discusses tools for supporting CPNs. It tends to overemphasize obvious functionalities and underestimate the general background derived by the common use of graphical tools; this results in the least exciting chapter of the book.

Chapter 7 is an excellent presentation of examples of industrial size, which can satisfy practitioners interested in the possible impact of CPNs on industrial-scale examples, as well as theoreticians interested in the practical implications of the theory. The preface mentions a third volume for a deeper discussion of industrial-scale examples: unfortunately, I have not seen this volume. Each chapter concludes with an excellent overview of the related literature and a set of exercises that can be helpful for students.

This is definitely the best book for courses on coloured Petri nets. The independence of the chapters makes the book suitable for different audiences, from a practical-minded audience that can look at chapter 1, at first two sections of chapter 3, and chapters 6 and 7, to a theoretically-minded audience that can enjoy the excellent discussion of the formal details.

- M. Pezzé, Milan, Italy

REFERENCES

[1] JENSEN, K. Coloured Petri nets: basic concepts, analysis methods and practical use, vol. 2. Springer, New York, 1995. See CR, Rev. 9608-0565.

GENERAL TERMS: LANGUAGES, THEORY, VERIFICATION


Preface

This book presents a coherent description of the theoretical and practical aspects of Coloured Petri Nets (CP-nets or CPN). It shows how CP-nets have been developed ­ from being a promising theoretical model to being a full-fledged language for the design, specification, simulation, validation and implementation of large software systems (and other systems in which human beings and/or computers communicate by means of some more or less formal rules). The book contains the formal definition of CP-nets and the mathematical theory behind their analysis methods. However, it has been the intention to write the book in such a way that it also becomes attractive to readers who are more interested in applications than the underlying mathematics. This means that a large part of the book is written in a style which is closer to an engineering textbook (or a users' manual) than it is to a typical textbook in theoretical computer science. The book consists of three separate volumes.

The first volume defines the net model (i.e., hierarchical CP-nets) and the basic concepts (e.g., the different behavioural properties such as deadlocks, fairness and home markings). It gives a detailed presentation of many small examples and a brief overview of some industrial applications. It introduces the formal analysis methods. Finally, it contains a description of a set of CPN tools which support the practical use of CP-nets. Most of the material in this volume is application oriented. The purpose of the volume is to teach the reader how to construct CPN models and how to analyse these by means of simulation.

The second volume contains a detailed presentation of the theory behind the formal analysis methods ­ in particular occurrence graphs with equivalence classes and place/transition invariants. It also describes how these analysis methods are supported by computer tools. Parts of this volume are rather theoretical while other parts are application oriented. The purpose of the volume is to teach the reader how to use the formal analysis methods. This will not necessarily require a deep understanding of the underlying mathematical theory (although such knowledge will of course be a help).

The third volume contains a detailed description of a selection of industrial applications. The purpose is to document the most important ideas and experiences from the projects ­ in a way which is useful for readers who do not yet have personal experience with the construction and analysis of large CPN diagrams. Another purpose is to demonstrate the feasibility of using CP-nets and the CPN tools for such projects.

Together the three volumes present the theory behind CP-nets, the supporting CPN tools and some of the practical experiences with CP-nets and the tools. In our opinion it is extremely important that these three research areas have been developed simultaneously. The three areas influence each other and none of them could be adequately developed without the other two. As an example, we think it would have been totally impossible to develop the hierarchy concepts of CP-nets without simultaneously having a solid background in the theory of CP-nets, a good idea for a tool to support the hierarchy concepts, and a thorough knowledge of the typical application areas.

ISBN: 3-540-55597-8 (first edition)
ISBN: 3-540-60943-1 (second edition)