Skip to main content

2013 | Buch

Time and Petri Nets

verfasst von: Louchka Popova-Zeugmann

Verlag: Springer Berlin Heidelberg

insite
SUCHEN

Über dieses Buch

At first glance the concepts of time and of Petri nets are quite contrary: while time determines the occurrences of events in a system, classic Petri nets consider their causal relationships and they represent events as concurrent systems. But if we take a closer look at how time and causality are intertwined we realize that there are many possible ways in which time and Petri nets interact. This book takes a closer look at three time-dependent Petri nets: Time Petri nets, Timed Petri nets, and Petri nets with time windows.

The author first explains classic Petri nets and their fundamental properties. Then the pivotal contribution of the book is the introduction of different algorithms that allow us to analyze time-dependent Petri nets. For Time Petri nets, the author presents an algorithm that proves the behavioral equivalence of a net where time is designed once with real and once with natural numbers, so we can reduce the state space and consider the integer states exclusively. For Timed Petri nets, the author introduces two time-dependent state equations, providing a sufficient condition for the non-reachability of states, and she also defines a local transformation for converting these nets into Time Petri nets. Finally, she shows that Petri nets with time-windows have the ability to realize every transition sequence fired in the net omitting time restrictions.

These classes of time-dependent Petri nets show that time alone does not change the power of a Petri net, in fact time may or may not be used to force firing. For Time Petri nets and Timed Petri nets we can say that they are Turing-powerful, and thus more powerful than classic Petri nets, because there is a compulsion to fire at some point in time. By contrast, Petri nets with time-windows have no compulsion to fire, their expressiveness power is less than that of Turing-machines.

This book derives from advanced lectures, and the text is supported throughout with examples and exercises. It is suitable for graduate courses in computer science, mathematics, engineering, and related disciplines, and as a reference for researchers.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
The objective of this book is to bring into accordance the two obviously completely contrary concepts of time and Petri nets. Introduced by C. A. Petri in [Pet62], Petri nets can be used to study concurrency in the sense of causal independence, but they do not directly deal with time; time is involved only implicitly through the causal relationships. However, the explicit indication of time is indispensable for a great variety of real problems. Even qualitative studies of strongly time-dependent systems are very inexact if time is included only implicitly through causality. The question arises, whether one should at all try to describe and analyze such systems using Petri nets and whether it is even possible.
Louchka Popova-Zeugmann
Chapter 2. The Classic Petri Net
Abstract
In this chapter the basic principles of classic Petri net theory are introduced and basic properties are explained. With the latter, the emphasis will not be on a complete listing but on the systematization of qualities as static or dynamic and qualitative or quantitative.
Louchka Popova-Zeugmann
Chapter 3. Time Petri Nets
Abstract
In this chapter we study Time Petri nets: After the introduction of this kind of time-dependent Petri net, we will discuss variations of the rules defining the possible state changes. We then show how to reduce the state space of an arbitrary Time Petri net to a discrete one and use this to study the dynamic behavior of these time-dependent Petri nets under both qualitative and quantitative aspects.
Louchka Popova-Zeugmann
Chapter 4. Timed Petri Nets
Abstract
In this chapter we consider a further important class of time-dependent Petri nets, the Timed Petri nets. In any real system every event takes some amount of time, no matter how small. In Timed Petri nets this fact is incorporated by associating a duration with each transition. To model a real system with a Timed Petri net the duration of a transition is set to the duration of the event or process modeled by this transition. Therefore, in most studies on Timed Petri nets, durations of length zero are not considered, but allowing time durations of certain events to be zero can be very useful for practical reasons. If, for instance, we want to model events of which one has a very small time duration compared with the others, then it might be convenient to set the small duration to zero, in order to avoid using huge values for the durations of the other events. Later on, this simplifies the analysis of the net.
Louchka Popova-Zeugmann
Chapter 5. Petri Nets with Time Windows
(Petri Nets with Retention Time on Places)
Abstract
The last time extension of Petri nets introduced in this book are Petri nets with retention time on places and we show ways to analyze them. They were first devised as a formal specification technique for designing complex automaton systems. Most important for this application are the possibilities for system diagnostics, namely error detection, localization, evaluation, recognition and reaction. It is important to minimize the total time needed for the internal diagnostic process of the system; considering only the causal relationships between events is therefore not sufficient.
Louchka Popova-Zeugmann
Backmatter
Metadaten
Titel
Time and Petri Nets
verfasst von
Louchka Popova-Zeugmann
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-41115-1
Print ISBN
978-3-642-41114-4
DOI
https://doi.org/10.1007/978-3-642-41115-1