Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1987 | Buch

Introduction to Part I Kapitel lesen Erstes Kapitel lesen

Petri Nets: Central Models and Their Properties

Advances in Petri Nets 1986, Part I Proceedings of an Advanced Course Bad Honnef, 8.–19. September 1986

herausgegeben von: W. Brauer, W. Reisig, G. Rozenberg

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Petri Nets represent a long and sustained effort· to develop concepts, theories and tools to aid in design and analysis of concurrent systems. They are used in many areas of computer science including software engineering, data base and in­ formation systems, computer architecture and operating systems, communication protocols and computer networks, process control, and socio-technical systems such as office communication and man-machine interaction. Quite substantial theory has been developed for Petri Nets. It reflects all major problem areas of concurrent distributed systems and covers many successfully applied principles and analysis techniques for systems organisation. Since the time that C. A. Petri has presented his original ideas, a rich body of knowledge has been developed-a recent bibliography (in Advances in Petri Nets 1981) includes more than 2000 entries. Already in 1979 an Advanced Course on Petri Nets was organized in Hamburg, West Germany, aiming at systematizing the existing knowledge and making it well accessible to a wide audience of computer scientists interested in theory and applications of concurrent systems. This course has turned out to be successful in the sense that it has initiated a lot of new research into applications and theory of Petri Nets. This had led to· another Advanced Course in 1986 in Bad Honnef, West Germany - where during two weeks more than 30 lectures were presented covering the most important current developments in the area of Petri Nets.

Inhaltsverzeichnis

Frontmatter

Introduction to Part I

Introduction to Part I
Abstract
In Part I of this book a number of central Petri Net models is presented and their properties discussed. In this way a firm formal basis is set for developing the theory of Petri Nets as well as for the numerous efforts to adopt Petri Nets to a wide range of applications.
W. Brauer, W. Reisig, G. Rozenberg

Prologue

Frontmatter
Concurrency Theory
Abstract
A great amount of work is being done today in the area of parallel information processing and supercomputation, and it is no longer considered extravagant to talk of 64 K or more processors being concurrently active at a single task. All technical problems of interconnecting many processors seem to be essentially solved, but it remains difficult to distribute and to organize a large task so as to extract the full advantage from the availability of a multitude of processors.
Carl Adam Petri

Elementary Net Systems — Fundamentals

Frontmatter
Elementary Net Systems
Abstract
Our aim will be to introduce and discuss the basic system model of net theory called Condition/Event Systems. We shall start with a brief discussion of the twin notions of states and transitions as viewed within net theory. This will motivate the restrictions placed on the Condition/Event System model. We shall then introduce nets and construct Condition/Event Systems with the help of nets.
A major objective will be to use our system model to formalize the fundamental situations associated with the behaviour of a distributed system. In particular, we shall consider phenomena such as conflict (choice), concurrency and confusion. This will then lead to the identification of a number of interesting behavioural sub-classes of Condition/Event Systems.
P. S. Thiagarajan
Behaviour of Elementary Net Systems
Abstract
We consider two ways of recording the behaviour of an elementary net system (EN system): via sequential observations and via non-sequential observations. In the sequential point of view each record of the behaviour of an EN system is a string of event occurrences (called a firing sequence) as registered by a sequential observer. In the nonsequential point of view we can define the behaviour of an EN system by either extracting causal order of events from firing sequences (obtaining firing traces) or by recording all nonsequential observations of event occurrences and of resulting holdings of conditions (each such record is called a process). In our contribution we discuss each of the three approaches and then relate them to each other.
G. Rozenberg
Non-Sequential Processes
Abstract
This paper present a selection of some properties of a non-sequential process.
Three types of properties are studied, namely: discreteness properties, density properties and the D-continuity property. Relations between these properties are established.
César Fernández

Place/Transition Systems — Fundamentals

Frontmatter
Place/Transition Systems
Abstract
In the 1970ies, Place/Transition Systems were certainly the most common and the most extensively studied class of nets. Often they have just been called Petri Nets.
We introduce their basic concepts, viz. the idea of places that carry any number of (identical) tokens. This introduces a dimension of infinity that implies a lot of interesting theoretical problems such as liveness, boundedness and the reachability of markings.
We especially stress the viewpoint of General Net Theory, considering such nets as shorthand notation for elementary net systems. In this way the rich body of theory for c/e systems is applicable also for place/ transition nets. Finally we will study net properties that can be derived from coverability trees.
Wolfgang Reisig
Linear Algebraic Techniques for Place/Transition Nets
Abstract
This paper is an introdurction into linear algebraic techniques for place/transition nets. Based on a linear representation of processes S- and T-invariants are introduced. S- and T-invariants are both, solutions of linear homogeneous equation systems and subnets with special properties.
Kurt Lautenbach
Structure Theory of Petri Nets: the Free Choice Hiatus
Abstract
Structure theory asks whether a relationship can be found between the behaviour of a marked net and the structure of the underlying unmarked net. From the rich body of structure theoretical results that exists in Petri net theory, this paper selects a few examples which are deemed to be typical. The class of free choice nets, whose structure theory is particularly agreeable, is studied in some detail.
Eike Best

High-Level Nets — Fundamentals

Frontmatter
Predicate/Transition Nets
Abstract
The paper deals with conceptual, mathematical and practical aspects of developing a net theoretic system model. The model presented is based on common techniques of modelling static systems as structured sets of individuals (relational structures). These structures are ‘dynamised’ by allowing some relations between individuals to be changed by the processes of the modelled system.
Hartmann J. Genrich
Coloured Petri Nets
Abstract
This paper describes a Petri net model, called Coloured Petri nets (CP-nets), where information is attached to each token. The information can be inspected and modified when a transition fires. For most applications, this generalization of ordinary Petri nets allows the user to make more manageable descriptions, due to the fact that equal subnets can be folded into each other, yielding a much smaller net. The paper investigates how to analyse Coloured Petri nets. It turns out that place-invariants and reachability trees, two of the most important methods for ordinary Petri nets, can be generalized to apply for Coloured Petri nets.
Coloured Petri nets and Predicate/transition-nets are very closely related to each other, in the sense that Coloured Petri nets have been developed as a modification of Predicate/transition-nets, in order to avoid some technical problems which arise when the method of place-invariants is generalized to apply for Predicate/transition-nets.
Kurt Jensen
Analysing Nets by the Invariant Method
Abstract
Methods for analysing P/T-systems can be roughly divided into several categories: study of the reachability set, transformation by homomorphism, and invariants. Each of these methods have advantages and disadvantages.
G. Memmi, J. Vautherin

Special Topics

Frontmatter
Synchronic Distance
Abstract
The concept of synchronic distance is introduced and motivated by S-completion. A definition based on processes of C/E-systems is given and several properties are proved. Weighted synchronic distances are shortly discussed.
Ursula Goltz
Transformations and Decompositions of Nets
Abstract
We present a set of transformations of place/transition systems which preserve several classical properties of nets namely boundedness, deadlock freeness, liveness and covering by S-invariants. These transformations may simplify or refine a system and allow either to simplify a place/transition system before analysing it or to introduce more details in a given system having some propreties without changing them. We also present a decomposition technique to split a system into subsytems which can be analysed separatly.
G. Berthelot
Infinite Behaviour and Fairness
Abstract
Specification techniques for the infinite behaviour of a P/T-system are introduced and their expressive power is compared. In particular, fair behaviour is related to the wellknown liveness problem. Finally, the problem is studied how to implement fair behaviour using a fair occurrence rule for transitions.
Rudiger Valk
Language Theory of Petri Nets
Abstract
Petri nets where multiple arcs are allows and the capacity of the places need not be bounded are here called Place/Transition systems. The restrictions of the possible finite or infinite occurence sequences of a P/T-system to the transitions are called transition sequences and give the basis to define families of formal languages related to classes of P/T-systems.
We introduce the notation and give a survey on methods and results about sets of finite transition sequences. We will compare the classes of Petri net languages we obtain with other families of languages known from automata and formal language theory. We hope to convince that these techniques and results are useful for the formulation and solution of certain questions about P/T-systems, as well as for comparing the underlying systems.
Matthias Jantzen
Complexity of Place / Transition Nets
Abstract
This is a survey of results about the complexity of decision problems for various questions about Petri nets that arise in the analysis of systems. The border between undecidable and decidable problems is discussed first and then problems are presented by decreasing complexity. As a consequence of the results presented it will follow that one has to concentrate on very restricted classes of systems in order to get practically relevant algorithms that work well for all cases, since even seemingly simple classes of Petri nets have simple problems with a provable high lower bound for the complexity of their sol’ution.
Matthias Jantzen

Other Petri Net Models

Frontmatter
FIFO — Nets
Abstract
This paper presents a survey of applications and theoretical properties of FIFO-nets, i.e. Place-Transition nets in which places behave as FIFO-queues rather than counters. In the first part, the adequacy of FIFO-nets for solving generic synchronization problems is shown and their impact on the fairness property of a concurrent system is discussed. The second part is devoted to the study of the computational power of this model as well as the characterization of some sub-classes for which some classical properties become decidable (liveness, boundedness). Finally, the notion of T-invariant for FIFO-nets is introduced.
Gérard Roucairol
Stochastic Nets and Performance Evaluation
Abstract
This paper is an introduction to the so-called stochastic Petri nets. It contains a critical overview of the most representative stochastic Petri net classes (Stochastic Petri Nets, both in Florin-Natkin and in Molloy form, Generalized Stochastic Petri Nets, Extended Stochastic Petri Nets). Their application to performance evaluation is discussed. A bibliograhy for furthering the subject is given in the appendix.
Anastasia Pagnoni
Backmatter
Metadaten
Titel
Petri Nets: Central Models and Their Properties
herausgegeben von
W. Brauer
W. Reisig
G. Rozenberg
Copyright-Jahr
1987
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-47919-2
Print ISBN
978-3-540-17905-4
DOI
https://doi.org/10.1007/978-3-540-47919-2