Overapproximation of the Number of Active Timers in Timed-Arc Petri Nets Using DP-Systems
https://doi.org/10.15514/ISPRAS-2022-34(5)-12
Abstract
Timed-arcs Petri nets are a time extension of Petri nets that allows assigning clocks to tokens. System of dynamic points on a metric graph (DP-systems) is another dynamical model that is studied in discrete geometry dynamics; DP-system combines continuous time and discrete branching events and used, for example, in study of localized Gaussian wave packets scattering on thin structures. In recent works, asymptotic estimates of the growth of the number of points in dynamic systems on metric graphs were obtained. In this paper, we provide a mean to overapproximate the number of different values of timers for a subclass of timed-arc Petri nets by constructing a system of dynamic points on a metric graph and prove overapproximation of the number of timer values by the number of points in the system of dynamic points.
Supporting agencies: The reported study was funded by RFBR according to the research project 20-07-01103a.
About the Author
Leonid Wladimirovich DWORZANSKI
National Research University Higher School of Economics
Russian Federation
Russian Federation
Doctor of Natural Sciences (Doctor rerum naturalium), independent researcher
References
1. Reisig W. Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. Springer, 2013, 257 p.
2. Berard B., Cassez F. et al. Comparison of different semantics for time Petri Nets. Lecture Notes in Computer Science, vol. 3707, 2005, pp. 293-307.
3. Brown C., Gurr D. Timing Petri Nets categorically. Lecture Notes in Computer Science, vol. 623, 1992, pp. 571-582.
4. Tvardovskii A.S., Yevtushenko N.V. On reduced forms of initialized Finite State Machines with timeouts. Trudy ISP RAN/Proc. ISP RAS, vol. 32, issue 2, 2020. pp. 125-134. DOI: 10.15514/ISPRAS-2020-32(2)-10.
5. Tvardovskii A.S., Laputenko A.V. On the possibilities of FSM description of parallel composition of timed Finite State Machines. Trudy ISP RAN/Proc. ISP RAS, vol. 30, issue 1, 2018, pp. 25-40 (in Russian). DOI: 10.15514/ISPRAS-2018-30(1)-2 / Твардовский А.С., Лапутенко А.В. О возможностях автоматного описания параллельной композиции временных автоматов. Труды ИСП РАН, том 30, вып. 1, 2018 г., стр. 25-40.
6. Akshay S., Genest B., Hélouët L. Decidable Classes of Unbounded Petri Nets with Time and Urgency. Lecture Notes in Computer Science, vol. 9698, 2016, pp. 301–322.
7. Hanisch H.-M. Analysis of place/transition nets with timed arcs and its application to batch process control. Lecture Notes in Computer Science, vol. 961, 1993, pp. 282–299.
8. Chernyshev V., Shafarevich A. Statistics of Gaussian packets on metric and decorated graphs, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 372, 2014, article id 20130145.
9. Dworzanski L.W. Towards dynamic-point systems on metric graphs with longest stabilization time. arXiv preprint arXiv:2010.12528, 15 p.
10. Chernyshev V.L. Tolchennikov A.A., Correction to the leading term of asymptotics in the problem of counting the number of points moving on a metric tree. Russian Journal of Mathematical Physics, vol. 24, issue 3, 2017, pp. 290–298.
11. Chernyshev V.L., Tolchennikov A.A. The second term in the asymptotics for the number of points moving along a metric graph. Regular and Chaotic Dynamics, vol. 22, issue 8, 2017, pp. 937–948.
12. Tolchennikov A.A., Chernyshev V.L., Shafarevich A.I. Asymptotic properties of the classical dynamical systems in quantum problems on singular spaces. Nonlinear Dynamics, vol. 6, issue 3, 2010, pp. 623-638 (in Russian)/ Толченников А.А., Чернышев В.Л., Шафаревич А.И. Асимптотические свойства и классические динамические системы в квантовых задачах на сингулярных пространствах. Нелинейная динамика, том 6, вып. 3, 2010 г., pp. 623-638.
13. Chernyshev V. L., Tolchennikov A. A., Shafarevich A. I., Behavior of quasi-particles on hybrid spaces. relations to the geometry of geodesics and to the problems of analytic number theory, Regular and Chaotic Dynamics, vol. 21, issue 5, 2016, pp. 531-537.
14. Chernyshev V., Tolchennikov A. Asymptotics of the number of endpoints of a random walk on a certain class of directed metric graphs. Russian Journal of Mathematical Physics, vol. 28, issue 4, 2021, pp. 434-438.
15. Pyatko D., Chernyshev V. Asymptotics of the number of possible endpoints of a random walk on a directed hamiltonian metric graph. arXiv preprint arXiv:2112.13822, 2021, 15 p.
16. Cohen G., Gaubert S., Quadrat J.-P., Asymptotic throughput of continuous timed petri nets. In Proc. of the 34th IEEE Conference on Decision and Control, vol. 2, 1995, pp. 2029-2034.
17. Tuncer D., Charalambides M. et al. Adaptive resource man agement and control in software defined networks, IEEE Transactions on Network and Service Management, vol. 12, issue 1, 2015, pp. 18-33.
18. Heidemann J., Stojanovic M., Zorzi M. Underwater sensor networks: applications, advances and challenges. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 370, 2012, pp. 158-175.
19. Liu K., Yang Z. et al. Oceansense: monitoring the sea with wireless sensor networks. Mobile Computing and Communications Review, vol. 14, issue 2, 2010, pp. 7-9.
20. Berkolaiko G., Kuchment P. Introduction to quantum graphs. Mathematical Surveys and Monographs, vol. 186. American Mathematical Society, 2013, 270 p.
21. Bolognesi T., Lucidi F., Trigila S. From timed Petri Nets to timed LOTOS. In Proc. of the IFIP WG6.1 Tenth International Symposium on Protocol Specification, Testing and Verification X, 1990, pp. 377-406.
22. de Frutos-Escrig D., Ruiz V.V., Alonso O.M. Decidability of properties of timed-arc petri nets. Lecture Notes in Computer Science, vol. 1825, 2000, pp. 187–206.
23. Merlin P. A study of the recoverability of computer systems. Ph.D. Thesis, University of California, Irvine, CA, 1974, 154 p.
24. Izmaylov A.A., Dworzanski L.W. Analysis of DP-systems Using Timed-Arc Petri Nets via TAPAAL Tool. Trudy ISP RAN/Proc. ISP RAS, vol. 32, issue 6, 2020, pp. 155-166. DOI: 10.15514/ISPRAS-2020-32(6)-12.
25. David A., Jacobsen L. et al. TAPAAL 2.0: Integrated Development Environment for Timed-Arc Petri Nets. Lecture Notes in Computer Science, vol. 7214, 2012, pp. 492-497.
26. Cabac L., Haustermann M., Mosteller D. Renew 2.5 – towards a comprehensive integrated development environment for Petri Net-based applications. Lecture Notes in Computer Science, vol. 9698, 2016, pp. 101–112.
Review
For citations:
DWORZANSKI L.W. Overapproximation of the Number of Active Timers in Timed-Arc Petri Nets Using DP-Systems. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2022;34(5):183-194. https://doi.org/10.15514/ISPRAS-2022-34(5)-12
Email this article 