Petri Net Theory and the Modeling of Systems

This book is now available, in either print or Kindle versions from Amazon.

This is an HTML version of Petri Net Theory and the Modeling of Systems It has been published. It should be referred to as:

James L. Peterson, Petri Net Theory and the Modelling of Systems, Prentice-Hall, Englewood Cliffs, New Jersey, (April 1981), 290 pages. Translated into Russian and Japanese.

This version does not have the figures that are associated with the printed version. I expect to scan those in, but have not had an opportunity to do so yet (September 1998).

Contents

Preface

Acknowledgements

Chapter 1. Introduction

1.1. Modeling

1.2. Features of Systems

1.3. The Early Development of Petri Nets

1.4. Applying Petri Net Theory

1.5. Applied and Pure Petri Net Theory

1.6. Further Reading

1.7. Topics for Further Study

Chapter 2. Basic Definitions

2.1. Petri Net Structure

2.2. Petri Net Graphs

2.3. Petri Net Markings

2.4. Execution Rules for Petri Nets

2.5. Petri Net State Spaces

2.6. Alternative Forms for Defining Petri Nets

2.7. Further Reading

2.8. Topics for Further Study

Chapter 3. Modeling with Petri Nets

3.1. Events and Conditions

3.2. Concurrency and Conflict

3.3. Computer Hardware

3.3.1. Finite State Machines

3.3.2. Pipelined Computers

3.3.3. Multiple Functional Units

3.4. Computer Software

3.4.1. Flowcharts

3.4.2. Parallelism

3.4.3. Synchronization

3.4.4. The Mutual Exclusion Problem

3.4.5. The Producer/Consumer Problem

3.4.6. The Dining Philosophers Problem

3.4.7. The Readers/Writers Problem

3.4.8. P and V Systems

3.5. Other Systems

3.6. Further Reading

3.7. Topics for Further Study

Chapter 4. Analysis of Petri Nets

4.1. Analysis Problems for Petri Nets

4.1.1. Safeness

4.1.2. Boundedness

4.1.3. Conservation

4.1.4. Liveness

4.1.5. Reachability and Coverability

4.1.6. Firing Sequences

4.1.7. Equivalence and Subset Problems

4.2. Analysis Techniques

4.2.1. The Reachability Tree

4.2.2. Matrix Equations

4.3. Further Reading

4.4. Topics for Further Study

Chapter 5. Complexity and Decidability

5.1. Reducibility Between Analysis Problems

5.2. Reachability Problems

5.3. Limited Petri Net Structures

5.4. Liveness and Reachability

5.5. Undecidable Results

5.5.1. The Polynomial Graph Inclusion Problem

5.5.2. Weak Computation

5.5.3. The Equality Problem

5.6. Complexity of the Reachability Problem

5.7. Further Reading

5.8. Topics for Further Study

Chapter 6. Petri Net Languages

6.1. Motivation

6.2. Related Formal Language Theory Concepts

6.3. Definitions of Petri Net Languages

6.3.1. Initial State

6.3.2. Labeling of Petri Nets

6.3.3. Final States of a Petri Net

6.3.4. Classes of Petri Net Languages

6.4. Properties of Petri Net Languages

6.5. Closure Properties

6.5.1. Concatenation

6.5.2. Union

6.5.3. Concurrency

6.5.4. Intersection

6.5.5. Reversal

6.5.6. Complement

6.5.7. Repeated Composition

6.5.8. Substitution

6.6. Petri Net Languages and Other Classes of Languages

6.6.1. Regular Languages

6.6.2. Context-Free Languages

6.6.3. Bounded Context-free Languages

6.6.4. Context-sensitive Languages

6.7. Additional Results

6.8. Further Reading

6.9. Topics for Further Study

Chapter 7. Extended and Restricted Petri Net Models

7.1. Limitations of Modeling with Petri Nets

7.2. Extensions

7.2.1. Constraints

7.2.2. Exclusive-OR Transitions and Switches

7.2.3. Other Extensions

7.3. Extended Petri Nets and Register Machines

7.4. Subclasses of Petri Nets

7.4.1. State Machines

7.4.2. Marked Graphs

7.4.3. Free-choice Petri Nets

7.4.4. Simple Petri Nets

7.5. Further Reading

7.6. Topics for Further Study

Chapter 8. Related Models of Parallel Computation

8.1. Finite State Machines

8.2. Marked Graphs

8.3. Computation Graphs

8.4. P/V Systems

8.5. Message Transmission Systems

8.6. UCLA Graphs

8.7. Vector Addition and Replacement Systems

8.8. Extended Petri Net Models

8.9. Further Reading

8.10. Topics for Further Study

Appendix A. A Brief Theory of Bags

A.1. Membership

A.2. Cardinality

A.3. Bag Inclusion and Equality

A.4. Operations

A.5. Bag Spaces

A.6. Parikh Mappings

A.7. Examples

Appendix B. Annotated Bibliography