Home | Up | Questions? |
This annotated bibliography brings to a close our presentation on the theory of Petri nets. As can be expected, we have not been able to present all of the work which has been done on Petri nets. More complete information is available in the scientific literature.
Unfortunately much of the research on Petri nets is available only as technical reports from the institutions where the research has been done; only a fraction appears in journals with wide circulation. Even the Petri net literature which has appeared in journals is scattered: Thus, there may be some problems in finding these works.
There are three main sources for literature on Petri nets: journals, reports, and conferences. Theoretical journals in computer science are the most readily available source. These journals would include Theoretical Computer Science, Journal of Computer and System Sciences, Information and Control, and Journal of the ACM.
The papers published in these journals are often available first as technical reports. These reports are generally available only from the author(s) or the issuing agency, typically a department of a university. Many departments issue Ph.D. dissertations as technical reports; alternatively these are available from University Microfilms in Ann Arbor, Michigan.
A major source of Petri net research has been the work performed at the Massachusetts Institute of Technology (M.I.T.). Originally these reports were issued by Project MAC; Project MAC has since changed its name to the Laboratory for Computer Science. Another important source of research reports is the Institut fur Informationssystemforschung of the Gesellschaft fur Mathematik und Datenverarbeitung in Bonn, West Germany.
A final source of research results in Petri net theory is the proceedings of conferences. Work on Petri nets is very scattered among conferences with few predictable forums for presenting new results. The Annual Symposium on Switching and Automata Theory (now called the Symposium on the Foundations of Computer Science) has often had some presentations related to Petri nets. Petri net research is also reported at the Symposium on Mathematical Foundations of Computer Science, the Allerton Conference on Communication, Control and Computing, the Design Automation Conference, the ACM Symposium on Theory of Computing, the Sagamore Computer Conference on Parallel Processing, the Conference on Information Sciences and Systems, the International Computing Symposium, and the IFIP Congress. The proceedings of these conferences are often available from ACM, IEEE, North-Holland Publishing Company, or Springer-Verlag.
This bibliography is mainly the result of my extensive research on Petri nets. An extensive search was made of journals and conference proceedings for papers on Petri nets. In addition, any reference listed by a new paper which was about Petri nets was also searched for until no new references were produced. I have read most of these references, but there are some which I have not been able to find (their existence is known only by being referenced in some paper which I have found) and others which I cannot read because they are not in English. I hope that this bibliography will be of use to you in any further research you may do on Petri nets.
An extended Petri net model is defined which allows inhibitor arcs. It is shown that this extended model is equivalent to a Turing machine model of computation. Since a Turing machine can model any algorithmic scheme for coordinating processes, it is called complete. The extended Petri net model is also complete.
Eighteen models of parallel computation as well as nine variants of Petri nets are analyzed and compared to create a lattice of models, similar to the lattice of Chapter 8. These results are compatible with the results of [Peterson and Bredt 1974] but independently derived and more ambitious.
An excellent, although short, paper on how Petri nets can be used to model systems with concurrency. A reasonable alternative to Chapter 3 of this text. A variety of applications are presented including computer software, hardware, asynchronous circuits, design languages, and some novel applications.
The 360/91 computer was designed to utilize a great deal of parallelism to provide high performance. The control unit should therefore be able to be modeled by a Petri net if Petri nets are good for modeling parallel hardware. This paper describes the basic operation of the control unit of the 360/91.
A survey of some of the theory which has been developed for parallel computation. First the problem of representing parallelism in a program, or automatically detecting hidden parallelism if the programming language does not allow explicit representation of parallelism, is considered. Then several models of parallel computation, including Petri nets, UCLA graphs, and parallel program schemata, are presented. Finally some techniques for attempting to predict the performance of a multiprocessor system are described. An appendix describes different types of multiprocessor hardware systems.
A report on early work in modeling a compiler with an extended Petri net is presented here. Only modeling is of concern. The Petri net model is extended by the addition of disjunctive (OR) logic, switches, and token absorbers. Then this model is used to describe the lexical analysis phase of a compiler. This work appears to have led to the results in [Baer and Ellis 1977].
This is a continuation of the work reported in [Baer 1973b]. An XPL compiler was modeled as a Petri net. This provided insight into the structure of the compiler which allowed it to be restructured as three separate stages, suitable for a three processor pipelined compiler with a resulting speed up by a factor of two. A practical application of Petri nets.
A short note describing the basic idea of associating a language with a Petri net and using this language to describe the behavior of the Petri net.
The title of this thesis is somewhat misleading. Some equivalence problems are mentioned, but the major emphasis and importance concern Baker's early thoughts on Petri net languages. This is one of the first works to consider Petri nets in the context of formal language theory. Baker works with a prefix language of a Petri net and derives a canonical form for prefix languages of marked graphs.
Rabin was misquoted in [Karp and Miller 1968] as having proved that the equality problem for reachability sets is undecidable when in fact he showed only that the inclusion problem was undecidable. This proof was never published, but in 1972 a new proof was presented at a talk at M.I.T.. This proof is presented here. It uses Hilbert's tenth problem to show that the inclusion problem is undecidable. Hilbert's tenth problem is reduced to nondeterministic register machines, which are in turn equivalent to Petri nets. This proof is the basis of the proof given in Chapter 5 for the undecidability of the equality and subset problems for Petri net reachability sets.
An early paper on automatic detection of parallelism in a program, this paper contains the definition of Bernstein's conditions: Two activities can be executed concurrently if the output of each activity is neither an input nor an output of the other activity.
This report mentions Petri nets as a model of parallel computation.
Comments on the close relation of commutative semigroups to vector addition systems and Petri nets.
One of a series of reports and dissertations developing the UCLA graph model of computation.
This article is a good introduction to pipelined computer architectures which can be modeled by Petri nets, as in Chapter 3.
A deadlock is a situation where two activities are each waiting for each other to proceed before they proceed themselves. Liveness is (in some sense) the opposite of deadlock. Commoner examines various degrees of deadlock, or liveness, and obtains a sufficient condition for liveness.
Marked graphs are a subclass of Petri nets which exhibit concurrency but not conflict. This paper is the basic presentation of marked graphs and results. Algorithms are given to solve the safeness, liveness, and reachability problems among other things.
Pages 44 to 47 describe a Presburger arithmetic algorithm which is used to prove simple theorems about algebraic formulas.
Some of the presentation in Chapter 3 on the use of Petri nets to model computer software is based on this draft. The presentation is somewhat mechanical, but the basic contents present and analyze many of the classical problems in process synchronization.
An attempt is made to characterize Petri net systems. First an algebraic characterization, based on the matrix representation of Petri nets is investigated; then a language approach is used to try to characterize Petri nets by their sequences of transition firings. Petri nets are shown to be equivalent to commutative phrase structure grammars, grammars in which the ordering of symbols is irrelevant. The report is a well written and understandable treatment of basic Petri net properties.
It is shown that the reachability problem for conflict-free Petri nets is decidable, and a brief description of the algorithm for finding a firing sequence leading from one marking to the other (if the marking is reachable) is given.
A machine language program for the computer at the Institute for Advanced Study is described. The program will determine the validity of a formula in Presburger arithmetic (subject to a limit of 96 symbols). The value of this paper is its explanation of Presburger's algorithm before the program.
A classic work on computability theory.
Davis reports the complete proof by Matijasevic of the undecidability of Hilbert's tenth problem.
A popular and very readable explanation of the proof that Hilbert's tenth problem is undecidable.
Examples of the use of Petri nets for the description of the control mechanisms of complex computers are given. The eventual goal would be to develop automatic mechanisms for implementing the Petri net as a digital system.
The Woods Hole Conference brought together 27 researchers on parallel computation for a few days and eventually resulted in this proceedings. Papers dealing with Petri nets include [Holt and Commoner 1970; Dennis 1970a; Seitz 1970; Patil 1970b] and there is an excellent bibliography.
Petri nets are used as a model of parallel computation to illustrate the problems of determinacy and communication between processes.
This classic paper first introduced the P and V operations on semaphores.
General net theory has been under development by Petri and others since the early work which lead to the Petri net model. These two reports, ``Net Topology I'' and ``Net Topology II,'' are concerned with the development of the algebraic (mathematical) properties of general net theory. Many definitions, theorems, and proofs; no intuition.
Mentioned in [Holt and Commoner 1970] as being a thorough study of marked graphs.
Uses Petri nets to represent theorems, axioms, lemmas, and their relationships.
A representation of first-order predicate calculus as a Petri net is given.
A subclass of Petri nets is defined which can be hierarchically combined to create larger nets whose liveness is guaranteed.
A finite state machine model of parallel computation, using shared memory for communication.
A very mathematical treatment of a part of formal language theory. The work on bounded languages, Parikh's theorem and semilinear sets relates to work in Petri net languages.
The connection is made among context-free languages, semilinearity, and Presburger arithmetic.
One of a series of reports and dissertations developing the UCLA graph model of computation. This dissertation defines the property of termination and develops an algorithm to decide proper termination. An appendix shows that Petri nets and UCLA graphs are almost equivalent, but the constructions mistakenly associate the places of a Petri net with the nodes of the UCLA graph, rather than the correct association with the arcs of the graph, so the results are misleading.
The property of proper termination of a Petri net is defined and discussed. A properly terminating Petri net can be substituted for a transition in another net without creating deadlocks.
This thesis introduces free-choice Petri nets and develops their properties. Necessary and sufficient conditions for liveness and safeness are the main results. There is also some work on decomposing free-choice nets into simpler subnets.
A Petri net version of the undecidability of the subset problem for reachability sets is given. Rabin's original proof, as reported in [Baker 1973b], was given for vector addition systems. This proof is also given in [Hack 1974a] and [Hack 1975c] and is given here in Chapter 5.
Three major results are collected into this report: (1) the equivalence of generalized Petri nets to restricted Petri nets (no self-loops and multiplicity of either zero or one), (2) the Petri net version of the undecidability of the subset problem for reachability sets (also [Hack 1973c]), and (3) the equivalence of the liveness and reachability problems (also [Hack 1974c]).
It is shown that the reachability problem and the liveness problems are mutually reducible.
It is shown that the subset problem for reachability sets is reducible to the equality problem. Thus since the subset problem is undecidable (see [Baker 1973b], [Hack 1973c], or [Hack 1974a]), the equality problem is undecidable also. This proof is given here in Chapter 5.
Following Baker's suggestion [Baker 1972], Hack carefully investigates Petri net languages. Two basic language classes are distinguished: the prefix languages of all sequences which lead to a reachable marking and the languages of sequences leading to a defined final marking. In addition, Hack considers languages which result from allowing or not allowing transitions to be labeled with , the empty string. For each of these four classes, simple closure properties and characterizations are obtained. In addition these languages are related to other classes of languages, including regular languages. It is shown that membership, emptiness, and finiteness are decidable for some languages and equivalent to the reachability problem for other languages (which now means they are decidable for these languages too). An excellent piece of research into a new subject.
This dissertation brings together much of Hack's work into one report. The report is an excellent treatment of Petri nets covering both basic definitions and properties and advanced research. Each topic is carefully introduced and developed. Major chapters include the following: Decidability of Boundedness and Coverability (using the reachability tree); Reachability Problems; Liveness and Persistence; Undecidability of Subset and Equality Problems for Petri net Reachability sets (as first presented in [Hack 1973c; Hack 1975a]), Petri net languages (from [Hack 1975b]). The dissertation concludes with some open questions and conjectures.
A well-organized summary of the results of the Information System Theory Project. Tutorial presentation of occurrence systems with examples and excellent discussion of concurrency and conflict in terms of occurrence systems and (thus) safe Petri nets.
Systemics is the name of Holt's work to develop a science of information and systems. This paper is an excellent presentation of the fundamentals of this work and the beginnings of Petri net theory. Petri nets are defined and illustrated. Marked graphs and state machines are defined and discussed at length.This paper relaxes the constraint of safeness in one example and thus plants the seed of modern definitions. Very readable and interesting.
A massive work, this report presents the results of the Information System Theory Project which was concerned with finding a proper descriptive means for modeling, evaluating, and implementing systems. Petri nets were a major portion of this work and are presented here in detail. The Petri net concept itself is still a safe net. This leads to a fair amount of work on occurrence graphs and occurrence systems, an approach to representation and analysis of firing sequences which is only applicable to safe nets. After some presentation in [Holt and Commoner 1970], occurrence systems have been dropped.Most works on Petri nets refer to this report, although it is now of mainly historical interest. Section V was revised as [Shapiro and Saint 1970].
The reachability problem for vector addition systems with up to five dimensions (Petri nets with up to five places) is studied. The reachability sets are shown to be effectively semilinear, which provides an algorithm for their solution. Also containment and equivalence, not generally decidable, are decidable for these systems. Unfortunately this approach will not work for more than five places and is, therefore, of limited practical use.
An excellent text, this book is a classic in the field. It is a concise, yet understandable, treatment of formal language theory (regular, context-free, context-sensitive, and type-0 languages) and automata theory (finite state pushdown, linear bounded, and Turing machines). Time and space complexity issues and decidability questions are well presented. Must reading and a constant reference source for work in any of these areas.
Petri nets, UCLA graphs, and vector addition systems are considered as models of the interconnections of hardware modules. Analysis using the reachability tree then shows some problems with the modules.
This is the final report on the investigations at the IBM Vienna Laboratories on marked graphs. It brings together into a consistent development the work of Izbicki, Henhapl, Hansal, and Schwab. The development is very formal, overloaded with arcane notation and theorems, and concerns marked graphs. The results are minimal.
An introduction to Petri nets, among other subjects.
Complexity theory is applied to Petri nets in this paper. Time and space bounds are given for several Petri net problems, including reachability, liveness, and safeness. It is shown that persistence is reducible to reachability. The complexity results are given both for Petri nets and for state machines, marked graphs, and free-choice Petri nets.
The computation graph model of computation is defined and its properties investigated. This model influenced many of the later models, such as the parallel program schemata of [Karp and Miller 1968].
Much of the early work on modeling parallelism in computer systems was based on the model of a computer system with memory and multiple processors. Processors executed programs which were modeled more or less as flowcharts. This paper by Karp and Miller is one of the high points of this approach. It presents the parallel program schemata model and then proceeds to determine various properties of the model, such as algorithms for equivalence, determinacy, and boundedness. Of particular interest to Petri nets is Section V, which introduces vector addition systems and the reachability tree to decide boundedness and coverability. A classic paper.
An important paper which is commonly referenced. Keller defines a ``transition system'' as a general model for parallel computation and then narrows this to vector replacement systems specifically. Vector replacement systems are the natural generalization of vector addition systems and an equivalent formalization to Petri nets. The liveness problem is the major property investigated.
Keller is interested here in defining the modeling power (systems which can be modeled) and decision power (questions which are decidable) of Petri nets. The modeling power is characterized by additive monotone systems. Decision properties discussed here center on the reachability tree for showing correctness.
The model used here is more powerful than Petri nets but has been developed from Keller's work with vector replacement systems and Petri nets.
This was the first paper to define a synchronization problem which Petri nets could not model. Since Petri nets can model P and V operations on semaphores, these were also shown to be incomplete. The problem simply encoded the state by one, two, or three tokens in a place. Since Petri nets are permissive, it is not possible to prevent transitions meant for one or two tokens from firing when there are three tokens.
Conflict-free Petri nets allow shared input places only if they are on self-loops; persistent Petri nets cannot disable a transition except by firing it. The reachability sets of both types of Petri nets are characterized as semilinear. Complexity and decidability are the main subjects of this work.
A very informal transcript of the development of the relationship between path expressions and Petri nets. This led to the writing of [Lauer and Campbell 1974].
A constructive approach is taken to showing how path expressions can be represented by Petri nets. Path expressions are a means of describing the sequences of allowable interactions between concurrent processes.
A review of the state of knowledge about liveness and deadlock in Petri nets, this paper brings together most of the results in one place.
Systems of concurrent processes are more difficult to analyze and prove correct than sequential programs. Petri nets can be used to model such a system and prove properties of the modeled system. This paper treats semaphores, bounded buffers, and the five philosophers to rederive in Petri net terms results that have been developed separately.
Termination properties mean deadlock and liveness properties. Since the problem for general Petri nets is still open, Lien investigates the problem for subclasses which are conflict-free or concurrent-free. Some graph theory concepts such as strongly connected are used as are Petri net concepts such as conservation. Lots of formal mathematics.
A tutorial paper showing the basic concepts of Petri nets and the related transition system model. Applications of the modeling techniques to transportation systems, genetic systems, and computations are given.
The results of this paper were first presented at the Conference on Petri Nets and Related Methods in July 1975. This paper is the most commonly cited result in complexity for Petri nets. Five lemmas are used to prove that the reachability problem for Petri nets and equivalent models such as vector addition systems require at least space. The result is based on a construction showing that it is possible to construct a counter which can effectively count from 0 to with a number of transitions proportional to . The operations of adding, subtracting, and testing for zero are possible on the counter. (It is the test for zero that is hard.) The proofs are constructive in a parallel program language which is easily shown to be equivalent to Petri nets. A rather tricky proof that requires several readings.
It is shown that computation graphs can be simulated by sets of processes using P and V operations.
Lipton, Snyder and Zalcstein compare the major models of parallel computation, similar to the work in [Agerwala 1974b] and [Peterson and Bredt 1974], but their results are substantially different. The differences are caused by the definition of equivalence and containment. Their research is more formal and harder to follow than [Agerwala 1974b] or [Peterson and Bredt 1974] but of equal validity and interest.
It is shown that Petri net languages which allow transitions are not closed under complement.
A curious presentation of Petri nets for the legal profession. Legal systems are social systems including lawyers, judges, plaintiffs, defendants, clerks, and so on. The interactions among these participants are described by such volumes as the Federal Rules of Civil Procedure. This presentation shows that at least some of these rules can be represented by an interpreted Petri net. It is suggested that modeling the legal system as a Petri net could lead to better understanding through analysis and then to a better legal system.
This dissertation is a strange combination of many topics. Petri nets are used to model systems. Then faults are introduced into the model by considering the behavior of the system when tokens are added or removed with no transition firing. ``Good'' Petri nets will eventually get back into an acceptable marking, while ``bad'' nets will either deadlock or go off into new markings where they shouldn't be. This work was strongly influenced by the work on the UCLA model and its token machine concepts.Another part of the dissertation presents the timed Petri net model in which transitions must wait a certain time after they are enabled before they can fire and then must fire within a certain amount of time. These nets can represent more systems since they are equivalent to Turing machines. However, Merlin's work is basically limited to finite systems, so no problems arise.
Time Petri nets are used to model communication protocols. An example is presented of the development and modeling of a protocol by a time Petri net followed by the validation of the protocol and an indication of how this protocol could then be implemented directly from the Petri net by a table-driven microprogrammed Petri net interpreter. The time Petri net model is, of course, derived from Merlin's dissertation [Merlin 1974].
Petri nets, computation graphs, parallel program schemata, and marked graphs are compared.
Reducibility between Petri nets, computation graphs, semaphore systems, vector addition systems, and vector replacement systems are considered.
A textbook, somewhat dated by its treatment of McCullouch-Pitts nets, which is still a fine treatment of computability theory. Of most interest to us here is Chapter 11 on register machines, but the chapters on Turing machines are related also.
An introduction to Petri nets for those in control theory, this paper concentrates on presenting and analyzing Petri nets as discrete time systems. Controllability and reachability are examined in terms of the matrix representation of a Petri net and maximal matchings. This is a first step toward an interchange between Petri net theory and optimal control theory.
A very nice introduction to Petri nets and marked graphs, stressing the circuit theory viewpoint. The matrix approach to representing Petri nets is used throughout and such concepts as controllability, in the systems theoretic sense, are considered. The presentation is tutorial and is a fine example of how Petri nets can be widely used in other fields of study. The informal treatment here is an interesting contrast from [Murata 1977b].
A matrix representation of Petri nets can lead to some useful analysis techniques. This approach is developed in this report, mainly for marked graphs but to some degree for Petri nets. This is the most complete investigation of Petri nets and matrix equations.
Uses the incidence matrix of an E-net to study the properties of liveness, deadlock, and reachability.
The reachability problem for vector addition systems is defined as a research problem. It is shown equivalent to the zero-reachability problem and the reachable-from-zero problems.
The title is rather misleading since not the CDC 6400 but the SCOPE 3.2 operating system is modeled. Also the model used is not strictly Petri nets but seems to have been extended to include inclusive- and exclusive-OR logic. It is not obvious whether this is necessary, but it is not relevant; this paper has mainly served as an example to show that Petri nets can model real systems (even if the details don't quite agree). This was also the start of the work which led to E-nets (see [Nutt 1972a] and [Noe and Nutt 1973]).
E-nets (evaluation nets) are an extended, interpreted model for parallel computation (derived from Petri nets) for performance measurement, evaluation, and simulation. E-nets represent one approach toward adding timing information to a Petri net.
The complete work on E-nets, an extension of Petri nets for performance modeling and evaluation.
The mapping from a string to a vector whose th component is the number of occurrences in the string of the th symbol is defined. It is shown that this mapping (the Parikh mapping) applied to a context-free language leads to a semilinear set.
A solution to the cigarette smokers' problem posed by Patil [1971] is presented. The solution uses an array of semaphores and a global variable, which were implicitly not allowed by Patil.
One of the early works on Petri nets, this dissertation touches a lot of bases. It has a reasonable introduction to the problems of controlling concurrent processes and to Petri nets. Then it moves on to an extended model, called coordination nets, and their properties. In particular, Patil is concerned with how his coordination nets can be implemented in hardware. This shows up in his later work also.
A system is determinate if it produces the same output for the same inputs. This will not always be the case if concurrent operations may happen in arbitrary order, and this order affects the output. Determinacy was a big problem when concurrent systems were first being defined, but at least the term is no longer broadly used. In this paper, Patil was concerned with how to connect smaller, determinate systems together to form a larger determinate system.
This short note defines the cigarette smokers' problem and shows that it cannot be solved by using semaphores. Petri nets are used to model the problem. It is shown that any solution must result in a form of Petri net which does not correspond to those resulting from P and V operations. This research led to [Kosaraju 1973] and [Agerwala and Flynn 1973], but also see the note by Parnas [1972].
Gate-level circuits for implementing Petri nets in hardware are given. These circuits differ from those in [Patil 1970a] by their detail (down to gate level) and by the assumption of a known bound on transmission delays.
A short presentation is given of the work on describing digital systems by Petri nets and then implementing them as speed-independent (asynchronous) circuits.
Two major results of this dissertation were the comparison of models later summarized in [Peterson and Bredt 1974] and the Petri net languages theory later printed in [Peterson 1976].
Chapter 4 of [Peterson 1973], revised, is published. A specific class of Petri net languages, those languages defined by executions from an initial state to a final state, are defined and investigated. Closure properties and the place of these languages in the hierarchy of languages (regular, context-free, context-sensitive, type-0) are the main points considered.
This is the first widely circulated survey and tutorial on Petri nets. It touches briefly on modeling with Petri nets, basic definitions, analysis problems and techniques, Petri net languages, and related models of computation. A good introduction which should be readable by any technically minded college student or graduate.
The control structures of several models of parallel computation are described and compared. The models include finite state machines, Petri nets, UCLA graphs, message systems, computation graphs, parallel program schemata, marked graphs, and coordination nets. Also see the related papers [Agerwala 1974b], [Lipton et al. 1974], and [Miller 1973].
This dissertation is the starting point for Petri net theory. Petri starts by discussing finite automata and shows (by reference to work by Davis, Turing, and others) that regular automata cannot recognize context-free or context-sensitive grammars. Petri then claims that if these automata were not finite but unbounded, then signal delay times are also unbounded and so synchronization problems result.Petri then proceeds to construct a net for simulating the tape of a Turing machine. This net is completely asynchronous and constructed of identical cells which pass information to their neighbors (left or right) as needed. Since the tape is infinite, an infinite number of cells are needed. However, the importance of this work is its stress on the asynchronous nature of the interactions.
In modern terms, all of the nets in Petri's dissertation are safe by definition. Petri's dissertation is of only historical interest today.
The development of a general net theory, related to general systems theory and topology.
Further development of net theory.
A compilation of most of the known works on Petri nets.
This paper uses the UCLA graph model rather than Petri nets (but the two are equivalent) to model communications protocols. Similar in intent to [Merlin 1975].
The basic algorithm for deciding the validity of a statement which uses only addition over integer numbers with quantifiers and logical connectives (Presburger arithmetic) is given.
New algorithms for the covering and boundedness problems are given. These results are presented for vector addition systems but are, of course, equally applicable to Petri nets. The algorithms use space and so are close to optimal. Lipton's lower bound is . The main emphasis of this paper is establishing complexity results.
This dissertation is concerned with the analysis of a Petri net model to determine its performance. The Petri net model is extended to associate a time with each transition. Analysis of some subclasses of these timed Petri nets then leads to calculation of throughput rates for these systems.
Uses reducibility to Petri net reachability problem to show difficulty of analyzing programs of a distributed environment.
Riddle's Ph.D. dissertation defined a model for parallel computation which assumes that a system is composed of independent asynchronously operating sequential processes. Communication between processes is by way of messages. The objective is to develop a method for analysis of computer systems. In Riddle's model, each process is described by a pseudoprogram. These are used to produce message transfer expressions (which are languages), and then the message transfer expressions are used for analysis. Decision problems were left open, but several examples show the power and usefulness of this approach. Peterson showed that these systems could be converted to Petri nets [Peterson 1973], and Riddle proved the reverse [Riddle 1974], showing the essential equivalence of these two modeling schemes.
The work reported in [Peterson 1973] and [Peterson and Bredt 1974] states that message systems are a proper subset of Petri nets. Riddle shows that if equivalence does not consider false deadlocks, this is incorrect: They are equivalent models. The proof shows how to construct a message system with the same (nondeadlock) behavior as a Petri net. The equivalence of these two models is comforting, since the message systems are much easier to use for modeling systems of parallel processes.
Uses a Petri net to transform sequential programs to parallel programs by modeling the precedence relations which exist in the algorithm rather than the ones introduced by writing the program in a linear programming language.
An extended abstract of this paper surfaced in November 1976. A constructive ``proof'' is given of the decidability of the reachability problem for vector addition systems and Petri nets. Unfortunately, the ``proof'' is in error. From the preface to the Proceedings of the Tenth Symposium: ``... in [Sacerdote and Tenney 1977], a number of difficulties have been pointed out. A new version, simpler and more accurate, is in preparation and will be available shortly from the authors.''
A comprehensive treatment of most of modern formal language theory, this reference text is particularly useful for its presentation of matrix grammars and Lindenmayer systems; both of these classes of languages have been linked to Petri net languages.
This report unifies the previous work of [Commoner 1972] and [Lautenbach 1975] with respect to the liveness problem.
This paper follows an example through to present a tentative methodology for constructing an asynchronous machine from a Petri net.
Petri nets are applied to compiling FORTRAN programs for a CDC 6600 computer. The FORTRAN program is converted into a Petri net showing precedence constraints between operations. This net is merged with a Petri net representing the CDC 6600 CPU. Timing information is associated with the transitions, and an exhaustive search is used to determine the sequence of operations and assignment of registers which minimizes execution time.This paper is a revision of Section V of [Holt et al. 1968].
This paper develops the register machine model and shows its equivalence to Turing machines. The register machine model of computation is easy to model with an extended Petri net model, showing the equivalence of the extended Petri net model to Turing machines.
The Petri net as a model of computation is investigated. Comparisons between the Petri net model and other models (such as in [Agerwala 1974b] or [Peterson and Bredt 1974]) are made. Also a program for simulating a Petri net is presented along with lots of output from this program tracing the execution of a Petri net.
An introduction to the use of Petri nets to model some simple operating system problems (mutual exclusion, producer/consumer) with some thoughts about how Petri nets could be used to aid the design, evaluation and implementation of an operating system.
The reachability problem for dimensions of one, two, or three is shown to be decidable.
Considers an abstract model of nets with axioms where instances of these axioms create models of the theory; concerned with the fundamental concepts of net theory, as in [Petri 1973].
Home | Comments? |