{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T02:22:09Z","timestamp":1768270929882,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T00:00:00Z","timestamp":1742342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"crossref","award":["AMAR (CUP D53C22002380006) and MAIPM (CUP C63C22000770006)"],"award-info":[{"award-number":["AMAR (CUP D53C22002380006) and MAIPM (CUP C63C22000770006)"]}],"id":[{"id":"10.13039\/100031478","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>Temporal logics over finite traces have recently seen wide application in a number of areas, from business process modelling, monitoring and mining to planning and decision-making. However, real-life dynamic systems contain a degree of uncertainty which cannot be handled with classical logics. We thus propose a new probabilistic temporal logic over finite traces using superposition semantics, where all possible evolutions are possible, until observed. We study the properties of the logic and provide automata-based mechanisms for deriving probabilistic inferences from its formulas. We then study a fragment of the logic with better computational properties. Notably, formulas in this fragment can be discovered from event log data using off-the-shelf existing declarative process discovery techniques.<\/jats:p>","DOI":"10.1145\/3714427","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T13:39:06Z","timestamp":1737466746000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic Temporal Reasoning Using Superposition Semantics"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9089-6896","authenticated-orcid":false,"given":"Fabrizio M.","family":"Maggi","sequence":"first","affiliation":[{"name":"Free University of Bozen-Bolzano, Bolzano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8021-3430","authenticated-orcid":false,"given":"Marco","family":"Montali","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Bolzano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2693-5790","authenticated-orcid":false,"given":"Rafael","family":"Pe\u00f1aloza","sequence":"additional","affiliation":[{"name":"University of Milano-Bicocca, Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.IS.2022.102033"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.006"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10817-010-9181-2"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1373322"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11572"},{"key":"e_1_3_2_7_2","volume-title":"Conformance Checking\u2014Relating Processes and Models","author":"Carmona Josep","year":"2018","unstructured":"Josep Carmona, Boudewijn F. van Dongen, Andreas Solti, and Matthias Weidlich. 2018. Conformance Checking\u2014Relating Processes and Models. Springer."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3661814.3662145"},{"key":"e_1_3_2_9_2","unstructured":"H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. 2007. Tree automata techniques and applications. Retrieved October 12 2007 from http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10172-9_1"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8872"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.11020"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/657"},{"key":"e_1_3_2_14_2","first-page":"854","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI \u201913).","author":"Giacomo Giuseppe De","year":"2013","unstructured":"Giuseppe De Giacomo and Moshe Y. Vardi. 2013. Linear temporal logic and linear dynamic logic on finite traces. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI \u201913). AAAI Press, 854\u2013860."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-08848-3_4"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52954-3_3"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2464827"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56509-4"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.10.012"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90019-V"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211866"},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the 2006 International Workshop on Description Logics (DL \u201906).The Lake District","author":"Hladik Jan","year":"2006","unstructured":"Jan Hladik and Rafael Pe\u00f1aloza. 2006. PSPACE automata for description logics. In Proceedings of the 2006 International Workshop on Description Logics (DL \u201906).Bijan Parsia, Ulrike Sattler, and David Toman (Eds.), CEUR-WS, Vol. 189, The Lake District, UK."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45085-6_8"},{"key":"e_1_3_2_25_2","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeff D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_3_2_28_2","unstructured":"Savas Konur. 2010. Real-time and probabilistic temporal logics: An overview. arXiv:1005.3200. Retrieved from http:\/\/arxiv.org\/abs\/1005.3200"},{"key":"e_1_3_2_29_2","first-page":"561","volume-title":"Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR \u201918).","author":"Kovtunova Alisa","year":"2018","unstructured":"Alisa Kovtunova and Rafael Pe\u00f1aloza. 2018. Cutting diamonds: A temporal logic with probabilistic distributions. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR \u201918). AAAI Press, 561\u2013570."},{"key":"e_1_3_2_30_2","first-page":"388","volume-title":"Proceedings of the 13th European Conference on Artificial Intelligence (ECAI \u201998).","author":"Lukasiewicz Thomas","year":"1998","unstructured":"Thomas Lukasiewicz. 1998. Probabilistic logic programming. In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI \u201998).Henri Prade (Ed.), John Wiley and Sons, 388\u2013392."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31095-9_18"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i06.6583"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58666-9_3"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23059-2_13"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626630"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14538-4"},{"key":"e_1_3_2_37_2","volume-title":"Probabilistic Distributed Temporal Logic","author":"Mor\u00e3o Lu\u00eds","year":"2011","unstructured":"Lu\u00eds Mor\u00e3o. 2011. Probabilistic Distributed Temporal Logic. Master Thesis. Universidade T\u00e9cnica de Lisboa, Portugal."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90031-7"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi077"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/EDOC.2007.14"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30409-5"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","unstructured":"Walter J. Savitch. 1970. Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4 2 (1970) 177\u2013192. DOI: 10.1016\/S0022-0000(70)80006-X","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1115\/DETC2013-13234"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","unstructured":"Helmut Seidl. 1994. Haskell overloading is DEXPTIME-complete. Inform. Process. Lett. 52 2 (1994) 57\u2013 60. DOI: 10.1016\/0020-0190(94)00130-8","DOI":"10.1016\/0020-0190(94)00130-8"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","unstructured":"A. P. Sistla and E. M. Clarke. 1985. The complexity of propositional linear temporal logics. J. ACM 32 3 (1985) 733\u2013749. DOI: 10.1145\/3828.3837","DOI":"10.1145\/3828.3837"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49851-4"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"M. Y. Vardi and P. Wolper. 1994. Reasoning about infinite computations. Information and Computation 115 1 (1994) 1\u201337. DOI: 10.1006\/inco.1994.1092","DOI":"10.1006\/inco.1994.1092"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","unstructured":"Moshe Y. Vardi and Pierre Wolper. 1986. Automata-theoretic techniques for modal logics of programs. J. Comput. Syst. Sci. 32 2 (1986) 183\u2013221. DOI: 10.1016\/0022-0000(86)90026-7","DOI":"10.1016\/0022-0000(86)90026-7"},{"key":"e_1_3_2_49_2","unstructured":"Bruno Woltzenlogel Paleo. 2016. An expressive probabilistic temporal logic. arXiv:1603.07453. Retrieved from http:\/\/arxiv.org\/abs\/1603.07453"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3714427","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3714427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:56Z","timestamp":1750295876000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3714427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,19]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3714427"],"URL":"https:\/\/doi.org\/10.1145\/3714427","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,19]]},"assertion":[{"value":"2024-02-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}