ACM Home Page
Please provide us with feedback. Feedback
Petri Nets
Full text PdfPdf (2.58 MB)
Source ACM Computing Surveys (CSUR) archive
Volume 9 ,  Issue 3  (September 1977) table of contents
Pages: 223 - 252  
Year of Publication: 1977
ISSN:0360-0300
Author
James L. Peterson  Department of Computer Sciences, The University of Texas, Austin, Texas
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 73,   Downloads (12 Months): 558,   Citation Count: 170
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/356698.356702
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
AGERWALA, T. A complete model for representtng the coordination of asynchronous processes, Hopkins Computer Research Report No. 32, Computer Science Program, Johns Hopkins Univ., Baltimore, Md., July 1974, 58 pp.
 
2
AGERWALA, T. An analysis of controlhng agents for asynchronous processes, Hopkins Computer Research Report No. 35, Computer Scmnce Program, Johns Hopkins Univ., Baltimore, Md., Aug. 1974, 85 pp.
3
 
4
ANDERSON, D W ; SPARACIO, F. J.; AND TOMA- SULO, R.M. "The IBM System/360 Model 91: Machine philosophy and instruction handling," IBM J. R. & D. 11, 1 (Jan. 1967), 8-24.
 
5
BAn, J.L. "Modelling for parallel computation: a case study," in Proc. 1973 Sagamore Computer Conf. Parallel Processing, Springer- Verlag, N.Y., 1973.
6
 
7
BAKER, H. G. Petri nets and languages, Computation Structures Group Memo 68, Project MAC, MIT, Cambridge, Mass., May 1972, 6 pp.
 
8
BAKES, H.G. "Equivalence problems of Petri nets," MS Thesis, Dep.t Electrical Eng,-" neering, MIT, Cambridge, Mass., June 1973, 53 pp.
 
9
BAKER, H.G. Rabin's proof of the undecidability of the reachability set inclusion problem of vector addition systems, Computation Structures Group Memo 79, Project MAC, MIT, Cambridge, Mass., July 1973, 18 pp.
 
10
BERNSTEIN, A.J. "Program analysis for parallel processing," IEEE Trans. Electronic Comp. EC-15, (Oct. 1966), 757-762.
 
11
BeRNSTEIN, P.A. Description problems in the modeling of asynchronous computer systems, Tech. Rep. 48, Dept. Computer Science, Univ. Toronto, Toronto, Canada, Jan. 1973.
 
12
CBmz, V. G. "Multiprocessors, semaphores, and a graph model of computation," PhD Thesin, Computer Science Dept., Univ. Calif., Los Angeles, April 1972.
 
13
CHEN, T. C. "Overlap and pipeline processing," in Introduction to computer architecture, H. S. Stone (Ed.), Science Research Associates, Chicago, ill., 1975, pp. 375-431.
 
14
CLARK, W.A. "Macromodular computer systems," in Proc. 1967 Spring Jr. Comp Conf., Thompson Book Co., Washi" "ngton, D.C., 1967, pp. 335-336.
 
15
 
16
COMMO~R, F. G. Deadlocks in Petri nets, CA-7206-2311, Applied Data Research, Wakefield, Mass., June 1972, 50 pp.
 
17
COMMONER, F.; HOLT, A. W.; EVEN, S.; AND PNU~.LI, A. "Marked directed graphs," J. Computer and Systems Science 5, (Oct. 1971), 511-523.
 
18
CRF~PI-REGHIZZI, S.; AND MANDRIOLI, D. "Properties of firing sequences," presented at MIT Conf. Petr~ Nets and Related Methods, MIT, Cambridge, Mass., July 1975.
 
19
CRESPI-REGHIZZI, S.; AND MANDRIOLI, D. Petri nets and commutative grammars, Internal Report No. 74-5, Laboratorio di Calcolatori, Instituto di Elettrotecnica ed Elettromca del Politecnico di Milano, Italy, March 1974.
 
20
CRESPI-REGHIZZI, S.; AND MANDRIOLI, D. "A decidability theorem for a class of vector-addition systems," Information Processing Letters 3, 3 (Jan. 1975), 78-80.
 
21
CEESPI-REGH|ZZI, S.; AND MANDEIOLI, D. "Petri nets and Szilard languages," Information and Control 33, 2 (Feb. 1977), 177-192.
 
22
DEN~IS, J. B. "Modular asynchronous control structures for a high performance processor," in Record of the Project MAC Conf. Concurrent and Parallel Computatwn, ACM, N. Y., 1970, pp. 55-80.
 
23
DzNms, J.B= (Ed.), Record of the project MAC conf. concurrent systems and parallel computation, ACM, N. Y., 1970, 199 pp.
 
24
 
25
DIJ~.STRA, E. W., "Cooperating sequential processes," in Programming languages, F. Genuys (Ed.), Academic Press, N. Y., 1968, pp. 43-112.
 
26
~CHER, P. C.; ME~ZR, A. R.; ANY RosEbnE~, A.L. "Counter machines and counter languages," Mathemaacal Systems Theory 2, 3 (1968), 265-283.
 
27
FURTEX, F. "Modular implementation of Petri nets," MS Thesis, Dept. Electrical Engineering, MIT, Cambridge, Mass., Sept 1971.
 
28
 
29
GENRICH, H. J. Einfache nicht-sequentielle Prozesse (Simple nonsequential processes), Gesellschaft fiir Mathematlk und Datenverarbeitung, Birlinghoven, W. Germany, 1970.
 
30
GENRICH, H. J. The Petr~ net representation of mathematical knowledge, GMD-ISF Internal Report 75-06, Institut fur Informationssystemforschung, Gesellschaft fiir Mathematik und Datenverarbeitung, Birlinghoven, W. Germany, 1975.
 
31
 
32
 
33
HACK, M. A Petri net version of Robin's undecidability proof for vector addition systems, Computation Structures Group Memo 94, Project MAC, MIT, Cambridge, Mass., Dec. 1973, 12pp.
 
34
HACK, M. Decision problems for Petn nets and vector addition systems, Computation Structures Group Memo 95, Project MAC, MIT, Cambridge, Mass., March 1974; also Technical Memo 59, Project MAC, MIT, March, 1975.
 
35
HACK, M. The recursive equwalence of the reachability problem and the liveness problem for Petri nets and vector additmn systems, Computation Structures Group Memo 107, Project MAC, MIT, Cambridge, Mass., Aug. 1974, 9 pp.; also in Proc. 15th Annual Syrup. Switching and Automata, IEEE, N. Y., 1974.
 
36
HACK, M. The equality problem for vector addition systems ~s undecidable, Computation Structures Group Memo 121, Project MAC, MIT, Cambridge, Mass., April 1975, 32 pp.; also in Theoretical Computer Science 2, 1 (June 1976).
 
37
 
38
 
39
HAcz, M.; ~m ~'ETERSON, J. L. "Petri nets and languages," presented at MIT Conf. Petn Nets and Related Methods, MIT, Cambridge, Mass., July 1975.
 
40
HANSAL, A.; AND SCHWAB, G.M. On marked graphs III, Report LN 25.6.038, IBM Vienna Laboratories, Vienna, Austrm, Sept. 1972.
 
41
HENHAPL, W. Firing sequences of marked graphs, Report LN 25.6.023, IBM Vienna Laboratories, Vienna, Austria, June 1972.
 
42
HENHAPL, W. Finn g sequences of marked graphs II, Report LN 25.6.036, IBM Vienna Laboratories, Vienna, Austria, June 1972.
 
43
HOLT, A. W.; SAINT, H ; SHAPIRO, R. M.; ANY WARSHALL, S. Final report of the mformatmn system theory project, Tech. Rep. RADC-TR- 68-305, Rome Air Development Center, Griffiss Air Force Base, N. Y., Sept. 1968.
 
44
HOLT, A. W.; AND COMMONER, F. JF, t;ents and condition, Applied Data Research N.Y., 1970; also in Record Project MAC Conf. Concurrent Systems and Parallel Computatton, (Chapters I, II, IV, and VI) ACM, N.Y., 1970, pp. 3-52.
 
45
HOLT, R. C. "On deadlock m computer systems," PhD Thesis, Dept. Computer Science, Cornell Umv., Ithaca, N Y., Jan. 1971; also TR 71-91, Dept. Computer Science, Cornell Univ.; and TR CSRG-6, Computer Science Research Group, Umv. Toronto, Toronto, Canada, July 1972.
 
46
IZmCKI, H. On marked graphs, Report LR 25.6.023, IBM Vienna Laboratories, Vienna, Austria, Sept. 1971.
 
47
IzBIcKI, H. On marked graphs H, Report LN 25.6.029, IBM Vienna Laboratories, Vienna, Austria, Jan. 1972.
 
48
JACK, L. "Graphical representation for fault tolerant phenomena," presented at Seminar, Dept. Electrical Engineering, Univ. Texas, Austin, Jan. 1976.
 
49
JONES, N. D.; LAm)W~,BER, L. H.; AND LIEN, Y. E. Complexity of some problems in Petri nets, TR-276, Comp. Science Dept., Umv. Wisconsin-Madison, Sept. 1976, 43 pp.; to appear in Theor. Comp. Sci.
 
50
Kxm,, R. M.; AND Mn~LER, R.E. "Properties of a model for parallel computation: determinacy, termination, queueing," SIAM J. Appl. Math. 14, 6 (Nov. 1966) 1390-1411.
 
51
KARP, R. M.; AND MILLER, R. E. 'Tarallel ~ rogram schemata," J. Computer and Systems cience 3, 4 (May 1969), 167-195.
 
52
KAsAm, T.; TOKURA, N.; AND PETERSON, W. W. "Vector addition systems and synchronization problems of concurrent processes," draft manuscript, 1974.
 
53
KELLER, R.M. Vector replacement systems: a formahsm for modelhng asynchronous systems, Tech. Rep. 117, Computer Science Laboratory, Princeton Umv., Princeton, N.J., Dec. 1972; Revised: Jan. 1974, 57 pp.
 
54
KELLER, R. M. Generaltzed Petrt nets as models for system verification, Tech. Rep. 202, Dept. Electrical Engineering, Princeton Univ., Princeton, N.J., Aug. 1975.
55
56
 
57
KOSARA~U, S. R. Limitations of Dijkstra's semaphore primitives and Petri nets, Tech. Rep. 25, Jol~ns Hopkins Univ., Baltimore, Md. May 1973, 5 pp.; also in Operating Systems Review 7, 4 (Oct. 1973), 122-126.
 
58
LANDWEBER, L. H.; Am) ROBERTSON, E. L. Properties of conflict ~_ e and pe:rslstent Petrt nets, Tech. Rep. 264, Computer Sciences Dept., Univ. Wisconsin-Madison, Madison, Wisc., Dec. 1975, 30 ~p.
 
59
LAUER, P. E.; aND t~Am'B~LL, R. H. A de. scription of path expressions by Petri nets, Tech. Rep. 64, Computing Laboratory, Univ. Newcastle Upon Tyne, England, May 1974, 39
 
60
LAUZR, P. E. Path expressions as Petri nets, or Petri nets with fewer tears, MRM 70, Computing Laboratory, Univ. Newcastle Upon Tyne, England, Jan. 1974, 61 pp.
 
61
LAUTENBACH, K.; AND SCHMID, H.A. "Use of Petri nets for proving correctness of concurrent process systems," in Proc. IFIP Congress 74, North-Holland Publ. Co., Amsterdam, The Netherlands, 1974, pp. 187-191.
 
62
LIzN, Y.E. "Termination properties of generalized Petri nets," SIAM J. Computing 5, 2 (June 1976), 251-265.
 
63
LIPTON, R. J.; SNYDBR, L.; ASD ZALC~ZIN, Y. "A comparative study of models of parallel computation," inProc, l@th Annual Syrup. Switching and Automata, IEEE, N.Y., 1974, p} p. 145-155.
 
64
LIPTos, R. "The reachability problem and the boundedness problem for Petri_ nets are exponential-space hard," presented at MIT Conf. Petri Nets and Related Methods, MIT, Cambridge, Mass., July 1975; also TR-62, Dept. Computer Science, Yale Univ., New Haven, Conn., Jan. 1976.
 
65
MELDMAN, J. A.; AND HOLT, A. W. ~Petri nets and legal systems," Jurimetrics J. 12, 2 (Dec. 1971).
 
66
67
 
68
MXLLER, R. E. A comparison of some theoretical models of parallel computation, RC 4230, IBM T.J. Watson Research Center, Yorktown Heights, N.Y.; also IEEE Trans. Comp. C-22, 8 (Aug. 1973), 710-717.
 
69
MURATA, T.; A~ CHURCH, R.W. Analysis of marked graphs and Petri nets by matrix equat/ons, Research Report MDC 1.1.8, Dept. Information Engineering, Univ. illinois, Chicago Circle, Nov. 1975, 25 pp.
 
70
NASH, B. O. "Reachability problems in vector addition systems," American Math. Monthly 80, 3 (March 1973), 292-295.
71
 
72
NoB, J. D.; Am) NuTr, G.J. "Macro E-Nets for representation of parallel systems," IEEE Trans. Comp. C-22, 8 (Aug. 1973), 718-727.
 
73
 
74
PATIL, S. Limttations and eapabdtttes of Dijkstra's semaphore prtmitives for coordina. twn among processes , Computation Structures Group Memo 57, Project MAC, MIT, Cambridge, Mass., Feb. 1971.
 
75
PATIL, S. S. Ctrcutt tmplementatton of Petri nets, Computation Structures Group Memo 73, Project MAC, MIT, Cambridge, Mass., Dec. 1972, 14 pp.
 
76
PATIL, S. S.; AND DENmS, J.B. The descrtptwn and realazatton of dtgttal systems, Computation Structures Group Memo 71, Project MAC, MIT, Cambridge, Mass., Oct. 1972; also in Proc. Stxth AnnuallEEE Computer Soctety Internatl. Conf. Digest of Papers, IEEE, N.Y., 1972.
 
77
PET~RSON, J. L. "Modelhng of parallel systems," PhD Thesis, Dept. Electrical Engineering, Stanford Univ., Stanford, Cahf., Dec. 1973, 241 pp.
 
78
PZTZRSO~, J. L ; Am) BREDT, T. H. "A comparison of models of parallel computatlon," in roc. IFIP Congress 74, North-Holland Publ. Co., Amsterdam, The Netherlands, 1974, pp. 466-470.
 
79
PZTERsoN, J. L. "Computation sequence sets," J. Computer and System Sciences 13, 1 (Aug. 1976) 1-24.
 
80
rEVR1, C. A'. "Kommunlkahon mit Automaten," Schriften des Rheintsch- Westfal-ischen Inst_ttutes ~r Instrumentelle Mathemattk an tier Universtrat Bonn, Heft 2, Bonn, W. Germany 1962; translation: C. F. Greene, Supplement 1 to Tech. Rep. RADC-TR-65-337, Vol. 1, Rome Air Development Center, GrifFins Air Force Base, N.Y., 1965, 89 pp.
 
81
P~ZTR}, C. A. "Concepts of net theory," in Proc. Symp. and Summer School on Mathematical Foundations of Computer Science, High Tatras, Sept. 3-8, 1973, Math. Inst. Slovak Academy of Science, 1973, pp. 137-146.
 
82
P~TRI, C.A. Interpretattons of net theory, Interner Bericht 75-07, Gesellschaft fur Mathematik und Datenverarbeltung, Bonn, W. Germany, July 1975, 34 pp.
 
83
RACteOFF, C. The covering and boundedness ~e roblems for vector addttion systems, Tech. p. 97, Dept. Computer Science, Univ. Toronto, Toronto, Canada, July 1976, 14 pp.
 
84
 
85
 
86
RIVDLE, W.E. The equzvalence of Petrz nets and message transmission models, SRM 97, Umv. Newcastle Upon Tyne, England, Aug. 1974, 11 pp.
 
87
RovmGVZZ, J.E. "A graph model for parallel computation," PhD Thesis, Dept. Electrical Engineering, MIT, Cambridge, Mass., Sept. 1967, 120 pp.
 
88
SACERDOTE, G.; AND TENNEY, R.L. "The decidabllity of the reachability problem for vector addition systems," (submitted for publication), Nov. 1976, 8pp.
 
89
SLUTZ, D. R. "The flow graph schemata model of parallel computation," PhD Thesis, Dept Electrical Engineering, MIT, Cambridge, Mass., Sept. 1968.
 
90
SHAPIRO, R. M.; AND SAZ~T, H. "A new approach to optimlzation of sequencing decisions," Annual Review of Automatlc Programmtng 6, 5, (1970), 257-288.
 
91
 
92
TSlCHR~ZlS, D. Modular system descr~ptlon, Tech. Rep. 33, Dept. Computer Science, Univ. Toronto, Toronto, Canada, Oct. 1971, 20 pp.
93

CITED BY  170