Time Causal Processes in Time Petri Nets with Weak Semantics
https://doi.org/10.15514/ISPRAS-2020-32(4)-19
Abstract
In this paper, we present a method for state space reduction of dense-time Petri nets (TPNs) – an extension of Petri nets by adding a time interval to every transition for its firing. The time elapsing and memory operating policies define different semantics for TPNs. The decidability of many standard problems in the context of TPNs depends on the choice of their semantics. The state space of the TPN is infinite and non-discrete, in general, and, therefore, the analysis of its behavior is rather complicated. To cope with the problem, we elaborate a state space discretization technique and develop a partial order semantics for TPNs equipped with weak time elapsing and intermediate memory policies.
About the Authors
Irina Bonaventurovna VIRBITSKAITE
A.P. Ershov Institute of Informatics Systems,
Novosibirsk State University
Russian Federation
Doctor of Physical and Mathematical Sciences, Professor, Head of the Laboratory of the Theory of Parallel Processes at IIS SB RAS
Russian Federation
Doctor of Physical and Mathematical Sciences, Professor, Head of the Laboratory of the Theory of Parallel Processes at IIS SB RAS
Alexey Yurievich ZUBAREV
A.P. Ershov Institute of Informatics Systems
Russian Federation
PhD student
Russian Federation
PhD student
References
1. M. Boyer and O. H. Roux. On the compared expressiveness of arc, place and transition time Petri nets. Fundamenta Informaticae, vol. 88, no. 3, 2008, pp. 225-249.
2. B. Bérard, F. Cassez, S. Haddad, D. Lime, and O. H. Roux. Comparison of different semantics for time Petri nets. Lecture Notes in Computer Science, vol. 3707, 2005, pp. 293-307.
3. P.-A. Reynier and A. Sangnier. Weak time Petri nets strike back! Lecture Notes in Computer Science, vol. 5710, 2009, pp. 557-571.
4. L. Popova-Zeugmann. Time Petri nets. Springer, 2013, pp. 31-137.
5. T. Aura and J. Lilius. A causal semantics for time Petri nets. Theoretical Computer Science, vol. 243, no. 1-2, 2000, pp. 409-447.
6. H. Fleischhack and C. Stehno. Computing a finite prefix of a time Petri net. Lecture Notes in Computer Science, vol. 2360, 2002, pp. 163-181
7. T. Chatain and C. Jard. Back in time Petri nets. Lecture Notes in Computer Science, vol. 8053, 2013, pp. 91-105.
Review
For citations:
VIRBITSKAITE I.B., ZUBAREV A.Yu. Time Causal Processes in Time Petri Nets with Weak Semantics. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(4):261-284. https://doi.org/10.15514/ISPRAS-2020-32(4)-19
Email this article 