On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

• Autorzy: Finkel Olivier , Skrzypczak Michał
• Języki publikacji: EN

Abstrakty

EN

To identify the causes of performance problems or to predict process behavior, it is essential to have correct and complete event data. This is particularly important for distributed systems with shared resources, e.g., one case can block another case competing for the same machine, leading to inter-case dependencies in performance. However, due to a variety of reasons, real-life systems often record only a subset of all events taking place. To understand and analyze the behavior and performance of processes with shared resources, we aim to reconstruct bounds for timestamps of events in a case that must have happened but were not recorded by inference over events in other cases in the system. We formulate and solve the problem by systematically introducing multi-entity concepts in event logs and process models. We introduce a partial-order based model of a multi-entity event log and a corresponding compositional model for multi-entity processes. We define PQR-systems as a special class of multi-entity processes with shared resources and queues. We then study the problem of inferring from an incomplete event log unobserved events and their timestamps that are globally consistent with a PQR-system. We solve the problem by reconstructing unobserved traces of resources and queues according to the PQR-model and derive bounds for their timestamps using a linear program. While the problem is illustrated for material handling systems like baggage handling systems in airports, the approach can be applied to other settings where recording is incomplete. The ideas have been implemented in ProM and were evaluated using both synthetic and real-life event logs.

Słowa kluczowe

EN

automata and formal languages; Petri nets; infinite words; logic in computer science; cantor topology; borel hierarchy; wadge degrees; highly undecidable properties; unambiguous Petri nets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 3-4
• Strony: 243--291
• Opis fizyczny: Bibliogr. 66 poz., rys.

Twórcy

autor

Finkel Olivier

• nstitut de Math´ematiques de Jussieu - Paris Rive Gauche CNRS, Universit´e de Paris, Sorbonne Universit´e, Paris, France.

autor

Skrzypczak Michał

• Institute of Informatics University of Warsaw

Bibliografia

• [1] Thomas W. Automata on infinite objects. In: van Leeuwen J (ed.), Handbook of Theoretical Computer Science, volume B, Formal models and semantics, Elsevier, 1990 pp. 135-191. doi:10.1016/B978-0-444-88074-1.50009-3.
• [2] Staiger L. ω-languages. In: Handbook of formal languages, Vol. 3, pp. 339-387. Springer, Berlin, 1997. doi:10.1007/978-3-642-59126-6.
• [3] Perrin D, Pin J ´E. Infinite words, automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004. ISBN:978-0-12-532111-2, 0079-8169.
• [4] Engelfriet J, Hoogeboom HJ. X-automata on ω-words. Theoretical Computer Science, 1993. 110(1):1-51. doi:10.1016/0304-3975(93)90349-X.
• [5] Cohen R, Gold A. ω-computations on Turing machines. Theoretical Computer Science, 1978. 6:1-23. doi:0.1016/0304-3975(78)90002-6.
• [6] Valk R. Infinite behaviour of Petri nets. Theoretical computer science, 1983. 25(3):311-341. doi:10.1016/0304-3975(83)90115-9.
• [7] Staiger L. Recursive Automata on Infinite Words. In: Enjalbert P, Finkel A, Wagner KW (eds.), Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 93, Würzburg, Germany, February 25-27, 1993, volume 665 of Lecture Notes in Computer Science. Springer, 1993 pp. 629-639. doi:10.1007/3-540-56503-5 62.
• [8] Lescow H, Thomas W. Logical specifications of infinite computations. In: de Bakker JW, de Roever WP, Rozenberg G (eds.), A Decade of Concurrency, volume 803 of Lecture Notes in Computer Science. Springer, 1994 pp. 583-621. doi:10.1007/3-540-58043-3 29.
• [9] Landweber L. Decision problems for ω-automata. Mathematical Systems Theory, 1969. 3(4):376-384. doi:10.1007/BF01691063.
• [10] Wadge W. Reducibility and determinateness in the Baire space. Ph.D. thesis, University of California, Berkeley, 1983.
• [11] Wagner K. On ω-regular sets. Information and Control, 1979. 43(2):123-177. doi:10.1016/S0019-9958(79)90653-3.
• [12] Selivanov V. Fine Hierarchy of Regular ω-Languages. Theoretical Computer Science, 1998. 191:37-59. doi:10.1007/3-540-59293-8 201.
• [13] Selivanov V. Wadge Reducibility and Infinite Computations. Special Issue on Intensional Programming and Semantics in honour of Bill Wadge on the occasion of his 60th cycle, Mathematics in Computer Science, 2008. 2(1):5-36. doi:10.1007/s11786-008-0042-x.
• [14] Selivanov V. Fine hierarchies and m-reducibilities in theoretical computer science. Theoretical Computer Science, 2008. 405(1-2):116-163. doi:10.1016/j.tcs.2008.06.031.
• [15] Simonnet P. Automates et th´eorie descriptive. Ph.D. thesis, Universit´e Paris VII, 1992.
• [16] Duparc J. A hierarchy of deterministic context free ω-languages. Theoretical Computer Science, 2003. 290(3):1253-1300. doi:10.1016/S0304-3975(02)00567-4.
• [17] Duparc J, Finkel O, Ressayre JP. Computer science and the fine structure of Borel sets. Theoretical Computer Science, 2001. 257(1-2):85-105. doi:10.1016/S0304-3975(00)00111-0.
• [18] Finkel O. An effective extension of the Wagner hierarchy to blind counter automata. In: Proceedings of Computer Science Logic, 15th International Workshop, CSL 2001, volume 2142 of Lecture Notes in Computer Science. Springer, 2001 pp. 369-383. doi:10.1007/3-540-44802-0_26.
• [19] Finkel O. Topological properties of omega context free languages. Theoretical Computer Science, 2001. 262(1-2):669-697. doi:10.1016/S0304-3975(00)00405-9.
• [20] Finkel O. Borel Ranks and Wadge Degrees of Context Free Omega Languages. Mathematical Structures in Computer Science, 2006. 16(5):813-840. URL https://hal.archives-ouvertes.fr/hal-00139169.
• [21] Finkel O. Wadge Degrees of Infinitary Rational Relations. Special Issue on Intensional Programming and Semantics in honour of Bill Wadge on the occasion of his 60th cycle, Mathematics in Computer Science, 2008. 2(1):85-102. doi:10.1007/s11786-008-0045-7.
• [22] Selivanov V. Wadge Degrees of ω-Languages of Deterministic Turing Machines. RAIRO-Theoretical Informatics and Applications, 2003. 37(1):67-83. doi:10.1051/ita:2003008.
• [23] Esparza J. Decidability and complexity of Petri net problems, an introduction. Lectures on Petri Nets I: Basic Models, 1998. pp. 374-428. doi:10.1007/3-540-65306-6_20.
• [24] Rozenberg G. Lectures on concurrency and Petri nets: advances in Petri nets, volume 3098. Springer Verlag, 2004. doi:10.1007/b98282.
• [25] Haddad S. Decidability and Complexity of Petri Net Problems. In: Diaz M (ed.), Petri Nets: Fundamental Models, Verification and Applications, pp. 87-122. Wiley-ISTE, 2009. doi:10.1002/9780470611647.ch4.
• [26] Hopcroft J, Pansiot JJ. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 1979. 8(2):135-159. doi:10.1016/0304-3975(79)90041-0.
• [27] Leroux J, Schmitz S. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, 2019 pp. 1-13. doi:10.1109/LICS.2019.8785796.
• [28] Greibach S. Remarks on Blind and Partially Blind One Way Multicounter Machines. Theoretical Computer Science, 1978. 7:311-324. doi:10.1016/0304-3975(78)90020-8.
• [29] Carstensen H. Infinite behaviour of deterministic Petri nets. In: Proceedings of Mathematical Foundations of Computer Science 1988, volume 324 of Lecture Notes in Computer Science. Springer, 1988 pp. 210-219. doi:10.1007/BFb0017144.
• [30] Duparc J, Finkel O, Ressayre JP. The Wadge hierarchy of Petri nets ω-languages. In: Special Volume in Honor of Victor Selivanov at the occasion of his sixtieth birthday, Logic, computation, hierarchies, volume 4 of Ontos Math. Log., pp. 109-138. De Gruyter, Berlin, 2014. URL https://hal.archives-ouvertes.fr/hal-00743510.
• [31] Finkel O, Skrzypczak M. On the topological complexity of ω-languages of non-deterministic Petri nets. Information Processing Letters, 2014. 114(5):229-233. arXiv:1401.6835 [cs.LO].
• [32] Finkel O. Wadge Degrees of ω-Languages of Petri Nets, 2017. Preprint available from arXiv:1712.07945.
• [33] Finkel O. On the High Complexity of Petri Nets ømega-Languages. In: Janicki R, Sidorova N, Chatain T (eds.), Application and Theory of Petri Nets and Concurrency - 41st International Conference, PETRI NETS 2020, Paris, France, June 24-25, 2020, Proceedings, volume 12152 of Lecture Notes in Computer Science. Springer, 2020 pp. 69-88. doi:10.1007/978-3-030-51831-8_4.
• [34] Skrzypczak M. B¨uchi VASS Recognise Σ1 1-complete ω-languages. In: Proceedings of Reachability Problems - 12th International Conference, RP 2018, Marseille, France, September 24-26, volume 11123 of Lecture Notes in Computer Science. Springer, 2018 pp. 133-145. arXiv:1708.09658 [cs.FL].
• [35] Finkel O. Ambiguity in omega context free languages. Theoretical Computer Science, 2003. 301(1-3):217-270. doi:10.1016/S0304-3975(02)00584-4.
• [36] Finkel O. Ambiguity of ω-Languages of Turing machines. Logical Methods in Computer Science, 2014. 10(3:12):1-18. URL https://hal.archives-ouvertes.fr/hal-00735050.
• [37] Colcombet T. Forms of Determinism for Automata (Invited Talk). In: D¨urr C, Wilke T (eds.), 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th March 3rd 2012, Paris, France, volume 14 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
• 2012 pp. 1-23. doi:10.4230/LIPIcs.STACS.2012.1.
• [38] Stearns RE, III HBH. On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata. SIAM Journal on Computing, 1985. 14(3):598-611. doi:10.1137/0214044.
• [39] Mottet A, Quaas K. The Containment Problem for Unambiguous Register Automata. In: Niedermeier R, Paul C (eds.), 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019 pp. 53:1-53:15. doi:10.4230/LIPIcs.STACS.2019.53.
• [40] Carton O, Michel M. Unambiguous B¨uchi Automata. Theoretical Computer Science, 2003. 297(1–3):37-81. doi:10.1016/S0304-3975(02)00618-7.
• [41] Carayol A, L¨oding C, Niwi´nski D, Walukiewicz I. Choice functions and well-orderings over the infinite binary tree. Central European Journal of Mathematics, 2010. 8:662-682. doi:10.2478/s11533-010-0046-z.
• [42] Finkel O, Simonnet P. Topology and ambiguity in omega context free languages. Bulletin of the Belgian Mathematical Society, 2003. 10(5):707-722. arXiv:0801.0533.
• [43] Finkel O, Simonnet P. On Recognizable Tree Languages Beyond the Borel Hierarchy. Fundamenta Informaticae, 2009. 95(2-3):287-303. arXiv:0909.0393 [math.LO].
• [44] Rabinovich A, Tiferet D. Degrees of Ambiguity of B¨uchi Tree Automata. In: Chattopadhyay A, Gastin P (eds.), 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India, volume 150 of LIPIcs. Schloss Dagstuh - Leibniz-Zentrum f¨ur Informatik, 2019 pp. 50:1-50:14. doi:10.4230/LIPIcs.FSTTCS.2019.50.
• [45] Moschovakis YN. Descriptive set theory. North-Holland Publishing Co., Amsterdam, 1980. doi:10.2307/2273241.
• [46] Kechris AS, Marker D, Sami RL. Π1 1 Borel sets. Journal of Symbolic Logic, 1989. 54(3):915-920. doi:10.2307/2274751.
• [47] Duparc J. Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank. Journal of Symbolic Logic, 2001. 66(1):56-86. doi:10.2307/2694911.
• [48] Kechris AS. Classical descriptive set theory. Springer-Verlag, New York, 1995. ISBN:0-387-94374-9.
• [49] Finkel O. Borel hierarchy and omega context free languages. Theoretical Computer Science, 2003. 290(3):1385-1405. doi:10.1016/S0304-3975(02)00042-7.
• [50] Finkel O. The Determinacy of Context-Free Games. The Journal of Symbolic Logic, 2013. 78(4):1115-1134. arXiv:1312.3412 [cs.LO].
• [51] Jech T. Set theory, third edition. Springer, 2002. doi:10.1007/3-540-44761-X.
• [52] Louveau A, Saint-Raymond J. The strength of Borel Wadge determinacy. In: Cabal Seminar 81-85, volume 1333 of Lecture Notes in Mathematics, pp. 1-30. Springer, 1988. ISBN:978-3-540-45896-8.
• [53] Harrington L. Analytic determinacy and 0♯. Journal of Symbolic Logic, 1978. 43(4):685-693. doi: 10.2307/2273508.
• [54] Finkel O. The complexity of infinite computations in models of set theory. Logical Methods in Computer Science, 2009. 5(4:4):1-19. doi:10.2168/LMCS-5(4:4)2009.
• [55] Finkel O. Highly Undecidable Problems for Infinite Computations. Theoretical Informatics and Applications, 2009. 43(2):339-364. URL http://eudml.org/doc/250587.
• [56] Odifreddi P. Classical Recursion Theory, Vol I, volume 125 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 1989. ISBN:9780444894830, 9780080886596.
• [57] Castro J, Cucker F. Nondeterministic ω-Computations and the Analytical Hierarchy. Journal Math. Logik und Grundlagen d. Math, 1989. 35:333-342. doi:10.1002/malq.19890350406.
• [58] Böhm S, Göller S, Halfon S, Hofman P. On B üchi One-Counter Automata. In: Vollmer H, Vallée B (eds.), 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017 pp. 14:1-14:13. doi:10.4230/LIPIcs.STACS.2017.14.
• [59] Hummel S, Skrzypczak M. The Topological Complexity of MSO+U and Related Automata Models. Fundamenta Informaticae, 2012. 119(1):87-111. doi:10.3233/FI-2012-728.
• [60] Habermehl P. On the complexity of the linear-time μ-calculus for Petri Nets. In: Azéma P, Balbo G (eds.), Application and Theory of Petri Nets 1997. Springer Berlin Heidelberg, 1997 pp. 102-116. doi:10.1007/3-540-63139-9 32.
• [61] Selivanov V. Fine Hierarchy of Regular ω-Languages. In: Proceedings of the International Joint Conference on the Theory and Practice of Software Development TAPSOFT-95, in Aarhus, Denmark, volume 915 of Lecture Notes in Computer Science. Springer, 1995 pp. 277-287. doi:10.1007/3-540-59293-8 201.
• [62] Selivanov V. Wadge Degrees of ω-Languages of Deterministic Turing Machines. In: Proceedings of the International Conference STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, volume 2607 of Lecture Notes in Computer Science. Springer, 2003 pp. 97-108. doi:10.1007/3-540-36494-3_10.
• [63] Selivanov V. Fine Hierarchy of Regular Aperiodic omega-Languages. International Journal of Foundations of Computer Science, 2008. 19(3):649-675. doi:10.1142/S0129054108005875.
• [64] Finkel O. Wadge Hierarchy of omega context free languages. Theoretical Computer Science, 2001. 269(1–2):283-315. doi:10.1016/S0304-3975(01)00008-1.
• [65] Minsky ML. Recursive Unsolvability of Post’s Problem of ”Tag” and other Topics in Theory of Turing Machines. Annals of Mathematics, 1961. 74(3):437-455. doi:10.2307/1970290.
• [66] Mayr R. Undecidable problems in unreliable computations. Theoretical Computer Science, 2003. 297(1):337 - 354. doi:10.1016/S0304-3975(02)00646-1.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)