Skip to main content

1982 | Buch

Application and Theory of Petri Nets

Selected Papers from the First and the Second European Workshop on Application and Theory of Petri Nets Strasbourg, 23.–26. September 1980 Bad Honnef, 28.–30. September 1981

herausgegeben von: Claude Girault, Wolfgang Reisig

Verlag: Springer Berlin Heidelberg

Buchreihe : Informatik-Fachberichte

insite
SUCHEN

Über dieses Buch

This volume documents the progress of application and theory of Petri Nets since the Advanced Course on General Net Theory of Processes and Systems, held in Hamburg, October 8-19, 1979, This course presen ted in detail wha t had been achieved in this area since the first studies of concurrent systems 20 years ago, After this course it seemed worthwhile to establish a co-operation between different groups working in the field of Petri N ets, The starting points were the AFCET Special Interest Group "Systemes Paralleles et Distribues" and the Gl Special Interest Group "Petrinetze und verwandte Systemmodelle", Meanwhile, group s of many European countries are involved, A main activity of this co-operation is the realization of workshops in varying European countries, The first workshop of this kind was carried out in Strasbourg (France), September 23-26, 1980, The second one took place in Bad Honnef (Germany) September 28-30, 1981. This volume contains contributions of these two workshops, The 1980 workshop in Strasbourg was partitioned into 6 topics : (1) Application of Nets to Realtime Systems, (2) Programming Languages and Software Engineering, (3) Information Flow and Concurrency, (4) Net Morphisms and High Level Petri Nets, (5) Mathematical Analysis and N et Languages, (6) Reliability and Recovery Issues, In this volume, the chairman of each topic gives a short introduction to his area whict should help to understand its specific problems and to in troduce the presented papers,

Inhaltsverzeichnis

Frontmatter

Papers of the First European Workshop on Application and Theory of Petri Nets

Frontmatter

Application of Nets to Real-Time Systems

Overview on Topic 1: Application of Nets to Real-Time Systems

Despite the ability of nets to describe fundamental concepts in concurrency and the number of analytic tools that have been provided, it is wellknown that modelling concrete systems with place-transition nets leads generally to large unreadable and unmanageable nets.

G. Roucairol
Petri Net Modelling and Reliability of Distributed Algorithms

In distributed systems most difficulties come from parallelism. The multiplicity of sites but also the repetitions due to losses of informations and to recoveries of crashed sites induce a combinatorial proliferation of possible system states. This makes difficult to study the conjonctions of normal actions, failures and recoveries and to obtain more than a superficial confidence of the reliability of algorithms. Thus a methodology oriented toward the modelling of parallelism is needed for the analysis of distributed algorithms and protocols.

G. Berthelot, C. Girault, G. Roucairol
Using Petri-Nets in Measurement of a Distributed Data Base System

Measurement during data base life is a necessity to manage it and keep good performances. We shall explain two problems of distributed data base system, which impact the global performances. We have choose in SIRIUS-DELTA to make a permanent measurement system closely related to the algorithm’s model.

P. Rolin
On the Problem of Time in Nets

We use Timed Petri Nets (TPN) in our general modelling tool for sociotechnical systems, called Function Nets. Our interest is to find the general differences in behaviour between Petri Nets and TPN. The influence of timing to basic net-properties is discussed: The time-concept imposes a restriction to the set of firing-sequences in a given net, which in turn influences the liveness of the net. The standard-liveness is not suitable for our purpose. The use of more basic liveness-definitions is suggested. A modelling example utilizing a TPN is given.

Heinrich P. Godbersen

Programming Languages and Software Engineering

Overview on Topic 2: Programming Languages and Software Engineering

Nets are being taken seriously as one of the tools which might turn software development into an engineering discipline. However, there are two different viewpoints on the role they have to play: a)as a notation for recording and presenting the analyst/designer’s evolving understanding of the system behaviour andb)as a means of defining the semantics of the concurrency/communication primitives of system design languages so that critical adequacy properties (liveness, safeness etc.) of systems designed in such languages may be determined analytically.

B. Cohen
Transforming nets along the syntactic production of programs

The semantics of the process control language PEARL has been described in a semi-formal way for the German Standard DIN 66 253 Part 2. The techniques used there, especially the connectors between sets of nodes in nets, are outlined here.

Eberhard Wegner
Design-Review by Petri-Nets

This paper intends to show,that there is a morphism between the description of a system by the HIPO-technique and a certain type of Petri-nets.This morphism is used to detect design-errors at a very early state, where data for testing are not yet available.

Ernst Grill
Concurrency in Functional Descriptions

Functional descriptions are used to specify digital systems in the design method showed in /1, 2, 3/. They are formulated in a language called RNL /4, 5/. To obtain the control structure and the topology of the data structure of the specified digital system, functional descriptions are converted into an intermediate model, a net, by the algorithms given in /3/. The intention of this paper is to show how concurrency is defined and how it is introduced into a functional description. It is investigated, in which way different, equivalent degrees of concurrency can be derived and maximized, and how the notion of maximal concurrency is influenced by the restrictions imposed on the functional descriptions.

Raul Camposano
RNL — A Language for Digital Systems Design Based on Nets

The register net language (RNL) was introduced to provide a description of the functions to be designed and implemented by hardware /4/. This description consists of operations and a relation concerning their logical dependencies. The operations change or preserve information contained in the storage elements of the register transfer structure. Each operation is described by an operator and the corresponding input and output registers /1/. Thus, an RNL-program describes the flow of data through the register transfer structure.

Wolfgang Rosenstiel
Galileo: A Methodology for Modelling and Designing Real Time Systems

The identification, ambiguity, relativity, and recursivity of the concepts related to Real Time Systems and Software, in particular, have created a problem in the understanding and designing of these systems. Other problems have complicated this situation even more. But instead of evaluating these problems, we are going to present an overview of our solution, obtained during the course of the Galileo project, (l).

F. Vidondo, I. López
Petri Nets and Semantics of System Descriptions

The full version of this paper has been published as: DAIMI PB-116, Computer Science Department, Aarhus University. It can be requested from the address above.

Kurt Jensen, Morten Kyng

Information Flow and Concurrency

Overview on Topic 3: Information Flow and Concurrency

The range of papers addressed to this topic made it seem convenient that it be split into two separate parts.

E. Best
The Relationship Between Time and Information

The general problem of interest is the development of a mathematical theory capable of describing the behavior and properties of data processing systems. Data processors do something sometimes called “work”, they have the ability to make accomplishments sometimes called “thruput”, and they have a consequent “response time”. This particular analysis describes a way to relate time and information in a way that will subsequently facilitate analysis and measurement of computer “work”.

Robert R. Johnson
Information Flow in Nets

The concept of “information flow” in programs is at the same time significant and elusive. The intuitive informational analysis of a simple program such as the following, however, presents no great difficulty. Let x,y e {0,1} be binary variables and consider (1)$$\left( {x,y} \right): = \left( {x \wedge y,x \oplus y} \right)$$ where ∧ and ⨁ denote “logical and” and “exclusive or”, respectively.

Eike Best
An Exercise in Processes with Infinite Pasts

We present some mathematical results on modelling processes with possibly infinite pasts. We intend the word “process” to be close in spirit to “real process” in [Pet] and “process” in [Bes]. They do not assume a process to have an initial state. As in [Nie], where an initial state was assumed, we work with event structures rather than causal nets. The event structures will be essentially causal nets without conditions.

Glynn Winskel
Two Alternative Definitions of Synchronic Distance

The purpose of this note is to present two closely related definitions of the notion of synchronic distance. We have developed these definitions because we feel that they might be easier to grasp and to work with than the original definition given in [1].

Goltz, Reisig, Thiagarajan
On the Construction of System Nets

In different fields, not only in the field of computer science, the net theory has found increasing applicability. The Advanced Course on ‘General Net Theory of Processes and Systems’ clarified the role of the net theory. The main difference between net theory and other system theories is that it renounces a universal time scale as a basis of its theory. Instead net theory relies on an empirically determined concurrency relation /Pet77/.

Gert Scheschonk

Net Morphisms and Higher Level Net Interpretations

Overview on Topic 4: Net Morphisms and Higher Level Net Interpretations

Discussion about real systems means to relate them, e. g. to compare their properties or capabilities. If real systems are represented by nets, relations between systems are transformed to relations between nets. It appeared that such relations are not arbitrarily; rather, they fulfill some properties which are condensed in the notion of net morphism. Roughly a net morphism is a mapping which either respects of collapses arrows of the source net.

W. Reisig
Net Morphisms and Software Engineering

The best general method that is known for dealing with the complexity of such large software systems as compilers and operating systems is that of structuring. Structuring itself is of course a very difficult task, where many different and not yet very well understood rules must be observed. Nevertheless methods and tools have been and will be developed to assist this purpose. “Structured Programming”, “Modularity”, “SADT”, “HIPO” and “Jackson” are some keywords that should be mentioned in this context. Even though the methods developed so far have proved helpful for the construction of software systems, they are usually restricted to the design of sequential systems in addition to being not very well formalized, which prevents consistency checking and other analytical examinations in most cases.

Dimitrios Christodoulakis, Matthias Moritz
An Equivalence-Notion For Condition/Event-Systems

According to our point of view the relevant question “When are two processes or two Condition/Event-Systems (C/E-System) equivalent?” is not thoroughly discussed yet in the general net theory.

Engin Sirmen
Recursive Nets

Recursion is a widespread definition priciple in computer science. It allows for finite characterizations of infinite objects and provides tools for the construction of initial segments of these infinite objects. A special yet important subclass of recursion is iteration (which needs no storing of provisional results).

W. Reisig
Behaviour of a Place-Transition Net on a Subset of Transitions

Place-transition nets are often used to model concurrent systems. The increase of the number of concurrent events in a system, can make the analyses unfeasable. The substitution of a subnet, modelling a subsystem, by an equivalent but simpler net, is a way to reduce the analysis complexity.

C. Andre
Stepwise Refinements of Transitions and Places

It is known [1] that Petri nets can model a system hierarchically, i. e., a transition or a place of a Petri net representing a system at an abstract level can be refined to model the system in more detail, and conversely, a portion of a Petri net may be replaced by a transition or by a place to give a more abstract description of the system.

I. Suzuki, T. Murata
Transfer of graph constructs in Goguen’s paper to net constructs

Goguen /1/ presents in his paper a definition of sequential programs with a given graph as flow diagrams and a definition of program homomorphism which allows to contract and expand paths. The nodes of a flow diagram correspond to global state vectors, and the paths between two nodes correspond to the global state transformations of the program.

Wolfgang Hinderer
Structural Modifications in Net Theory

In real-world systems we can distinguish two different modes of behaviour: 1. the “normal” functioning of the system, and 2. a modification of system structure, which may happen from time to time.

Dieter Gernert

Mathematical Analysis and Net Languages

Overview on Topic 5: Mathematical Analysis and Net Languages

There were ten contributions to this topic which included the following four methods for the analysis of place/transition nets (which we will call “nets” in the sequel): transformation of methods from the verification of sequential programsgraph-theoretical methodsmethods known from formal language theory andmethods known from the formal logic

O. Herzog, R. Valk
Interactive Methods for the Analysis of Petri Nets

The aim of this paper is to show how the iterative methods for the analysis of discrete systems presented in [1][2][3] can be applied to Petri nets and their extensions. The results given in this paper have been obtained by direct application of those exposed in the references.

J. P. Queille, J. Sifakis
Inductive Assertions for Analyzing Reachability Sets

It is scetched how the inductive assertion method of Floyd/Hoare and the termination proof method of Floyd/Manna can be used for the analysis of reachability sets for arbitrary initial transition systems.

Horst Müller
Leakage Notion

The leakage notion was introduced in [5], and its symetric notion in [4] or [6].The aim of this work is to obtain a general tool in order to analyse liveness and boundedness in Petri nets, independently of the initial marking. Our results submitted striking analogies with other results based upon linear algebra. In this paper, after submitting some notations, we introduce the notion of weak leakage from which we deduce a necessary condition for a Petri net to be live. This condition is independent of the initial marking, implies the two first ones, and like the two first ones’shows a symetric notion.

G. Memmi
Graph-Theoretical Analysis of A Subclass of Petri-Nets

In this paper, an informal description of a Petri Net subclass is given, which is described in more detail in /HE79/. A diagram will be presented describing the relationship of that subclass to other well-known subclasses. A slightly different notion of liveness (compared to other approaches) is explained by an example, which is related to an interpretion in the area of concurrent programs. Finally, the same example /LAT/ of a non-live Petri Net is analysed as in /MEM/ (contained in these proceedings). The most important steps of the graphtheoretical analysis are shown.

Otthein Herzog
Synthesis of Concurrent Systems

This is a contribution towards a methodology for the synthesis of concurrent systems consisting of suitably cooperating sequential processes, particularly synchronization systems and communication protocols.

Michael Yoeli
Subclasses of Self-Modifying Nets

Petri nets (PT-nets) have proved as an excellent tool for the description and analysis of dynamic systems exhibiting concurrency. Nevertheless applications to problems in practice are rare. Among others one reason is that Petri nets for complex systems rapidly grow in size soon loosing their clearness and becoming unmanageable. In order to increase the abilities of Petri nets several extensions have been suggested in a more or less systematic way (e. g., inhibitor, reset arcs, transitions with special properties etc.).

B. Heinemann
Test on Zero in Petri Nets

In this note we discuss some aspects of nets (i. e. Petri-nets, place/transition nets, P/T-nets) augmented by inhibitor arcs. An inhibitor arc connects a transition t with a place p. For such a transition the firing rule is modified as follows. Transition t fires under the usual conventions, when p is empty, but is inhibited from firing, if p contains at least one token. This behaviour can be represented by ordinary nets only in those cases, where p is a bounded place. Nets, where inhibitor arcs are allowed, will be called inhibitor nets or I-nets in this paper.

Rüdiger Valk
Deterministic Languages of Petri Nets

One way of using Petri nets for modelling systems is to represent states by markings, and actions that modify the states by transitions. In order to represent the fact that one event can cause different modifications of the system, one has to label the transitions. For example, in a school, the beginning and the end of classes are signalled, or labelled, by the ringing of a bell. One possible way of investigating the functioning of a system is to examine the sequences of labels corresponding to the firing sequences of transitions of the Petri net that models the system. Several classes of languages have been defined and studied: languages of sequences of firing of transitions when one event or signal causes one action, and languages of words labelling firing sequences of transitions when one event can cause several actions.

G. Vidal-Naquet
A Study of the Projection Operation

By the projection of words or languages to a set of symbols the omission of all those ones not belonging to the given set is meant. This operation has a fundamental role in the algebraic representation of concurrent behaviour of sequential processes. Namely, permissible sequences of a superposed (merged) system of sequential components fin the sense of [43 and [8] have the characteristic property that when projecting one of them into any of the components the resulting sequence will also be a permissible one for that component.

E. Knuth, Gy. Györy, L. Ronyai

Reliability and Recovery Issues

Overview on Topic 6: Reliability and Recovery Issues

List of the participants in the discussion: C. André, C. Girault, H. Godbersen, W. Hinderer, M. Morganti, P. Rolin, G. Roucairol, U. Scholtze, R. Valette, (The discussion concerned topic Nr 1 “Application of Nets to Realtime Systems” and topic Nr 6 together)The discussion concerning topics Nr 1 and Nr 2 can be summarized by the following questions: how to manage a problem?how to obtain a Petri net describing a system?These two questions reflect probably quite well the positions of the designers that decide to utilize Petri nets. They are convinced of the analytical power of this tool but when they tackle actual systems they obtain hudge unreadable nets and loose heart. In fact no general methodology to use Petri nets is. available.

R. Valette
Petri-Net Implementation of Recovery Strategies in a Large ESS

A practical experience of design with Petri-nets is described, which basically consists in the analysis and implementation of recovery strategies within the project of a large stored program controlled electronic switching system.Emphasis is put on the optimum adequacy of Petri-nets for the analysis and representation of all fault-tolerance related phenomena.Net tailoring and adaptation to the peculiar application is also briefly discussed together with a short outline of the interactive design aids specially developed for this purpose.A summary of unsolved or still open problems, all of which are currently under study concludes the presentation.

M. Morganti
Petri Nets and Reliable Real-Time Systems

The zero-test problem is a well-known limitation of Petri nets, and unfortunately it appears very frequently when reliable real-time systems are concerned. If the Petri net is bounded (it is generally the case when actual systems are specified), the zero-test problem can be solved by the introduction of complementary places. Nevertheless this solution presents three major drawbacks: the specification becomes little readable,the net can rarely be reduced,the information given by the linear invariants does not take into account the elementary loops and therefore the zero-tests.

R. Valette
Towards Fault-Tolerant Real-Time Systems by Using Petri Nets

This paper presents current studies on the use of Petri nets for the design and validation of fault-tolerant distributed systems. Petri nets have been used at the various steps of the design process: initial modeling level definition, static verification and on-line testing. The main context of these studies involves distributed systems for which a crucial problem concerns the ability for the model to design and validate the consistency of the logical behavior for the communication among the processes.

J. M. Ayache, P. Azéma, M. Diaz
Treatment of recovery problems using cuts in Occurrence Nets

In the following I propose a concept of Dynamic Occurrence Nets- These nets are “dynamic” in so far as they contain a “past part” which is an Occurrence Net in the classical sense (i. e. an Occurrence Graph) and a “future part” which is a repetition free condition/event net (/1/ p. 120). They are able to model any concurrent system without folding, and they can serve as internal models in digital computers for treating backward recovery problems /3/.

Wolfgang Hinderer

Papers of the Second European Workshop on Application and Theory of Petri Nets

Frontmatter
Use of the Behaviour Equivalence in Place-Transition Net Analysis

In a previous paper [Andr80] we introduced the notion of the behaviour of a place-transition net on a subset of transitions. The behaviour-equivalence (B-equivalence) was defined and properties preserved by this equivalence were exhibited.

C. Andre
Modeling and Proofs of a Data Transfer Protocol by Predicate/Transition Nets

After a brief introduction to Predicate/Transition Nets, the model of the underlying transmission medium is modeled, according to the properties it has to verify. Then a model of the data transfer phase is described. It allows correction of the errors signalled by the Network level, by using a window mechanism, and control frames for acknowlegdments and rejections. The correctness of the data transfer is demonstrated using invariants. The service provided to the upper level is thus valided.

Gérard Berthelot, Richard Terrat
On the Logic of Concurrency and Conflict

Concurrent actions and non sequential processes are fundamental in any kind of system, not only computing systems; hence, an adequate formalization of these notions is required in order to understand systems and formally treat them, and many attempts have been made in this direction.

G. Mauri, M. Brambilla
Superposed Automata Nets

The capability of representing in an highly communicable way the concurrency among autonomous subsystems is frequently crucial in real systems modelling, whichever the nature of the system can be.

F. De Cindio, G. De Michelis, L. Pomello, C. Simone
Evaluation Based Upon Stochastic Petri Nets of the Maximum Throughput of a Full Duplex Protocol

This paper introduces some principles and tools which can be used to evaluate the maximum throughput of a class of computing processes. The function of these processes is to manage queues in computer systems (device handlers, communication protocols). Our approach is based upon stochastic Petri net models. We show how the theorem on maximum rate (Lavenberg) can be applied to stochastic Petri nets. This theoretical result and a general purpose evaluation software tool allows the numerical evaluation of maximum throughput rates. As an example, the maximum throughput of a full duplex protocol is computed.

Gérard Florin, Stéphane Natkin
Weighted Synchronic Distances

Weighted synchronic distances have been introduced by Kurt Lautenbach in [2] for pairs of single events and for nets which are covered by exactly one reproduction component. We will generalize this notion to pairs of sets of events and to arbitrary cyclic condition/ event-systems.Weighted synchronic distances yield a metric space and meet furthermore some other numerical properties which are already known for unweighted synchronic distances [4]. We will show how to compute weighted synchronic distances and how to find weights which yield finite distances. This will be achieved by help of linear algebra.

U. Goltz, W. Reisig
A simple and Fast Algorithm to Obtain all Invariants of a Generalised Petri Net

After a linear algebraic characterization of the minimal support invariant concept, it is proposed a very efficient algorithm to calculate all the minimal support invariants of Generalised and Capacity Petri Nets.Finally,it is presented a graphycal interpretation of the algorithm execution process. It may be considered as a reduction rule that non preserves liveness.

J. Martínez, M. Silva
Constructive Proofs as Programs Executable by PrT Nets

General net theory [l] is introduced in order to handle situations involving non sequential processes (concurrency, parallelism, synchronization, and so on). Such situations can he devised if one tries to interpret constructive logical proofs as algorithms solving tasks specified by first-order formulas.

P. Miglioli, U. Moscato, M. Ornaghi
Correctness Proof for the Alternating Bit Protocol by Assertion Systems

The net representation of the alternating bit protocol given in newsletter 7 of the special interest group on Petri nets and related system models (Feb. 1981) is proved “correct” by using assertion systems.

Horst Müller
A Fair Competition Between Two or More Partners

N partners compete for a single resource that can be used by only one of them at a time. When released, the resource becomes available and will again be contended by the partners.

Astasia Carla Pagnoni
Metadaten
Titel
Application and Theory of Petri Nets
herausgegeben von
Claude Girault
Wolfgang Reisig
Copyright-Jahr
1982
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-68353-4
Print ISBN
978-3-540-11189-4
DOI
https://doi.org/10.1007/978-3-642-68353-4