Nets, sequential components and concurrency relations. (English) Zbl 0546.68039
Two approaches to the notion of concurrency on the system level are discussed. One starts with a given decomposition of a net into sequential components. In the other one the concurrency relation is defined from a given marking class. It is shown that the postulate about a common element for every global system state and every sequential component under minor additional conditions imply the decomposability of the net into finite state machines.
Reviewer: H.Fuss and E.Smith
MSC:
68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
93B17 | Transformations |
93B30 | System identification |
68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
Keywords:
Petri nets; densities; concurrency; decomposition; sequential components; marking class; finite state machinesReferences:
[1] | Best, E., The relative strength of \(K\)-density, (Brauer, W., Net Theory and Applications. Net Theory and Applications, Lecture Notes in Comput. Sci., 84 (1980), Springer: Springer Berlin), 261-278 |
[2] | Hansen, P. Brinch, Operating Systems Principles (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0308.68007 |
[3] | (Brauer, W., Net Theory and Applications. Net Theory and Applications, Lecture Notes in Comput. Sci., 84 (1980), Springer: Springer Berlin) · Zbl 0434.68040 |
[4] | Campbell, R. H.; Habermann, A. H., The Specification of Process Synchronization by Path Expressions, (Lecture Notes in Comput. Sci., 16 (1974), Springer: Springer Berlin), 89-102 · Zbl 0295.68028 |
[5] | De Cindio, F.; De Michelis, G.; Pomello, L.; Simone, C., Superposed, automata nets, (Girault, C.; Reisig, W., Application and Theory of Petri Nets. Application and Theory of Petri Nets, Informatik-Fachberichte, 52 (1982), Springer: Springer Berlin), 269-279 · Zbl 0521.68059 |
[6] | Dijkstra, E. W., Cooperating sequential processes, (Genuys, F., Programming Languages (1968), Academic Press: Academic Press New York) |
[7] | (Girault, C.; Reisig, W., Application and Theory of Petri Nets. Application and Theory of Petri Nets, Informatik-Fachberichte, 52 (1982), Springer: Springer Berlin) · Zbl 0474.68075 |
[8] | Hack, M. T., Analysis of production schemata by Petri nets, (TR-94 (1972), Lab. for Comput. Sci., MIT: Lab. for Comput. Sci., MIT Cambridge, MA) |
[9] | Hoare, C. A.R., Communicating sequential processes, (McKeag, R. M.; MacNaghton, A. M., On the Construction of Programs (1980), Cambridge University Press: Cambridge University Press London), 229-254 · Zbl 0841.68042 |
[10] | Janicki, R., Synthesis of Concurrent Schemes, (Lecture Notes in Comput. Sci., 64 (1978), Springer: Springer Berlin), 298-307 · Zbl 0382.68023 |
[11] | Janicki, R., A Characterisation of Concurrency-like Relations, (Lecture Notes in Comput. Sci., 70 (1979), Springer: Springer Berlin), 109-122 · Zbl 0402.68020 |
[12] | Janicki, R., An Algebraic Structure of Petri Nets, (Lecture Notes in Comput. Sci., 83 (1980), Springer: Springer Berlin), 177-192 · Zbl 0438.68021 |
[13] | Janicki, R., On Atomic Nets and Concurrency Relations, (Lecture Notes in Comput. Sci., 88 (1980), Springer: Springer Berlin), 320-333 · Zbl 0449.68021 |
[14] | Janicki, R., On the design of concurrent systems, (Proc. 2nd Conf. on Distributed Computing Systems (1981), IEEE Comput. Soc. Press: IEEE Comput. Soc. Press New York), 455-466 |
[15] | Janicki, R., Analysis of concurrent systems by means of concurrency relations, Proc. AFCET Symp.. Proc. AFCET Symp., Mathematics for Computer Science (1982), Paris · Zbl 0513.68053 |
[16] | Lauer, P. E.; Shields, M. W.; Contronis, J. Y., Formal Behavioural Specification of Concurrent Systems without Globality Assumptions, (Lecture Notes in Comput. Sci., 107 (1981), Springer: Springer Berlin), 115-151 · Zbl 0481.68012 |
[17] | Mazurkiewicz, A., Concurrent program schemes and their interpretations, (DAIMI PB-78 (1977), Aarhus Univ. Press) |
[18] | Milner, R., A Calculus for Communicating Systems, (Lecture Notes in Comput. Sci., 92 (1980), Springer: Springer Berlin) · Zbl 0609.68021 |
[19] | C.A. Petri, Non-sequential processes, ISF Rept. 77-01, GMD, Bonn.; C.A. Petri, Non-sequential processes, ISF Rept. 77-01, GMD, Bonn. |
[20] | Petri, C. A., Concurrency, (Brauer, W., Net Theory and Applications. Net Theory and Applications, Lecture Notes in Comput. Sci., 84 (1980), Springer: Springer Berlin), 251-260 · Zbl 0434.68041 |
[21] | Petri, C. A., Introduction to general net theory, (Brauer, W., Net Theory and Applications. Net Theory and Applications, Lecture Notes in Comput. Sci., 84 (1980), Springer: Springer Berlin) · Zbl 1027.68642 |
[22] | Prószyński, P., Petri Nets and Concurrency-like Relations, (Lecture Notes in Comput. Sci., 107 (1981), Springer: Springer Berlin), 471-478 · Zbl 0473.68055 |
[23] | Whorf, B. L.; Carroll, J. B., Language, Thought and Reality (1962), Cambridge Univ. Press: Cambridge Univ. Press MA, Selected papers |
[24] | Whorf, B. L., Indian model of universum, Internat. J. Amer. Linguistics, 16, 67-72 (1950) |
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.