Availability of Some Early English-language Reports on Petri Nets

James L. Peterson

Department of Computer Sciences
The University of Texas at Austin
Austin, Texas 78712

February 1980

This paper has been published. It should be cited as

James L. Peterson, ``Availability of Some Early English Language Reports On Petri Nets'', Newsletter of the Special Interest Group on Petri Nets and Related System Models, Number 4, (February 1980), pages 21-27.

Many people have indicated that some of the early classic papers on Petri nets are difficult to obtain. In the United States much research is supported by grants and contracts from the U.S. government and so copies of these research reports are filed with the government. The National Technical Information Service (Department of Commerce) provides access to most of these reports. To get a copy of a particular report, you must know its accession number. Accession numbers are determined by searching the semi-monthly Government Reports Announcements which print the accession number, source, and abstract. I have compiled the following list of Petri net reports which are on file with NTIS. The accession number is the AD-xxx xxx or PB-xxx xxx number.

To get a copy of one of these reports, write first to obtain a price quote (giving the accession number of the report or reports which you want) and a copy of Folder PR-360-4. Copies are available in paper (generally $10.00 to $25.00) and microfiche (around $3.50 to $5.00). Prices vary according to the number of pages. The address to write is:

		National Technical Information Service
		5285 Port Royal Road
		Springfield, Virginia  22161

A source of any research which is published as a Ph.D. dissertation is University Microfilms. Almost all Ph.D. dissertations in the U.S. and Canada are available from them. Prices are similar to those of NTIS for paper copy, but seem to be higher for microfiche. They have two addresses:

    University Microfilms	  University Microfilms International
    P. O. Box 1764		  Tylers Green
    Ann Arbor, Michigan 48106	  High Wycombe
    U.S.A.			  Buckinghamshire, England HP10 8HR

A final alternative: If there was sufficient interest, we might be able to interest a publisher (like Springer-Verlag) in publishing a collection of important (historical) Petri net papers. The major question of course is: What are the major Petri net papers? One is obvious: Petri's thesis. What are the others? If you would like to send me your suggestions, mail them to:

		James L. Peterson
		Department of Computer Sciences
		University of Texas
		Austin, Texas  78712

AD-630 125

Carl Adam Petri, COMMUNICATION WITH AUTOMATA, Final report, Volume 1, Supplement 1, RADC TR-65-377-vol-1-suppl-1, Applied Data Research, Princeton, NJ, Contract AF 30(602)-3324, (January 1966), 98 pages; Translation by Clifford F. Greene, Jr. of Kommunikation mit Automaten, Bonn, 1962.

The theory of automata is shown not capable of representing the actual physical flow of information in the solution of a recursive problem. The argument proceeds as follows:
  1. The following postulates are assumed: (a) there exists an upper bound on the speed of signals; (b) there exists an upper bound on the density with which information can be stored.

  2. Automata of fixed, finite size can recognize, at best, only iteratively defined classes of input sequences.

  3. Recursively defined classes of input sequences that cannot be defined iteratively can be recognized only by automata of unbounded size.

  4. In order for an automaton to solve a (soluble) recursive problem, the possiblity must be granted that it can be extended unboundedly in whatever way might be required.

  5. Automata (as actual hardware) formulated in accordance with automata theory will, after a finite number of extensions, conflict with at least one of the postulates.
Suitable conceptual structures for an exact theory of communication are then discussed, and a theory of communication proposed.

AD-676 972

Anatol W. Holt, et al., INFORMATION SYSTEM THEORY PROJECT, Final report, RADC-TR-68-305, Applied Data Research, Princeton, NJ, Contract AF 30(602)-4211, (September 1968), 359 pages.

Project ISTP has been engaged in basic research aimed at developing theory and technique for analysis and description of data structures. Three principal objectives were defined at the outset:
  1. Description of data structures with precision and conciseness for communication between designers, implementers, and users;

  2. Description of data structures leading to implementation insights;

  3. Description of data structures leading to evaluations of the form: Given a particular computing system and a given class of storage and retrieval problems, how suitable is a described structure as a means of accomplishing problem solutions on the proposed equipment.
This report gives the main results to date of the project.

AD-704 796

Anatol W. Holt and Frederic Commoner, RESEARCH IN MACHINE-INDEPENDENT SOFTWARE PROGRAMMING: TASK AREA II. EVENTS AND CONDITIONS: AN APPROACH TO THE DESCRIPTION AND ANALYSIS OF DYNAMIC SYSTEMS, Semi-annual technical report number 3, Massachusetts Computer Associates, Wakefield, MA, Contract DAHC04-68-C-0043, ARPA Order 1228, (April 1970), 197 pages.

The document reports studies on marked graphs and state transition diagrams, both of which are special cases of occurrence systems. It is hoped that the developing ability to analyze these two classes will give the tools with which to attack the analysis of systems which are Petri-net describable. Marked graphs and state transition diagrams isolate two aspects of system description from one another: the aspect which has to do with flow, and the aspect which has to do with function. In the area of marked graphs, effort was divided into two parts: semantics and mathematics. In the area of state transition analysis, a new technical concept of information was developed which makes it possible to measure information quantities that flow in and out of a state machine, as well as identify the information content which flows in and out at different state transitions.

AD-711 763

Suhas Shrikrishna Patil, COORDINATION OF ASYNCHRONOUS EVENTS, Report number MAC TR-72, Massachusetts Institute of Technology, Cambridge, MA, Contract NONR-4102(01), (June 1970), 235 pages.

The way activity in a system proceeds is that events occur as a result of some conditions and lead to some new conditions which make other events possible. Often it is necessary to coordinate such events to ensure proper behavior. Coordination nets for representing such coordinations and physically realizable structures for enforcing such coordinations are presented. These structures are modular and can be mechanically derived from the coordination nets. Coordinations involved in concurrent management of resources are also discussed.

AD-740 320

Michel Hack, ANALYSIS OF PRODUCTION SCHEMATA BY PETRI NETS, Master's thesis, Report number MAC TR-94, Project MAC, Massachusetts Institute of Technology, Cambridge, MA, Contract N00014-70-A-0362-0001, ARPA Order 433, (February 1972), 114 pages.

Petri nets provide a powerful graphical tool for representing and analyzing complex concurrent systems. Properties such as hang-up freeness, determinacy, conflict, concurrency and dependency, can be represented and studied. The precise relationship between structural and behavioral properties, and between local and global properties is not well understood for the most general class of Petri nets. This thesis presents such results for a restricted class of Petri nets called Free Choice Petri Nets, and for a corresponding class of systems called Production Schemata. Results on structural constraints guaranteeing global operation, and decompositions of complex systems into meaningful parts, are also presented.

PB-231 916

Michel Hack, DECISION PROBLEMS FOR PETRI NETS AND VECTOR ADDITION SYSTEMS, CSG-Memo-95, Computation Structures Group, Massachusetts Institute of Technology, Cambridge, MA, Grant NSF-GJ-34671, (March 1974), 76 pages.

Four formalisms are mentioned: Vector Addition Systems, Petri nets, Vector Replacement Systems, and Generalized Petri Nets. The graphical appeal of Petri Net methods permits a better grasp for intuitive arguments, which can help enormously to find rigorous proofs of various facts. New proofs of the major decidability results obtained for Vector Addition Systems by Karp and Miller, as well as of Rabin's undecidability result are presented. Finally, the author applies these tools to several open questions, and proves the recursive reducibilities between various decidability questions. The author proves the recursive equivalence of the Liveness problem and the Reachability problem.

PB-231 926

James L. Peterson, MODELLING OF PARALLEL SYSTEMS, Technical report number 46, SU-SEL-74-006, STAN-CS-74-410, Stanford Electronics Laboratories, Stanford University, Stanford, CA, Grant NSF-GK-23315, (December 1973), 254 pages.

A schematic model of parallel systems, the p-model, is presented. The p-model is defined in terms of a control structure, called the p-net, and an interpretation. Emphasis is on the control structure rather than the interpretation. Execution rules for the p-net specify a set of reachable states which the p-net may enter. An execution of a p-net generates a sequence of operations called a computation sequence. The set of all possible computation sequences for a p-net is its computation sequence set.

AD-779 257

DEVELOPMENT OF THEORETICAL FOUNDATIONS FOR DESCRIPTION AND ANALYSIS OF DISCRETE INFORMATION SYSTEMS. VOLUME I. SEMANTICS, Final report, Report number CADD-7405-2011-Vol-1, Massachusetts Computer Associates, Wakefield, MA, Sponsored in part by Advanced Research Projects Agency, (May 1974), 66 pages.

  1. Communication mechanics (Parts, Values, Motion and propagation, The motion of parts and values);

  2. Nets, time and space (Cells and boundaries, Full and empty space and time, One-directional motion).

AD-779 891

DEVELOPMENT OF THEORETICAL FOUNDATIONS FOR DESCRIPTION AND ANALYSIS OF DISCRETE INFORMATION SYSTEMS. VOLUME II. MATHEMATICS, Final report, Report number CADD-7405-2011-Vol-2, Massachusetts Computer Associates, Wakefield, MA, Sponsored in part by Advanced Research Projects Agency, (May 1974), 227 pages.

  1. Marked directed graphs;

  2. Integer programming theorems for oriented graphoids;

  3. The path graphoid of a graph and its applications to network theory;

  4. The vertex graphoid of a bipartite graph and a sufficient condition for total unimodularity;

  5. Deadlocks in Petri nets;

  6. A sufficient condition for a matrix to be totally unimodular.

AD-780 804

DEVELOPMENT OF THEORETICAL FOUNDATIONS FOR DESCRIPTION AND ANALYSIS OF DISCRETE INFORMATION SYSTEMS, Semi-annual technical report number 1, CADD-7406-0611, Massachusetts Computer Associates, Wakefield, MA, Sponsored in part by Advanced Research Projects Agency, (June 1974), 78 pages.

The first section considers a further development of ideas pertaining to the interpretation of Petri nets. The second section is an attempt to specify the mathematical foundation for the theory. The purpose of this section is purely to set forth the important structural ideas, not to show how these ideas relate to the semantic content they are designed to support. The third section reports on a new theorem due to Fred Commoner, about marked graphs, which has an important bearing on the development of Communication Mechanics.

AD-A008 385

DEVELOPMENT OF THEORETICAL FOUNDATIONS FOR DESCRIPTION AND ANALYSIS OF DISCRETE INFORMATION SYSTEMS, Semi-annual technical report number 2, CADD-7503-1411, Massachusetts Computer Associates, Wakefield, MA, Sponsored in part by Advanced Research Projects Agency, (March 1975), 210 pages.

  1. Role/activity models and Petri nets;

  2. Role-activity nets in the analysis of a financial information system;

  3. The connection of parts to one another in system contexts;

  4. Definitions pertaining to Petri nets, states and events and behavior;

  5. Calculating logical and probabilistic dependencies in a class of net models;

  6. System modeling with net structures;

  7. On periodic solutions of affine recurrence systems;

  8. Communication mechanics.

AD-A047 864

Anatol W. Holt, RESEARCH ON INFORMATION SYSTEM SPECIFICATION, Final report, CADD-7708-0911, Massachusetts Computer Associates, Wakefield, MA, Contract N00014-76-C-0781, (August 1977), 183 pages.

This document reports the results of the development of methods for system specification and analysis in conjunction with the National Software Works Project currently in progress in our company. This report indicates that the ideas developed and partially tested in this setting are, potentially, of wide utility in the description and analysis of systems where the interest focuses on the relation of communication among a set of agents with interdependent tasks. The is a description of a theoretical framework in which to study the effects of the propagation of information in a system context as a result of analysis of logical dependence relations in the nets. There is a discussion of the relationship between the concepts concurrency and choice, a survey of the use of Petri nets for the representation of organizational relations.