The residue of vector sets with applications to decidability problems in Petri nets. (English) Zbl 0545.68051
Various right-closed vector sets which are important for analyzing, constructing, or controlling Petri nets are studied. The minimal generating set of a right closed vector set (\(K=K+{\mathbb{N}}^ n)\) is finite and called the residue set of K:\(res(K).\) It is shown that for various sets, which are important for analysis of Petri nets (such as CONTINUAL(\^T), UNBOUNDED, or NOTBLOCKED(\^T)) one can effectively compute their respective residue sets. The new method for calculating the residue set not only solves a number of open problems but also gives a method for controlling a Petri net in order to realize its maximal live subbehaviour. This gives a new solution for the bankers problem described by Dijkstra.
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 68N25 | Theory of operating systems |
Keywords:
right-closed vector sets; Petri nets; residue sets; maximal live subbehaviour; bankers problemReferences:
| [1] | Brinch Hansen, P.: Operating System Principles. Englewood Cliffs: Prentice-Hall 1973 · Zbl 0308.68007 |
| [2] | Brams, G.W.: Réseaux de Petri: Théorie et pratique. Paris: Masson 1983 · Zbl 0508.68034 |
| [3] | Burkhard, H.D.: Two Pumping Lemmata for Petri nets. EIK 17, 349-362 (1981) · Zbl 0494.68065 |
| [4] | Byrn, H.W.: Sequential processes, deadlocks and semaphore primitives. Harvard Univ., Techn. Rep. 7-75, Cambridge 1975 |
| [5] | Carstensen, H.: Fairneß bei Petrinetzen mit unendlichem Verhalten. Univ. Hamburg, Fachbereich Informatik, Report B-93/82 (1982) |
| [6] | Conway, J.H.: Regular Algebra and Finite Machines. London: Chapman and Hall 1971 · Zbl 0231.94041 |
| [7] | Carstensen, H., Valk, R.: Infinite behaviour and fairness in Petri nets. Fourth European Workshop on Application and Theory of Petri Nets, Toulouse, France (1983) · Zbl 0571.68045 |
| [8] | Dijkstra, E.W.: Co-operating sequential Processes. In: Programming Languages 43-112 F. Genuys (ed.). Academic Press, London: 1968 |
| [9] | Best, E, Thiagarajan, P.S.: P24 (iii). In: EATCS Bulletin 20, 310 (1983) |
| [10] | Eilenberg, S., Schützenberger, M.P.: Rational sets in communicative monoids. J. Algebra 13, 173-191 (1969) · Zbl 0206.02703 · doi:10.1016/0021-8693(69)90070-2 |
| [11] | Genrich, H.J., Lautenbach, K.: Facts in place/transition-nets. Lect. Notes Comput. Sci. No 64, pp. 213-231. Berlin-Heidelberg-New York: Springer · Zbl 0389.93002 |
| [12] | Grabowski, J.: Linear methods in the Theory of Vector addition systems I. EIK 16, 207-236 (1980) · Zbl 0447.68060 |
| [13] | Hack, M.: Decision Problems for Petri Nets and Vector Addition Systems. MIT, Proj. MAC, Comput. Struct. Group Memo 95-1 (1974) |
| [14] | Hack, M.: Petri net languages. MIT, Proj. MAC, Comp. Struct. Group Memo 124 (1975) |
| [15] | Hack, M.: The equality problem for vector addition systems is undecidable. Theoret. Comput. Sci. 2, 77-95 (1976) · Zbl 0357.68038 · doi:10.1016/0304-3975(76)90008-6 |
| [16] | Hauschildt, D., Valk, R.: Safe states in banker like resource allocation problems. Proc. 5th. European Workshop Appl. Theory of Petri Nets, Aarhus, 1984 · Zbl 0626.68017 |
| [17] | Jantzen, M., Valk, R.: Formal properties of place/transition nets, In: Net Theory and Applications. W. Brauer (ed.), pp. 165-212. Lect. Notes Comput. Sci. No 84. Berlin-Heidelberg-New York: Springer 1979 |
| [18] | Keller, R.M.: Vector Replacement Systems: A Formalism for Modelling Asynchronous Systems. Comput. Sci. Lab., Princeton Univ., Techn. Rep. 117 (1972, revised 1974) |
| [19] | Karp, R.M., Miller, R.E.: Parallel Program Schemata. J. Comput. Syst. Sci. 3, 147-195 (1969) · Zbl 0198.32603 · doi:10.1016/S0022-0000(69)80011-5 |
| [20] | Landweber, L.H.: Decision problems for ?-automata. Math. Syst. Theory 3, 376-384 (1969) · Zbl 0182.02402 · doi:10.1007/BF01691063 |
| [21] | Lipton, R.J.: The Reachability Problem Requires Exponential Space. Yale Univ., Dept. of Comp. Sci., Research Report #62 (1976) |
| [22] | Nivat, M., Arnold, A.: Comportements de processus. Lab. Informatique Théor. et Programm., Univ. Paris 6 and 7, Paris (1982) · Zbl 0538.68062 |
| [23] | Patil, S.S., Thiagarajan, P.S.: unpublished manuscript |
| [24] | Rackoff, C.: The Covering and Boundedness Problems for Vector Addition Systems. Theor. Comput. Sci. 6, 223-231 (1978) · Zbl 0368.68054 · doi:10.1016/0304-3975(78)90036-1 |
| [25] | Schroff, R.: Vermeidung von totalen Verklemmungen in bewerteten Petrinetzen. Ph.D. Thesis, Techn. Univ. München (1974) · Zbl 0303.68033 |
| [26] | Schroff, R.: Vermeidung von Verklemmungen in bewerteten Petrinetzen. Lect. Notes Comput. Sci. No. 26, pp. 316-325 Berlin-Heidelberg-New York: Springer 1975 · Zbl 0303.68033 |
| [27] | Valk, R.: Prévention des bloquages aux systèmes paralleles, Lecture notes, Univ. Paris VI (1976) |
| [28] | Valk, R.: Infinite behaviour of Petri nets. Theor. Comput. Sci. 25, 311-341 (1983) · Zbl 0559.68057 · doi:10.1016/0304-3975(83)90115-9 |
| [29] | Valk, R., Vidal-Naquet, G.: Petri Nets and Regular Languages. J. Comput. Syst. Sci. 23, 299-325 (1981) · Zbl 0473.68057 · doi:10.1016/0022-0000(81)90067-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
