Оценка сверху числа активных таймеров в сетях Петри с временными дугами с помощью динамических систем точек на графах
https://doi.org/10.15514/ISPRAS-2022-34(5)-12
Аннотация
Сети Петри с временными дугами – это временное расширение сетей Петри (TaPN-сети), которое позволяет присваивать таймеры фишкам. Система динамических точек на метрическом графе (DP-система) это другая динамическая модель, которая рассматривается в теории геометрических дискретных динамических систем и, исторически, ее изучение мотивировано изучением распространения локализованных гауссовых волновых пакетов по тонким структурам. DP-система моделирует дискретные ветвящиеся события происходящие в реальном времени. В недавних работах были получены асимптотические оценки на рост числа точек в DP-системах на метрических графах. В данной работе мы предлагаем методы оценки сверху числа различных значений таймеров для подкласса сетей Петри с временными дугами с помощью построения DP-системы на метрическом графе по сети Петри и показывает, что количество различных значений таймеров в исходной сети Петри не превосходят количество точек в DP-системе. Это позволяет переносить известные оценки для DP-систем на сети Петри с временными дугами для выделенного подкласса.
При поддержке: Работа выполнена при поддержке гранта РФФИ 20-07-01103 a.
Об авторе
Леонид Владимирович ДВОРЯНСКИЙ
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Доктор естественных наук (Doctor rerum naturalium), независимый исследователь
Список литературы
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.
Рецензия
Для цитирования:
ДВОРЯНСКИЙ Л.В. Оценка сверху числа активных таймеров в сетях Петри с временными дугами с помощью динамических систем точек на графах. Труды Института системного программирования РАН. 2022;34(5):183-194. https://doi.org/10.15514/ISPRAS-2022-34(5)-12
For citation:
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
Послать статью по эл. почте 