<?xml version="1.0" encoding="UTF-8"?> <metadata xmlns="https://drops.dagstuhl.de/storage/schema/dagstuhl/dagpub.xsd"> <volume> <title>31st International Symposium on Temporal Representation and Reasoning (TIME 2024), TIME 2024, October 28-30, 2024, Montpellier, France</title> <shortTitle>TIME 2024</shortTitle> <date>October 28-30, 2024</date> <location>Montpellier, France</location> <conference> <conferenceTitle>International Symposium on Temporal Representation and Reasoning</conferenceTitle> <acronym>TIME</acronym> <website>https://time-symposium.org/</website> <dblp>https://dblp.org/db/conf/time</dblp> </conference> <series> <seriesTitle>Leibniz International Proceedings in Informatics</seriesTitle> <acronym>LIPIcs</acronym> <website>https://www.dagstuhl.de/dagpub/1868-8969</website> <dblp>https://dblp.org/db/series/lipics</dblp> <issn>1868-8969</issn> </series> <editor> <firstName>Pietro</firstName> <lastName>Sala</lastName> <name>Pietro Sala</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-2612-1519</orcid> </editor> <editor> <firstName>Michael</firstName> <lastName>Sioutis</lastName> <name>Michael Sioutis</name> <affiliation>LIRMM UMR 5506, Université de Montpellier &amp; CNRS, France</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-7562-2443</orcid> </editor> <editor> <firstName>Fusheng</firstName> <lastName>Wang</lastName> <name>Fusheng Wang</name> <affiliation>Stony Brook University, NY, USA</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-9369-9361</orcid> </editor> <publisher>Schloss Dagstuhl – Leibniz-Zentrum für Informatik</publisher> <volumeNo>318</volumeNo> <year>2024</year> <isbn>978-3-95977-349-2</isbn> <url>https://www.dagstuhl.de/dagpub/978-3-95977-349-2</url> </volume> <article articleNo="0"> <title>Front Matter, Table of Contents, Preface, Conference Organization</title> <abstract>Front Matter, Table of Contents, Preface, Conference Organization</abstract> <keyword>Front Matter</keyword> <keyword>Table of Contents</keyword> <keyword>Preface</keyword> <keyword>Conference Organization</keyword> <subjectClassification acmID="10003752">Theory of computation</subjectClassification> <subjectClassification acmID="10002951">Information systems</subjectClassification> <subjectClassification acmID="10010147.10010178">Computing methodologies~Artificial intelligence</subjectClassification> <subjectClassification acmID="10010405">Applied computing</subjectClassification> <pages>0:i-0:xiv</pages> <category>Front Matter</category> <acknowledgements/> <author> <firstName>Pietro</firstName> <lastName>Sala</lastName> <name>Pietro Sala</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-2612-1519</orcid> </author> <author> <firstName>Michael</firstName> <lastName>Sioutis</lastName> <name>Michael Sioutis</name> <affiliation>LIRMM UMR 5506, Université de Montpellier &amp; CNRS, France</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-7562-2443</orcid> </author> <author> <firstName>Fusheng</firstName> <lastName>Wang</lastName> <name>Fusheng Wang</name> <affiliation>Stony Brook University, NY, USA</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-9369-9361</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.0</doi> <contentUrl/> <archivedUrl/> <copyright>Pietro Sala, Michael Sioutis, and Fusheng Wang</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="1"> <title>A General Logical Approach to Learning from Time Series (Invited Talk)</title> <abstract>Machine learning from multivariate time series is a common task, and countless different approaches to typical learning problems have been proposed in recent years. In this talk, we review some basic ideas towards logic-based learning methods, and we sketch a general framework.</abstract> <keyword>Machine learning</keyword> <keyword>temporal logic</keyword> <keyword>general approach</keyword> <subjectClassification acmID="10003752.10010070">Theory of computation~Theory and algorithms for application domains</subjectClassification> <pages>1:1-1:2</pages> <category>Invited Talk</category> <funding>We acknowledge the support of the FIRD project Methodological Developments in Modal Symbolic Geometric Learning, funded by the University of Ferrara, and the INDAM-GNCS project Symbolic and Numerical Analysis of Cyberphysical Systems (code CUP_E53C23001670001), funded by INDAM; Guido Sciavicco is a GNCS-INdAM member. Moreover, this research has also been funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI", funded by the European Union under the "NextGeneration EU programme".</funding> <acknowledgements/> <author> <firstName>Guido</firstName> <lastName>Sciavicco</lastName> <name>Guido Sciavicco</name> <affiliation>Department of Mathematics and Computer Science, University of Ferrara, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-9221-879X</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.1</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>D. Del Fante, F. Manzella, G. Sciavicco, and I. E. Stan. A post-modern approach to automatic metaphor identification. In Proc. of the 9th Italian Conference on Computational Linguistics (CLIC), volume 3596 of CEUR Workshop Proceedings. CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3596/short9.pdf.</text> <url>https://ceur-ws.org/Vol-3596/short9.pdf</url> </reference> <reference refNo="2"> <text>R. Hegde, S. Ranjana, and C. D. Divya. Survey on development of smart healthcare monitoring system in iot environment. In Proc. of the 5th International Conference on Computing Methodologies and Communication (ICCMC), pages 395-399, 2021.</text> <url/> </reference> <reference refNo="3"> <text>F. Manzella, G. Pagliarini, G. Sciavicco, and I. E. Stan. The voice of COVID-19: breath and cough recording classification with temporal decision trees and random forests. Artif. Intell. Medicine, 137:102486, 2023. URL: https://doi.org/10.1016/J.ARTMED.2022.102486.</text> <url>https://doi.org/10.1016/J.ARTMED.2022.102486</url> </reference> <reference refNo="4"> <text>S. Mazzacane, M. Coccagna, F. Manzella, G. Pagliarini, V. A. Sironi, A. Gatti, E. Caselli, and G. Sciavicco. Towards an objective theory of subjective liking: A first step in understanding the sense of beauty. PLOS ONE, 18(6):1-20, June 2023.</text> <url/> </reference> <reference refNo="5"> <text>Y. Ran, X. Zhou, P. Lin, Y. Wen, and R. Deng. A survey of predictive maintenance: Systems, purposes and approaches. ArXiv, abs/1912.07383, 2019. URL: https://arxiv.org/abs/1912.07383.</text> <url>https://arxiv.org/abs/1912.07383</url> </reference> <copyright>Guido Sciavicco</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="2"> <title>Strategic Reasoning Under Imperfect Information with Synchronous Semantics (Invited Talk)</title> <abstract>Dynamic Epistemic Logic is a modal logic dedicated to specifying epistemic property changes along the dynamic behavior of a multi-agent system. The models that underlie this logic are (epistemic) states together with transitions caused by events, the occurrence of which may modify the current state. We first develop a setting where the entire dynamics of the system starting from an initial state is captured by a single infinite tree, in a way similar to what has been considered for Epistemic Temporal Logic, and second go through the current state-of-the-art regarding strategic reasoning, with a focus on planning problems in this infinite structure.</abstract> <keyword>Strategic reasoning</keyword> <keyword>Imperfect information</keyword> <keyword>chain-MSO</keyword> <keyword>Automatic structures</keyword> <subjectClassification acmID="10003752.10003766">Theory of computation~Formal languages and automata theory</subjectClassification> <subjectClassification acmID="10003752.10003790.10002990">Theory of computation~Logic and verification</subjectClassification> <subjectClassification acmID="10003752.10003790.10003793">Theory of computation~Modal and temporal logics</subjectClassification> <subjectClassification acmID="10003752.10003790.10011192">Theory of computation~Verification by model checking</subjectClassification> <pages>2:1-2:2</pages> <category>Invited Talk</category> <acknowledgements/> <author> <firstName>Sophie</firstName> <lastName>Pinchinat</lastName> <name>Sophie Pinchinat</name> <affiliation>IRISA Laboratory/University of Rennes, France</affiliation> <homepageUrl>https://people.irisa.fr/Sophie.Pinchinat/</homepageUrl> <orcid>https://orcid.org/0000-0002-0901-8480</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.2</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Achim Blumensath and Erich Grädel. Automatic structures. In Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on, pages 51-62. IEEE, 2000. URL: https://doi.org/10.1109/LICS.2000.855755.</text> <url>https://doi.org/10.1109/LICS.2000.855755</url> </reference> <reference refNo="2"> <text>Thomas Bolander, Tristan Charrier, Sophie Pinchinat, and François Schwarzentruber. Del-based epistemic planning: Decidability and complexity. Artif. Intell., 287:103304, 2020. URL: https://doi.org/10.1016/j.artint.2020.103304.</text> <url>https://doi.org/10.1016/j.artint.2020.103304</url> </reference> <reference refNo="3"> <text>Gaëtan Douéneau-Tabot, Sophie Pinchinat, and François Schwarzentruber. Chain-monadic second order logic over regular automatic trees and epistemic planning synthesis. In Guram Bezhanishvili, Giovanna D'Agostino, George Metcalfe, and Thomas Studer, editors, Advances in Modal Logic 12, proceedings of the 12th conference on "Advances in Modal Logic," held in Bern, Switzerland, August 27-31, 2018, pages 237-256. College Publications, 2018. URL: http://www.aiml.net/volumes/volume12/DoueneauTabot-Pinchinat-Schwarzentruber.pdf.</text> <url>http://www.aiml.net/volumes/volume12/DoueneauTabot-Pinchinat-Schwarzentruber.pdf</url> </reference> <reference refNo="4"> <text>Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Logic and computational complexity, pages 367-392. Springer, 1995.</text> <url/> </reference> <reference refNo="5"> <text>Bastien Maubert. Logical foundations of games with imperfect information: uniform strategies. PhD thesis, Université Rennes 1, 2014.</text> <url/> </reference> <reference refNo="6"> <text>Bastien Maubert, Aniello Murano, Sophie Pinchinat, François Schwarzentruber, and Silvia Stranieri. Dynamic epistemic logic games with epistemic temporal goals. In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang, editors, ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pages 155-162. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200088.</text> <url>https://doi.org/10.3233/FAIA200088</url> </reference> <reference refNo="7"> <text>Bastien Maubert, Sophie Pinchinat, François Schwarzentruber, and Silvia Stranieri. Concurrent games in dynamic epistemic logic. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 1877-1883. ijcai.org, 2020. URL: https://doi.org/10.24963/ijcai.2020/260.</text> <url>https://doi.org/10.24963/ijcai.2020/260</url> </reference> <reference refNo="8"> <text>Côme Neyrand and Sophie Pinchinat. On the role of postconditions in dynamic first-order epistemic logic. CoRR, abs/2205.00876, 2022. URL: https://doi.org/10.48550/arXiv.2205.00876.</text> <url>https://doi.org/10.48550/arXiv.2205.00876</url> </reference> <reference refNo="9"> <text>Michael O Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the american Mathematical Society, 141:1-35, 1969.</text> <url/> </reference> <reference refNo="10"> <text>Wolfgang Thomas. Infinite trees and automaton-definable relations over ω-words. Theoretical Computer Science, 103(1):143-159, 1992.</text> <url/> </reference> <reference refNo="11"> <text>Hans Van Ditmarsch, Wiebe van Der Hoek, and Barteld Kooi. Dynamic epistemic logic, volume 337. Springer Science &amp; Business Media, 2007.</text> <url/> </reference> <copyright>Sophie Pinchinat</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="3"> <title>Rule-Based Temporal Reasoning: Exploring DatalogMTL (Invited Talk)</title> <abstract>I will introduce DatalogMTL - an extension of Datalog, augmenting it with operators known from metric temporal logic (MTL). DatalogMTL is an expressive language which allows us for complex temporal reasoning over a dense timeline and, at the same time, remains decidable. I will provide an overview of research on DatalogMTL by discussing its computational complexity, syntactic and semantic modifications, practical reasoning approaches, applications, and future research directions.</abstract> <keyword>Temporal Datalog</keyword> <keyword>Temporal Logic Programming</keyword> <keyword>Temporal Reasoning</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <pages>3:1-3:3</pages> <category>Invited Talk</category> <funding>This research was partially supported by the EPSRC projects OASIS (EP/S032347/1), ConCuR (EP/V050869/1) and UK FIRES (EP/S019111/1), as well as SIRIUS Centre for Scalable Data Access and Samsung Research UK.</funding> <acknowledgements>The research surveyed in this talk is a result of a joint work with Bernardo Cuenca Grau, Mark Kaminski, Egor V. Kostylev, Michał Zawidzki, Dingmin Wang, David Tena Cucala, Pan Hu, Matthias Lanzinger, Markus Nissl, and Emanuel Sallinger.</acknowledgements> <author> <firstName>Przemysław Andrzej</firstName> <lastName>Wałęga</lastName> <name>Przemysław Andrzej Wałęga</name> <affiliation>University of Oxford, UK</affiliation> <affiliation>Queen Mary University of London, UK</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-2922-0472</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.3</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Luigi Bellomarini, Emanuel Sallinger, and Georg Gottlob. The Vadalog system: Datalog-based reasoning for knowledge graphs. Proc. VLDB Endow., 11(9):975-987, 2018. URL: https://doi.org/10.14778/3213880.3213888.</text> <url>https://doi.org/10.14778/3213880.3213888</url> </reference> <reference refNo="2"> <text>Sebastian Brandt, Elem Güzel Kalaycı, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. Querying log data with metric temporal logic. J. Artif. Intell. Res., 62:829-877, 2018. URL: https://doi.org/10.1613/JAIR.1.11229.</text> <url>https://doi.org/10.1613/JAIR.1.11229</url> </reference> <reference refNo="3"> <text>Elem Güzel Kalayci, Sebastian Brandt, Diego Calvanese, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. Ontology–based access to temporal data with Ontop: A framework proposal. Int. J. Appl. Math. Comput. Sci, 29(1):17-30, 2019. URL: https://doi.org/10.2478/AMCS-2019-0002.</text> <url>https://doi.org/10.2478/AMCS-2019-0002</url> </reference> <reference refNo="4"> <text>Przemysław Andrzej Wałęga, Bernardo Cuenca Grau, Mark Kaminski, and Egor V. Kostylev. DatalogMTL: Computational complexity and expressive power. In Sarit Kraus, editor, Proc. IJCAI, pages 1886-1892, 2019.</text> <url/> </reference> <reference refNo="5"> <text>Dingmin Wang, Pan Hu, Przemysław Andrzej Wałęga, and Bernardo Cuenca Grau. MeTeoR: Practical reasoning in datalog with metric temporal operators. In Proc. AAAI, pages 5906-5913, 2022.</text> <url/> </reference> <reference refNo="6"> <text>Przemysław Andrzej Wałęga, David J. Tena Cucala, Bernardo Cuenca Grau, and Egor V. Kostylev. The stable model semantics of Datalog with metric temporal operators. Theory Pract. Log. Program., 24(1):22-56, 2024. URL: https://doi.org/10.1017/S1471068423000315.</text> <url>https://doi.org/10.1017/S1471068423000315</url> </reference> <reference refNo="7"> <text>Przemysław Andrzej Wałęga, Mark Kaminski, Dingmin Wang, and Bernardo Cuenca Grau. Stream reasoning with DatalogMTL. J. Web Semant., 76:100776, 2023. URL: https://doi.org/10.1016/J.WEBSEM.2023.100776.</text> <url>https://doi.org/10.1016/J.WEBSEM.2023.100776</url> </reference> <reference refNo="8"> <text>Przemysław Andrzej Wałęga, Michał Zawidzki, and Bernardo Cuenca Grau. Finite materialisability of Datalog programs with metric temporal operators. J. Artif. Intell. Res., 76:471-521, 2023. URL: https://doi.org/10.1613/JAIR.1.14040.</text> <url>https://doi.org/10.1613/JAIR.1.14040</url> </reference> <copyright>Przemysław Andrzej Wałęga</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="4"> <title>Agile Controllability of Simple Temporal Networks with Uncertainty and Oracles</title> <abstract>Simple temporal networks with uncertainty (STNUs) have achieved wide attention and are the basis of many applications requiring the representation of temporal constraints and checking whether they are conflicting. Dynamic controllability is currently the most relaxed notion to check whether a system can be controlled without violating temporal constraints despite uncertainties. However, dynamic controllability assumes that the actual duration of a contingent activity is only known when the end event of this activity takes place. The recently introduced notion of agile controllability considers when this duration is known earlier, leading to a more relaxed notion of temporal feasibility. We extend the definition of STNUs to STNUOs (Simple Temporal Networks with Uncertainty and Oracles) to represent the point in time at which information about a contingent duration is available. We formally define agile controllability as a generalization of dynamic controllability considering the timepoints of information availability. We propose a set of constraint propagation rules for STNUOs leading to an algorithm for checking agile controllability.</abstract> <keyword>Temporal constraint networks</keyword> <keyword>contingent durations</keyword> <keyword>agile controllability</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <subjectClassification acmID="10003752.10003809.10003635.10010038">Theory of computation~Dynamic graph algorithms</subjectClassification> <pages>4:1-4:16</pages> <category>Regular Paper</category> <supplements> <url category="Software">https://git-isys.aau.at/ics/Papers/stnuo.git</url> <url category="Dataset">https://profs.scienze.univr.it/~posenato/software/benchmarks/OSTNUBenchmarks2024.tgz</url> </supplements> <acknowledgements/> <author> <firstName>Johann</firstName> <lastName>Eder</lastName> <name>Johann Eder</name> <affiliation>University of Klagenfurt, Austria</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-6050-468X</orcid> </author> <author> <firstName>Roberto</firstName> <lastName>Posenato</lastName> <name>Roberto Posenato</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-0944-0419</orcid> </author> <author> <firstName>Carlo</firstName> <lastName>Combi</lastName> <name>Carlo Combi</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-4837-4701</orcid> </author> <author> <firstName>Marco</firstName> <lastName>Franceschetti</lastName> <name>Marco Franceschetti</name> <affiliation>University of St. Gallen, Switzerland</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-7030-282X</orcid> </author> <author> <firstName>Franziska S.</firstName> <lastName>Hollauf</lastName> <name>Franziska S. Hollauf</name> <affiliation>University of Klagenfurt, Austria</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-1098-8713</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.4</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Shyan Akmal, Savana Ammons, Hemeng Li, Michael Gao, Lindsay Popowski, and James C. Boerkoel Jr. Quantifying controllability in temporal networks with uncertainty. Artif. Intell., 289:103384, 2020. URL: https://doi.org/10.1016/J.ARTINT.2020.103384.</text> <url>https://doi.org/10.1016/J.ARTINT.2020.103384</url> </reference> <reference refNo="2"> <text>Arthur Bit-Monnot and Paul Morris. Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments. Journal of Artificial Intelligence Research, 77:1311-1369, August 2023. URL: https://doi.org/10.1613/jair.1.13065.</text> <url>https://doi.org/10.1613/jair.1.13065</url> </reference> <reference refNo="3"> <text>Massimo Cairo, Luke Hunsberger, and Romeo Rizzi. Faster dynamic controllability checking for simple temporal networks with uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018), volume 120 of LIPIcs, pages 8:1-8:16, 2018. ISBN: 9783959770897. URL: https://doi.org/10.4230/LIPIcs.TIME.2018.8.</text> <url>https://doi.org/10.4230/LIPIcs.TIME.2018.8</url> </reference> <reference refNo="4"> <text>Massimo Cairo and Romeo Rizzi. Dynamic controllability of simple temporal networks with uncertainty: Simple rules and fast real-time execution. Theoretical Computer Science, 797:2-16, 2019. URL: https://doi.org/10.1016/J.TCS.2018.11.005.</text> <url>https://doi.org/10.1016/J.TCS.2018.11.005</url> </reference> <reference refNo="5"> <text>Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.</text> <url>https://doi.org/10.1016/0004-3702(91)90006-6</url> </reference> <reference refNo="6"> <text>Johann Eder, Marco Franceschetti, and Julius Köpke. Controllability of business processes with temporal variables. In ACM SAC 2019, pages 40-47, 2019. URL: https://doi.org/10.1145/3297280.3297286.</text> <url>https://doi.org/10.1145/3297280.3297286</url> </reference> <reference refNo="7"> <text>Johann Eder, Marco Franceschetti, and Josef Lubas. Time and processes: Towards engineering temporal requirements. In Proceedings of the 16th International Conference on Software Technologies, ICSOFT 2021, pages 9-16. SCITEPRESS, 2021. URL: https://doi.org/10.5220/0010625400090016.</text> <url>https://doi.org/10.5220/0010625400090016</url> </reference> <reference refNo="8"> <text>Marco Franceschetti and Johann Eder. Checking temporal service level agreements for web service compositions with temporal parameters. In 2019 IEEE International Conference on Web Services (ICWS), pages 443-445. IEEE, 2019. URL: https://doi.org/10.1109/ICWS.2019.00080.</text> <url>https://doi.org/10.1109/ICWS.2019.00080</url> </reference> <reference refNo="9"> <text>Marco Franceschetti and Johann Eder. Semi-contingent task durations: Characterization and controllability. In Marcello La Rosa, Shazia W. Sadiq, and Ernest Teniente, editors, Advanced Information Systems Engineering - 33rd International Conference, CAiSE 2021, Melbourne, VIC, Australia, June 28 - July 2, 2021, Proceedings, volume 12751 of Lecture Notes in Computer Science, pages 246-261. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79382-1_15.</text> <url>https://doi.org/10.1007/978-3-030-79382-1_15</url> </reference> <reference refNo="10"> <text>Marco Franceschetti, Roberto Posenato, Carlo Combi, and Johann Eder. Dynamic Controllability of Parameterized CSTNUs. In ACM SAC 2023, pages 965-973, 2023. URL: https://doi.org/10.1145/3555776.3577618.</text> <url>https://doi.org/10.1145/3555776.3577618</url> </reference> <reference refNo="11"> <text>Luke Hunsberger. Efficient execution of dynamically controllable simple temporal networks with uncertainty. Acta Informatica, 53:89-147, 2016. URL: https://doi.org/10.1007/S00236-015-0227-0.</text> <url>https://doi.org/10.1007/S00236-015-0227-0</url> </reference> <reference refNo="12"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the RUL¯ Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, pages 9776-9785. AAAI Press, 2022. URL: https://doi.org/10.1609/aaai.v36i9.21213.</text> <url>https://doi.org/10.1609/aaai.v36i9.21213</url> </reference> <reference refNo="13"> <text>Luke Hunsberger and Roberto Posenato. A Faster Algorithm for Converting Simple Temporal Networks with Uncertainty into Dispatchable Form. Information and Computation, 293, June 2023. URL: https://doi.org/10.1016/j.ic.2023.105063.</text> <url>https://doi.org/10.1016/j.ic.2023.105063</url> </reference> <reference refNo="14"> <text>Andreas Lanz, Roberto Posenato, Carlo Combi, and Manfred Reichert. Simple Temporal Networks with Partially Shrinkable Uncertainty. In Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART 2015), volume 2, 2015. URL: https://doi.org/10.5220/0005200903700381.</text> <url>https://doi.org/10.5220/0005200903700381</url> </reference> <reference refNo="15"> <text>Josef Lubas and Johann Eder. A time-aware model for legal smart contracts. In Han van der Aa, Dominik Bork, Henderik A. Proper, and Rainer Schmidt, editors, Enterprise, Business-Process and Information Systems Modeling, pages 121-135, Cham, 2023. Springer Nature Switzerland. URL: https://doi.org/10.1007/978-3-031-34241-7_9.</text> <url>https://doi.org/10.1007/978-3-031-34241-7_9</url> </reference> <reference refNo="16"> <text>Paul Morris. Dynamic controllability and dispatchability relationships. In CPAIOR 2014, volume 8451 of LNCS, 2014. URL: https://doi.org/10.1007/978-3-319-07046-9_33.</text> <url>https://doi.org/10.1007/978-3-319-07046-9_33</url> </reference> <reference refNo="17"> <text>Paul H. Morris and Nicola Muscettola. Temporal dynamic controllability revisited. In 20th National Conf. on Artificial Intelligence (AAAI-2005), 2005. URL: https://cdn.aaai.org/AAAI/2005/AAAI05-189.pdf.</text> <url>https://cdn.aaai.org/AAAI/2005/AAAI05-189.pdf</url> </reference> <reference refNo="18"> <text>Roberto Posenato. CSTNU Tool: A Java library for checking temporal networks. SoftwareX, 17:100905, 2022. URL: https://doi.org/10.1016/j.softx.2021.100905.</text> <url>https://doi.org/10.1016/j.softx.2021.100905</url> </reference> <reference refNo="19"> <text>Roberto Posenato and Carlo Combi. Adding flexibility to uncertainty: Flexible simple temporal networks with uncertainty (FTNU). Inf. Sci., 584:784-807, 2022. URL: https://doi.org/10.1016/J.INS.2021.10.008.</text> <url>https://doi.org/10.1016/J.INS.2021.10.008</url> </reference> <reference refNo="20"> <text>Roberto Posenato and Carlo Combi. Flexible temporal constraint management in modularized processes. Inf. Syst., 118:102257, 2023. URL: https://doi.org/10.1016/J.IS.2023.102257.</text> <url>https://doi.org/10.1016/J.IS.2023.102257</url> </reference> <reference refNo="21"> <text>Roberto Posenato, Marco Franceschetti, Carlo Combi, and Johann Eder. Some results and challenges Extending Dynamic Controllability to Agile Controllability in Simple Temporal Networks with Uncertainties. TechRep 1/2023, Dip. Informatica-Univ. di Verona, 2023. URL: https://iris.univr.it/handle/11562/1116013.</text> <url>https://iris.univr.it/handle/11562/1116013</url> </reference> <reference refNo="22"> <text>Roberto Posenato, Marco Franceschetti, Carlo Combi, and Johann Eder. Introducing agile controllability in temporal business processes. In Enterprise, Business-Process and Information Systems Modeling - 25th International Conference, BPMDS 2024, and 29th International Conference, EMMSAD 2024, volume 511 of Lecture Notes in Business Information Processing, pages 87-99. Springer, 2024. URL: https://doi.org/10.1007/978-3-031-61007-3_8.</text> <url>https://doi.org/10.1007/978-3-031-61007-3_8</url> </reference> <reference refNo="23"> <text>Roberto Posenato, Andreas Lanz, Carlo Combi, and Manfred Reichert. Managing time-awareness in modularized processes. Softw. Syst. Model., 18(2):1135-1154, 2019. URL: https://doi.org/10.1007/S10270-017-0643-4.</text> <url>https://doi.org/10.1007/S10270-017-0643-4</url> </reference> <reference refNo="24"> <text>Michael Saint-Guillain, Tiago Vaquero, Steve A. Chien, Jagriti Agrawal, and Jordan R. Abrahams. Probabilistic temporal networks with ordinary distributions: Theory, robustness and expected utility. J. Artif. Intell. Res., 71:1091-1136, 2021. URL: https://doi.org/10.1613/JAIR.1.13019.</text> <url>https://doi.org/10.1613/JAIR.1.13019</url> </reference> <reference refNo="25"> <text>Thierry Vidal and Hélène Fargier. Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell., 11(1), 1999. URL: https://doi.org/10.1080/095281399146607.</text> <url>https://doi.org/10.1080/095281399146607</url> </reference> <copyright>Johann Eder, Roberto Posenato, Carlo Combi, Marco Franceschetti, and Franziska S. Hollauf</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="5"> <title>Open the Chests: An Environment for Activity Recognition and Sequential Decision Problems Using Temporal Logic</title> <abstract>This article presents Open the Chests, a novel benchmark environment designed for simulating and testing activity recognition and reactive decision-making algorithms. By leveraging temporal logic, Open the Chests offers a dynamic, event-driven simulation platform that illustrates the complexities of real-world systems. The environment contains multiple chests, each representing an activity pattern that an interacting agent must identify and respond to by pressing a corresponding button. The agent must analyze sequences of asynchronous events generated by the environment to recognize these patterns and make informed decisions. With the aim of theoretically grounding the environment, the Activity-Based Markov Decision Process (AB-MDP) is defined, allowing to model the context-dependent interaction with activities. Our goal is to propose a robust tool for the development, testing, and bench-marking of algorithms that is illustrative of realistic scenarios and allows for the isolation of specific complexities in event-driven environments.</abstract> <keyword>Event-Based Decision Making</keyword> <keyword>Activity Recognition</keyword> <keyword>Temporal Logic</keyword> <keyword>Reinforcement Learning</keyword> <keyword>Dynamic Systems</keyword> <keyword>Complex Event Processing</keyword> <keyword>Benchmark Environment</keyword> <keyword>Real-Time Simulation</keyword> <subjectClassification acmID="10010147.10010341.10010366.10010367">Computing methodologies~Simulation environments</subjectClassification> <pages>5:1-5:19</pages> <category>Regular Paper</category> <supplements> <url category="Software" subCategory="Source Code" softwareHeritageId="swh:1:dir:4c883ad251fc88889142844a79d0d71cc667dd40;origin=https://github.com/ThalesGroup/open-the-chests;visit=swh:1:snp:18be3b91fcfaed5be55bb312e6abe64dba04371a;anchor=swh:1:rev:b46b569541d6d3f24af3f0283e83700a5a9b9c61">https://github.com/ThalesGroup/open-the-chests</url> </supplements> <acknowledgements/> <author> <firstName>Ivelina</firstName> <lastName>Stoyanova</lastName> <name>Ivelina Stoyanova</name> <affiliation>U2IS, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France</affiliation> <affiliation>THALES, Palaiseau, France</affiliation> <homepageUrl/> <orcid/> </author> <author> <firstName>Nicolas</firstName> <lastName>Museux</lastName> <name>Nicolas Museux</name> <affiliation>THALES, Palaiseau, France</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-8097-8604</orcid> </author> <author> <firstName>Sao Mai</firstName> <lastName>Nguyen</lastName> <name>Sao Mai Nguyen</name> <affiliation>U2IS, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France</affiliation> <homepageUrl>http://nguyensmai.free.fr</homepageUrl> <orcid>https://orcid.org/0000-0003-0929-0019</orcid> </author> <author> <firstName>David</firstName> <lastName>Filliat</lastName> <name>David Filliat</name> <affiliation>U2IS, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France</affiliation> <homepageUrl/> <orcid/> </author> <doi>10.4230/LIPIcs.TIME.2024.5</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Marc G Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in Neural Information Processing Systems, 2021.</text> <url/> </reference> <reference refNo="2"> <text>Elias Alevizos, Anastasios Skarlatidis, Alexander Artikis, and Georgios Paliouras. Probabilistic complex event recognition: A survey. ACM Computing Surveys (CSUR), 50(5):1-31, 2017. URL: https://doi.org/10.1145/3117809.</text> <url>https://doi.org/10.1145/3117809</url> </reference> <reference refNo="3"> <text>James F Allen and George Ferguson. Actions and events in interval temporal logic. Journal of logic and computation, 4(5):531-579, 1994. URL: https://doi.org/10.1093/LOGCOM/4.5.531.</text> <url>https://doi.org/10.1093/LOGCOM/4.5.531</url> </reference> <reference refNo="4"> <text>Anindya Das Antar, Masud Ahmed, and Md Atiqur Rahman Ahad. Challenges in sensor-based human activity recognition and a comparative analysis of benchmark datasets: A review. In 2019 Joint 8th International Conference on Informatics, Electronics &amp; Vision (ICIEV) and 2019 3rd International Conference on Imaging, Vision &amp; Pattern Recognition (icIVPR), pages 134-139. IEEE, 2019.</text> <url/> </reference> <reference refNo="5"> <text>Fahiem Bacchus, Craig Boutilier, and Adam Grove. Structured solution methods for non-markovian decision processes. In AAAI/IAAI, pages 112-117. Citeseer, 1997. URL: http://www.aaai.org/Library/AAAI/1997/aaai97-018.php.</text> <url>http://www.aaai.org/Library/AAAI/1997/aaai97-018.php</url> </reference> <reference refNo="6"> <text>Iyad Batal, Gregory F Cooper, Dmitriy Fradkin, James Harrison, Fabian Moerchen, and Milos Hauskrecht. An efficient pattern mining approach for event detection in multivariate temporal data. Knowledge and information systems, 46:115-150, 2016. URL: https://doi.org/10.1007/S10115-015-0819-6.</text> <url>https://doi.org/10.1007/S10115-015-0819-6</url> </reference> <reference refNo="7"> <text>Benjamin Beyret, José Hernández-Orallo, Lucy Cheke, Marta Halina, Murray Shanahan, and Matthew Crosby. The animal-ai environment: Training and testing animal-like artificial cognition. arXiv preprint arXiv:1909.07483, 2019. URL: https://arxiv.org/abs/1909.07483.</text> <url>https://arxiv.org/abs/1909.07483</url> </reference> <reference refNo="8"> <text>Damien Bouchabou, Sao Mai Nguyen, Christophe Lohr, Benoit LeDuc, and Ioannis Kanellos. A survey of human activity recognition in smart homes based on iot sensors algorithms: Taxonomies, challenges, and opportunities with deep learning. Sensors, 21(18):6037, 2021. URL: https://doi.org/10.3390/S21186037.</text> <url>https://doi.org/10.3390/S21186037</url> </reference> <reference refNo="9"> <text>Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1-94, 1999. URL: https://doi.org/10.1613/JAIR.575.</text> <url>https://doi.org/10.1613/JAIR.575</url> </reference> <reference refNo="10"> <text>Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. URL: https://arxiv.org/abs/arXiv:1606.01540.</text> <url>https://arxiv.org/abs/arXiv:1606.01540</url> </reference> <reference refNo="11"> <text>Christos G Cassandras and Stéphane Lafortune. Introduction to discrete event systems. Springer, 2008.</text> <url/> </reference> <reference refNo="12"> <text>Wuhui Chen, Xiaoyu Qiu, Ting Cai, Hong-Ning Dai, Zibin Zheng, and Yan Zhang. Deep reinforcement learning for internet of things: A comprehensive survey. IEEE Communications Surveys &amp; Tutorials, 23(3):1659-1692, 2021. URL: https://doi.org/10.1109/COMST.2021.3073036.</text> <url>https://doi.org/10.1109/COMST.2021.3073036</url> </reference> <reference refNo="13"> <text>Jean-René Coffi, Christophe Marsala, and Nicolas Museux. Adaptive complex event processing for harmful situation detection. Evolving Systems, 3:167-177, 2012. URL: https://doi.org/10.1007/S12530-012-9052-7.</text> <url>https://doi.org/10.1007/S12530-012-9052-7</url> </reference> <reference refNo="14"> <text>Gianpaolo Cugola and Alessandro Margara. Processing flows of information: From data stream to complex event processing. ACM Computing Surveys (CSUR), 44(3):1-62, 2012. URL: https://doi.org/10.1145/2187671.2187677.</text> <url>https://doi.org/10.1145/2187671.2187677</url> </reference> <reference refNo="15"> <text>Ala’ Darabseh and Nikolaos M Freris. A software-defined architecture for control of iot cyberphysical systems. Cluster Computing, 22(4):1107-1122, 2019. URL: https://doi.org/10.1007/S10586-018-02889-8.</text> <url>https://doi.org/10.1007/S10586-018-02889-8</url> </reference> <reference refNo="16"> <text>Dario Della Monica, Valentin Goranko, Angelo Montanari, and Guido Sciavicco. Interval temporal logics: a journey. Bulletin of EATCS, 3(105), 2013.</text> <url/> </reference> <reference refNo="17"> <text>Florenc Demrozi, Graziano Pravadelli, Azra Bihorac, and Parisa Rashidi. Human activity recognition using inertial, physiological and environmental sensors: A comprehensive survey. IEEE access, 8:210816-210836, 2020. URL: https://doi.org/10.1109/ACCESS.2020.3037715.</text> <url>https://doi.org/10.1109/ACCESS.2020.3037715</url> </reference> <reference refNo="18"> <text>Derui Ding, Qing-Long Han, Yang Xiang, Xiaohua Ge, and Xian-Ming Zhang. A survey on security control and attack detection for industrial cyber-physical systems. Neurocomputing, 275:1674-1683, 2018. URL: https://doi.org/10.1016/J.NEUCOM.2017.10.009.</text> <url>https://doi.org/10.1016/J.NEUCOM.2017.10.009</url> </reference> <reference refNo="19"> <text>Anton Dries and Luc De Raedt. Towards clausal discovery for stream mining. In Inductive Logic Programming: 19th International Conference, ILP 2009, Leuven, Belgium, July 02-04, 2009. Revised Papers 19, pages 9-16. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13840-9_2.</text> <url>https://doi.org/10.1007/978-3-642-13840-9_2</url> </reference> <reference refNo="20"> <text>Gabriel Dulac-Arnold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 110(9):2419-2468, 2021. URL: https://doi.org/10.1007/S10994-021-05961-4.</text> <url>https://doi.org/10.1007/S10994-021-05961-4</url> </reference> <reference refNo="21"> <text>Kevin Esslinger, Robert Platt, and Christopher Amato. Deep transformer q-networks for partially observable reinforcement learning. arXiv preprint arXiv:2206.01078, 2022. URL: https://doi.org/10.48550/arXiv.2206.01078.</text> <url>https://doi.org/10.48550/arXiv.2206.01078</url> </reference> <reference refNo="22"> <text>Ido Finder, Eitam Sheetrit, and Nir Nissim. Time-interval temporal patterns can beat and explain the malware. Knowledge-Based Systems, 241:108266, 2022. URL: https://doi.org/10.1016/J.KNOSYS.2022.108266.</text> <url>https://doi.org/10.1016/J.KNOSYS.2022.108266</url> </reference> <reference refNo="23"> <text>Frédérick Garcia and Emmanuel Rachelson. Markov decision processes. Markov Decision Processes in Artificial Intelligence, pages 1-38, 2013.</text> <url/> </reference> <reference refNo="24"> <text>Nikos Giatrakos, Elias Alevizos, Alexander Artikis, Antonios Deligiannakis, and Minos Garofalakis. Complex event recognition in the big data era: a survey. The VLDB Journal, 29:313-352, 2020. URL: https://doi.org/10.1007/S00778-019-00557-W.</text> <url>https://doi.org/10.1007/S00778-019-00557-W</url> </reference> <reference refNo="25"> <text>Ben Goertzel, Nil Geisweiller, Lucio Coelho, Predrag Janičić, and Cassio Pennachin. Real-World Reasoning: Toward Scalable, Uncertain Spatiotemporal, Contextual and Causal Inference, volume 2. Springer Science &amp; Business Media, 2011.</text> <url/> </reference> <reference refNo="26"> <text>Shaogang Gong and Tao Xiang. Recognition of group activities using dynamic probabilistic networks. In Proceedings ninth IEEE international conference on computer vision, pages 742-749. IEEE, 2003. URL: https://doi.org/10.1109/ICCV.2003.1238423.</text> <url>https://doi.org/10.1109/ICCV.2003.1238423</url> </reference> <reference refNo="27"> <text>Valentin Goranko, Angelo Montanari, and Guido Sciavicco. A road map of interval temporal logics and duration calculi. Journal of Applied Non-Classical Logics, 14(1-2):9-54, 2004. URL: https://doi.org/10.3166/JANCL.14.9-54.</text> <url>https://doi.org/10.3166/JANCL.14.9-54</url> </reference> <reference refNo="28"> <text>Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv:1502.02259, 2015. URL: https://arxiv.org/abs/1502.02259.</text> <url>https://arxiv.org/abs/1502.02259</url> </reference> <reference refNo="29"> <text>Derek Hao Hu, Sinno Jialin Pan, Vincent Wenchen Zheng, Nathan Nan Liu, and Qiang Yang. Real world activity recognition with multiple goals. In Proceedings of the 10th international conference on Ubiquitous computing, pages 30-39, 2008. URL: https://doi.org/10.1145/1409635.1409640.</text> <url>https://doi.org/10.1145/1409635.1409640</url> </reference> <reference refNo="30"> <text>Frank Höppner. Learning temporal rules from state sequences. In IJCAI Workshop on Learning from Temporal and Spatial Data, volume 25. Citeseer, 2001.</text> <url/> </reference> <reference refNo="31"> <text>Michael Kaminski and Nissim Francez. Finite-memory automata. Theoretical Computer Science, 134(2):329-363, 1994. URL: https://doi.org/10.1016/0304-3975(94)90242-9.</text> <url>https://doi.org/10.1016/0304-3975(94)90242-9</url> </reference> <reference refNo="32"> <text>Nikos Katzouris, Evangelos Michelioudakis, Alexander Artikis, and Georgios Paliouras. Online learning of weighted relational rules for complex event recognition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10-14, 2018, Proceedings, Part II 18, pages 396-413. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-10928-8_24.</text> <url>https://doi.org/10.1007/978-3-030-10928-8_24</url> </reference> <reference refNo="33"> <text>Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual reinforcement learning: A review and perspectives. Journal of Artificial Intelligence Research, 75:1401-1476, 2022. URL: https://doi.org/10.1613/JAIR.1.13673.</text> <url>https://doi.org/10.1613/JAIR.1.13673</url> </reference> <reference refNo="34"> <text>Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michał Zając, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI conference on artificial intelligence, pages 4501-4510, 2020.</text> <url/> </reference> <reference refNo="35"> <text>Niels Landwehr. Modeling interleaved hidden processes. In Proceedings of the 25th international conference on Machine learning, pages 520-527, 2008. URL: https://doi.org/10.1145/1390156.1390222.</text> <url>https://doi.org/10.1145/1390156.1390222</url> </reference> <reference refNo="36"> <text>D Luckham. The power of events: An introduction to complex event processing in distributed enterprise systems. additions-wesley. Reading, 2001.</text> <url/> </reference> <reference refNo="37"> <text>Sultan Javed Majeed and Marcus Hutter. On q-learning convergence for non-markov decision processes. In IJCAI, volume 18, pages 2546-2552, 2018. URL: https://doi.org/10.24963/IJCAI.2018/353.</text> <url>https://doi.org/10.24963/IJCAI.2018/353</url> </reference> <reference refNo="38"> <text>Nijat Mehdiyev, Julian Krumeich, David Enke, Dirk Werth, and Peter Loos. Determination of rule patterns in complex event processing using machine learning techniques. Procedia Computer Science, 61:395-401, 2015. URL: https://doi.org/10.1016/J.PROCS.2015.09.168.</text> <url>https://doi.org/10.1016/J.PROCS.2015.09.168</url> </reference> <reference refNo="39"> <text>Vlad I Morariu and Larry S Davis. Multi-agent event recognition in structured scenarios. In CVPR 2011, pages 3289-3296. IEEE, 2011. URL: https://doi.org/10.1109/CVPR.2011.5995386.</text> <url>https://doi.org/10.1109/CVPR.2011.5995386</url> </reference> <reference refNo="40"> <text>Robert Moskovitch. Multivariate temporal data analysis-a review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(1):e1430, 2022. URL: https://doi.org/10.1002/WIDM.1430.</text> <url>https://doi.org/10.1002/WIDM.1430</url> </reference> <reference refNo="41"> <text>Robert Moskovitch. Mining temporal data. Machine Learning for Data Science Handbook: Data Mining and Knowledge Discovery Handbook, pages 469-490, 2023.</text> <url/> </reference> <reference refNo="42"> <text>Sindhu Padakandla. A survey of reinforcement learning algorithms for dynamically varying environments. ACM Computing Surveys (CSUR), 54(6):1-25, 2021. URL: https://doi.org/10.1145/3459991.</text> <url>https://doi.org/10.1145/3459991</url> </reference> <reference refNo="43"> <text>Carlos F Pfeiffer, Veralia Gabriela Sánchez, and Nils-Olav Skeie. A discrete event oriented framework for a smart house behavior monitor system. In 2016 12th International Conference on Intelligent Environments (IE), pages 119-123. IEEE, 2016. URL: https://doi.org/10.1109/IE.2016.26.</text> <url>https://doi.org/10.1109/IE.2016.26</url> </reference> <reference refNo="44"> <text>Emmanuel Rachelson. Temporal markov decision problems. PhD thesis, Citeseer, 2009.</text> <url/> </reference> <reference refNo="45"> <text>Emmanuel Rachelson, Gauthier Quesnel, Frédérick Garcia, and Patrick Fabiani. A simulation-based approach for solving generalized semi-markov decision processes. In ECAI 2008, pages 583-587. IOS Press, 2008. URL: https://doi.org/10.3233/978-1-58603-891-5-583.</text> <url>https://doi.org/10.3233/978-1-58603-891-5-583</url> </reference> <reference refNo="46"> <text>Matthijs TJ Spaan. Partially observable markov decision processes. In Reinforcement learning: State-of-the-art, pages 387-414. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27645-3_12.</text> <url>https://doi.org/10.1007/978-3-642-27645-3_12</url> </reference> <reference refNo="47"> <text>Richard S Sutton. The quest for a common model of the intelligent decision maker. arXiv preprint arXiv:2202.13252, 2022. URL: https://arxiv.org/abs/2202.13252.</text> <url>https://arxiv.org/abs/2202.13252</url> </reference> <reference refNo="48"> <text>Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.</text> <url/> </reference> <reference refNo="49"> <text>Kevin Tang, Li Fei-Fei, and Daphne Koller. Learning latent temporal structure for complex event detection. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 1250-1257. IEEE, 2012. URL: https://doi.org/10.1109/CVPR.2012.6247808.</text> <url>https://doi.org/10.1109/CVPR.2012.6247808</url> </reference> <reference refNo="50"> <text>Guy Tennenholtz, Nadav Merlis, Lior Shani, Martin Mladenov, and Craig Boutilier. Reinforcement learning with history dependent dynamic contexts. In International Conference on Machine Learning, pages 34011-34053. PMLR, 2023. URL: https://proceedings.mlr.press/v202/tennenholtz23a.html.</text> <url>https://proceedings.mlr.press/v202/tennenholtz23a.html</url> </reference> <reference refNo="51"> <text>Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024.</text> <url/> </reference> <reference refNo="52"> <text>Aashma Uprety and Danda B Rawat. Reinforcement learning for iot security: A comprehensive survey. IEEE Internet of Things Journal, 8(11):8693-8706, 2020. URL: https://doi.org/10.1109/JIOT.2020.3040957.</text> <url>https://doi.org/10.1109/JIOT.2020.3040957</url> </reference> <reference refNo="53"> <text>Antonio Vitale, Alpha Renner, Celine Nauer, Davide Scaramuzza, and Yulia Sandamirskaya. Event-driven vision and control for uavs on a neuromorphic chip. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 103-109. IEEE, 2021. URL: https://doi.org/10.1109/ICRA48506.2021.9560881.</text> <url>https://doi.org/10.1109/ICRA48506.2021.9560881</url> </reference> <reference refNo="54"> <text>Michalis Vrigkas, Christophoros Nikou, and Ioannis A Kakadiaris. A review of human activity recognition methods. Frontiers in Robotics and AI, 2:28, 2015. URL: https://doi.org/10.3389/FROBT.2015.00028.</text> <url>https://doi.org/10.3389/FROBT.2015.00028</url> </reference> <reference refNo="55"> <text>Cuebong Wong, Erfu Yang, Xiu-Tian Yan, and Dongbing Gu. Autonomous robots for harsh environments: a holistic overview of current solutions and ongoing challenges. Systems Science &amp; Control Engineering, 6(1):213-219, 2018.</text> <url/> </reference> <copyright>Ivelina Stoyanova, Nicolas Museux, Sao Mai Nguyen, and David Filliat</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="6"> <title>Extending the Range of Temporal Specifications of the Run-Time Event Calculus</title> <abstract>Composite event recognition (CER) frameworks reason over streams of low-level, symbolic events in order to detect instances of spatio-temporal patterns defining high-level, composite activities. The Event Calculus is a temporal, logical formalism that has been used to define composite activities in CER, while RTEC_{∘} is a formal CER framework that detects composite activities based on their Event Calculus definitions. RTEC_{∘}, however, cannot handle every possible set of Event Calculus definitions for composite activities, limiting the range of CER applications supported by RTEC_{∘}. We propose RTEC_{fl}, an extension of RTEC_{∘} that supports arbitrary composite activity specifications in the Event Calculus. We present the syntax, semantics, reasoning algorithms and time complexity of RTEC_{fl}. Our analysis demonstrates that RTEC_{fl} extends the scope of RTEC_{∘}, supporting every possible set of Event Calculus definitions for composite activities, while maintaining the high reasoning efficiency of RTEC_{∘}.</abstract> <keyword>Event Calculus</keyword> <keyword>temporal pattern matching</keyword> <keyword>composite event recognition</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <pages>6:1-6:14</pages> <category>Regular Paper</category> <funding>This work was supported by the EU-funded CREXDATA project (No 101092749), and partly supported by the University of Piraeus Research Center.</funding> <supplements> <url category="Software" softwareHeritageId="swh:1:dir:71c0e451729b42a4ad25f6e6fad998fe5d35adba;origin=https://github.com/aartikis/rtec;visit=swh:1:snp:f52a8034fad7209f21bdb51333e64125bd50ab57;anchor=swh:1:rev:a6a142d0d1ae83910a0ac44b364fa27b6e78c93b">https://github.com/aartikis/rtec</url> </supplements> <acknowledgements/> <author> <firstName>Periklis</firstName> <lastName>Mantenoglou</lastName> <name>Periklis Mantenoglou</name> <affiliation>National and Kapodistrian University of Athens, Greece</affiliation> <affiliation>NCSR "Demokritos", Athens, Greece</affiliation> <homepageUrl/> <orcid>https://orcid.org/0009-0002-3275-1522</orcid> </author> <author> <firstName>Alexander</firstName> <lastName>Artikis</lastName> <name>Alexander Artikis</name> <affiliation>University of Piraeus, Greece</affiliation> <affiliation>NCSR "Demokritos", Athens, Greece</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-6899-4599</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.6</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Elias Alevizos, Anastasios Skarlatidis, Alexander Artikis, and Georgios Paliouras. Probabilistic complex event recognition: A survey. Commun. ACM, 50(5):71:1-71:31, 2017. URL: https://doi.org/10.1145/3117809.</text> <url>https://doi.org/10.1145/3117809</url> </reference> <reference refNo="2"> <text>Alexander Artikis, Marek J. Sergot, and Georgios Paliouras. A logic programming approach to activity recognition. In EIMM Workshop in MM, pages 3-8, 2010. URL: https://doi.org/10.1145/1877937.1877941.</text> <url>https://doi.org/10.1145/1877937.1877941</url> </reference> <reference refNo="3"> <text>Alexander Artikis, Marek J. Sergot, and Georgios Paliouras. An event calculus for event recognition. IEEE Trans. Knowl. Data Eng., 27(4):895-908, 2015. URL: https://doi.org/10.1109/TKDE.2014.2356476.</text> <url>https://doi.org/10.1109/TKDE.2014.2356476</url> </reference> <reference refNo="4"> <text>Hamid R. Bazoobandi, Harald Beck, and Jacopo Urbani. Expressive stream reasoning with laser. In ISWC, volume 10587, pages 87-103, 2017. URL: https://doi.org/10.1007/978-3-319-68288-4_6.</text> <url>https://doi.org/10.1007/978-3-319-68288-4_6</url> </reference> <reference refNo="5"> <text>Harald Beck, Minh Dao-Tran, and Thomas Eiter. LARS: A logic-based framework for analytic reasoning over streams. Artif. Intell., 261:16-70, 2018. URL: https://doi.org/10.1016/J.ARTINT.2018.04.003.</text> <url>https://doi.org/10.1016/J.ARTINT.2018.04.003</url> </reference> <reference refNo="6"> <text>Harald Beck, Thomas Eiter, and Christian Folie. Ticker: A system for incremental asp-based stream reasoning. Theory Pract. Log. Program., 17(5-6):744-763, 2017. URL: https://doi.org/10.1017/S1471068417000370.</text> <url>https://doi.org/10.1017/S1471068417000370</url> </reference> <reference refNo="7"> <text>Stefano Bragaglia, Federico Chesani, Paola Mello, Marco Montali, and Paolo Torroni. Reactive event calculus for monitoring global computing applications. In Logic Programs, Norms and Action - Essays in Honor of Marek J. Sergot on the Occasion of His 60th Birthday, volume 7360, pages 123-146, 2012. URL: https://doi.org/10.1007/978-3-642-29414-3_8.</text> <url>https://doi.org/10.1007/978-3-642-29414-3_8</url> </reference> <reference refNo="8"> <text>Sebastian Brandt, Elem Güzel Kalayci, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. Querying log data with metric temporal logic. J. Artif. Intell. Res., 62:829-877, 2018. URL: https://doi.org/10.1613/JAIR.1.11229.</text> <url>https://doi.org/10.1613/JAIR.1.11229</url> </reference> <reference refNo="9"> <text>Stefano Bromuri, Visara Urovi, and Kostas Stathis. icampus: A connected campus in the ambient event calculus. Int. J. Ambient Comput. Intell., 2(1):59-65, 2010. URL: https://doi.org/10.4018/JACI.2010010105.</text> <url>https://doi.org/10.4018/JACI.2010010105</url> </reference> <reference refNo="10"> <text>Marco Bucchi, Alejandro Grez, Andrés Quintana, Cristian Riveros, and Stijn Vansummeren. CORE: a complex event recognition engine. Proc. VLDB Endow., 15(9):1951-1964, 2022. URL: https://doi.org/10.14778/3538598.3538615.</text> <url>https://doi.org/10.14778/3538598.3538615</url> </reference> <reference refNo="11"> <text>Francesco Calimeri, Marco Manna, Elena Mastria, Maria Concetta Morelli, Simona Perri, and Jessica Zangari. I-dlv-sr: A stream reasoning system based on I-DLV. Theory Pract. Log. Program., 21(5):610-628, 2021. URL: https://doi.org/10.1017/S147106842100034X.</text> <url>https://doi.org/10.1017/S147106842100034X</url> </reference> <reference refNo="12"> <text>Iliano Cervesato and Angelo Montanari. A calculus of macro-events: Progress report. In TIME, pages 47-58, 2000. URL: https://doi.org/10.1109/TIME.2000.856584.</text> <url>https://doi.org/10.1109/TIME.2000.856584</url> </reference> <reference refNo="13"> <text>Hervé Chaudet. Extending the event calculus for tracking epidemic spread. Artif. Intell. Medicine, 38(2):137-156, 2006. URL: https://doi.org/10.1016/J.ARTMED.2005.06.001.</text> <url>https://doi.org/10.1016/J.ARTMED.2005.06.001</url> </reference> <reference refNo="14"> <text>L. Chittaro and A. Montanari. Efficient temporal reasoning in the cached event calculus. Comput. Intell., 12(3):359-382, 1996. URL: https://doi.org/10.1111/J.1467-8640.1996.TB00267.X.</text> <url>https://doi.org/10.1111/J.1467-8640.1996.TB00267.X</url> </reference> <reference refNo="15"> <text>Keith L. Clark. Negation as failure. In Logic and Data Bases, pages 293-322. Plemum Press, 1977. URL: https://doi.org/10.1007/978-1-4684-3384-5_11.</text> <url>https://doi.org/10.1007/978-1-4684-3384-5_11</url> </reference> <reference refNo="16"> <text>Gianpaolo Cugola and Alessandro Margara. Processing flows of information: From data stream to complex event processing. ACM Comput. Surv., 44(3), 2012. URL: https://doi.org/10.1145/2187671.2187677.</text> <url>https://doi.org/10.1145/2187671.2187677</url> </reference> <reference refNo="17"> <text>C. Dousson and P. Le Maigat. Chronicle recognition improvement using temporal focusing and hierarchisation. In IJCAI, pages 324-329, 2007.</text> <url/> </reference> <reference refNo="18"> <text>Thomas Eiter, Paul Ogris, and Konstantin Schekotihin. A distributed approach to LARS stream reasoning (system paper). Theory Pract. Log. Program., 19(5-6):974-989, 2019. URL: https://doi.org/10.1017/S1471068419000309.</text> <url>https://doi.org/10.1017/S1471068419000309</url> </reference> <reference refNo="19"> <text>Nicola Falcionelli, Paolo Sernani, Albert Brugués de la Torre, Dagmawi Neway Mekuria, Davide Calvaresi, Michael Schumacher, Aldo Franco Dragoni, and Stefano Bromuri. Indexing the event calculus: Towards practical human-readable personal health systems. Artif. Intell. Medicine, 96:154-166, 2019. URL: https://doi.org/10.1016/J.ARTMED.2018.10.003.</text> <url>https://doi.org/10.1016/J.ARTMED.2018.10.003</url> </reference> <reference refNo="20"> <text>Nikos Giatrakos, Elias Alevizos, Alexander Artikis, Antonios Deligiannakis, and Minos N. Garofalakis. Complex event recognition in the big data era: a survey. VLDB J., 29(1):313-352, 2020. URL: https://doi.org/10.1007/S00778-019-00557-W.</text> <url>https://doi.org/10.1007/S00778-019-00557-W</url> </reference> <reference refNo="21"> <text>Alejandro Grez, Cristian Riveros, Martín Ugarte, and Stijn Vansummeren. A formal framework for complex event recognition. ACM Trans. Database Syst., 46(4):16:1-16:49, 2021. URL: https://doi.org/10.1145/3485463.</text> <url>https://doi.org/10.1145/3485463</url> </reference> <reference refNo="22"> <text>Özgür Kafali, Alfonso E. Romero, and Kostas Stathis. Agent-oriented activity recognition in the event calculus: An application for diabetic patients. Comput. Intell., 33(4):899-925, 2017. URL: https://doi.org/10.1111/COIN.12121.</text> <url>https://doi.org/10.1111/COIN.12121</url> </reference> <reference refNo="23"> <text>Nikos Katzouris, Georgios Paliouras, and Alexander Artikis. Online learning probabilistic event calculus theories in answer set programming. Theory Pract. Log. Program., 23(2):362-386, 2023. URL: https://doi.org/10.1017/S1471068421000107.</text> <url>https://doi.org/10.1017/S1471068421000107</url> </reference> <reference refNo="24"> <text>Robert A. Kowalski and Marek J. Sergot. A logic-based calculus of events. New Gener. Comput., 4(1):67-95, 1986. URL: https://doi.org/10.1007/BF03037383.</text> <url>https://doi.org/10.1007/BF03037383</url> </reference> <reference refNo="25"> <text>Periklis Mantenoglou, Dimitrios Kelesis, and Alexander Artikis. Complex event recognition with allen relations. In KR, pages 502-511, 2023. URL: https://doi.org/10.24963/KR.2023/49.</text> <url>https://doi.org/10.24963/KR.2023/49</url> </reference> <reference refNo="26"> <text>Periklis Mantenoglou, Manolis Pitsikalis, and Alexander Artikis. Stream reasoning with cycles. In KR, pages 544-553, 2022.</text> <url/> </reference> <reference refNo="27"> <text>Adrian Paschke. Eca-ruleml: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics. CoRR, abs/cs/0610167, 2006.</text> <url/> </reference> <reference refNo="28"> <text>Adrian Paschke and Martin Bichler. Knowledge representation concepts for automated SLA management. Decis. Support Syst., 46(1):187-205, 2008. URL: https://doi.org/10.1016/J.DSS.2008.06.008.</text> <url>https://doi.org/10.1016/J.DSS.2008.06.008</url> </reference> <reference refNo="29"> <text>Kostas Patroumpas, Alexander Artikis, Nikos Katzouris, Marios Vodas, Yannis Theodoridis, and Nikos Pelekis. Event recognition for maritime surveillance. In EDBT, pages 629-640, 2015. URL: https://doi.org/10.5441/002/EDBT.2015.63.</text> <url>https://doi.org/10.5441/002/EDBT.2015.63</url> </reference> <reference refNo="30"> <text>Manolis Pitsikalis, Alexander Artikis, Richard Dreo, Cyril Ray, Elena Camossi, and Anne-Laure Jousselme. Composite event recognition for maritime monitoring. In DEBS, pages 163-174, 2019. URL: https://doi.org/10.1145/3328905.3329762.</text> <url>https://doi.org/10.1145/3328905.3329762</url> </reference> <reference refNo="31"> <text>J. Pitt, L. Kamara, M. Sergot, and A. Artikis. Voting in multi-agent systems. Comput. J., 49(2):156-170, 2006. URL: https://doi.org/10.1093/COMJNL/BXH164.</text> <url>https://doi.org/10.1093/COMJNL/BXH164</url> </reference> <reference refNo="32"> <text>Olga Poppe, Chuan Lei, Elke A. Rundensteiner, and David Maier. Event trend aggregation under rich event matching semantics. In SIGMOD, pages 555-572, 2019. URL: https://doi.org/10.1145/3299869.3319862.</text> <url>https://doi.org/10.1145/3299869.3319862</url> </reference> <reference refNo="33"> <text>Teodor C. Przymusinski. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming, pages 193-216. Morgan Kaufmann, 1988. URL: https://doi.org/10.1016/B978-0-934613-40-8.50009-9.</text> <url>https://doi.org/10.1016/B978-0-934613-40-8.50009-9</url> </reference> <reference refNo="34"> <text>Nausheen Saba Shahid, Dan O'Keeffe, and Kostas Stathis. A knowledge representation framework for evolutionary simulations with cognitive agents. In ICTAI, pages 361-368. IEEE, 2023. URL: https://doi.org/10.1109/ICTAI59109.2023.00059.</text> <url>https://doi.org/10.1109/ICTAI59109.2023.00059</url> </reference> <reference refNo="35"> <text>M. Sirbu. Credits and debits on the Internet. IEEE Spectrum, 34(2):23-29, 1997.</text> <url/> </reference> <reference refNo="36"> <text>Efthimis Tsilionis, Alexander Artikis, and Georgios Paliouras. Incremental event calculus for run-time reasoning. J. Artif. Intell. Res., 73:967-1023, 2022. URL: https://doi.org/10.1613/JAIR.1.12695.</text> <url>https://doi.org/10.1613/JAIR.1.12695</url> </reference> <reference refNo="37"> <text>Przemyslaw Andrzej Walega, Mark Kaminski, and Bernardo Cuenca Grau. Reasoning over streaming data in metric temporal datalog. In AAAI, pages 3092-3099, 2019. URL: https://doi.org/10.1609/AAAI.V33I01.33013092.</text> <url>https://doi.org/10.1609/AAAI.V33I01.33013092</url> </reference> <reference refNo="38"> <text>Przemyslaw Andrzej Walega, Mark Kaminski, Dingmin Wang, and Bernardo Cuenca Grau. Stream reasoning with datalogmtl. J. Web Semant., 76:100776, 2023. URL: https://doi.org/10.1016/J.WEBSEM.2023.100776.</text> <url>https://doi.org/10.1016/J.WEBSEM.2023.100776</url> </reference> <reference refNo="39"> <text>Bo Zhao, Han van der Aa, Thanh Tam Nguyen, Quoc Viet Hung Nguyen, and Matthias Weidlich. EIRES: efficient integration of remote data in event stream processing. In SIGMOD, pages 2128-2141, 2021. URL: https://doi.org/10.1145/3448016.3457304.</text> <url>https://doi.org/10.1145/3448016.3457304</url> </reference> <reference refNo="40"> <text>Bartosz Zielinski. Explanatory denotational semantics for complex event patterns. Formal Aspects Comput., 35(4):23:1-23:37, 2023. URL: https://doi.org/10.1145/3608486.</text> <url>https://doi.org/10.1145/3608486</url> </reference> <copyright>Periklis Mantenoglou and Alexander Artikis</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="7"> <title>Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation</title> <abstract>Many-valued logics, often referred to as fuzzy logics, are a fundamental tool for reasoning about uncertainty, and are based on truth value algebras that generalize the Boolean one; the same logic can be interpreted on algebras from different varieties, for different purposes and pose different challenges. Although temporal many-valued logics, that is, the many-valued counterpart of popular temporal logics, have received little attention in the literature, the many-valued generalization of Halpern and Shoham’s interval temporal logic has been recently introduced and studied, and a sound and complete tableau system for it has been presented for the case in which it is interpreted on some finite Heyting algebra. In this paper, we take a step further in this inquiry by exploring a tableau system for Halpern and Shoham’s interval temporal logic interpreted on some finite {FL_{ew}}-algebra, therefore generalizing the Heyting case, and by providing its open-source implementation.</abstract> <keyword>Interval temporal logic</keyword> <keyword>many-valued logic</keyword> <keyword>tableau system</keyword> <subjectClassification acmID="10003752.10010070">Theory of computation~Theory and algorithms for application domains</subjectClassification> <pages>7:1-7:16</pages> <category>Regular Paper</category> <funding>This research has been partially funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI", funded by the European Union under the "NextGeneration EU programme". Moreover, this research has also been founded by the FIRD project Modal Geometric Symbolic Learning (University of Ferrara), and the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (INDAM-GNCS) project Symbolic and Numerical Analysis of Cyberphysical Systems, CUP code E53C22001930001. Guido Sciavicco and Ionel Eduard Stan are GNCS-INdAM members; Carles Noguera is a GNSAGA-INdAM member.</funding> <acknowledgements/> <author> <firstName>Guillermo</firstName> <lastName>Badia</lastName> <name>Guillermo Badia</name> <affiliation>School of Historical and Philosophical Inquiry, University of Queensland, Brisbane, Australia</affiliation> <homepageUrl>https://sites.google.com/site/guillermobadialogic</homepageUrl> <orcid>https://orcid.org/0000-0003-2795-3728</orcid> </author> <author> <firstName>Carles</firstName> <lastName>Noguera</lastName> <name>Carles Noguera</name> <affiliation>Department of Information Engineering and Mathematics, University of Siena, Italy</affiliation> <homepageUrl>https://docenti.unisi.it/en/noguera-clofent</homepageUrl> <orcid>https://orcid.org/0000-0003-4910-599X</orcid> </author> <author> <firstName>Alberto</firstName> <lastName>Paparella</lastName> <name>Alberto Paparella</name> <affiliation>Department of Mathematics and Computer Science, University of Ferrara, Italy</affiliation> <homepageUrl>https://alberto-paparella.github.io/</homepageUrl> <orcid>https://orcid.org/0009-0007-1653-3660</orcid> </author> <author> <firstName>Guido</firstName> <lastName>Sciavicco</lastName> <name>Guido Sciavicco</name> <affiliation>Department of Mathematics and Computer Science, University of Ferrara, Italy</affiliation> <homepageUrl>https://sites.google.com/unife.it/guido/</homepageUrl> <orcid>https://orcid.org/0000-0002-9221-879X</orcid> </author> <author> <firstName>Ionel Eduard</firstName> <lastName>Stan</lastName> <name>Ionel Eduard Stan</name> <affiliation>Faculty of Engineering, Free University of Bozen-Bolzano, Italy</affiliation> <homepageUrl>https://eduardstan.github.io/</homepageUrl> <orcid>https://orcid.org/0000-0001-9260-102X</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.7</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>J. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832-843, 1983. URL: https://doi.org/10.1145/182.358434.</text> <url>https://doi.org/10.1145/182.358434</url> </reference> <reference refNo="2"> <text>M. Baaz, N. Preining, and R. Zach. First-order Gödel logics. Annals of Pure and Applied Logic, 147:23-47, 2007. URL: https://doi.org/10.1016/J.APAL.2007.03.001.</text> <url>https://doi.org/10.1016/J.APAL.2007.03.001</url> </reference> <reference refNo="3"> <text>U. Bodenhofer. Representations and constructions of similarity-based fuzzy orderings. Fuzzy Sets and Systems, 137(1):113-136, 2003. URL: https://doi.org/10.1016/S0165-0114(02)00436-0.</text> <url>https://doi.org/10.1016/S0165-0114(02)00436-0</url> </reference> <reference refNo="4"> <text>G. E. Brancati, E. Vieta, J. M. Azorin, J. Angst, C. L. Bowden, S. Mosolov, A. H. Young, and G. Perugi. The role of overlapping excitatory symptoms in major depression: are they relevant for the diagnosis of mixed state? Journal of Psychiatric Research, 115:151-157, 2019.</text> <url/> </reference> <reference refNo="5"> <text>D. Bresolin, D. Della Monica, A. Montanari, and G. Sciavicco. A tableau system for right propositional neighborhood logic over finite linear orders: An implementation. In Proc. of the 22th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX), volume 8123 of LNCS, pages 74-80. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40537-2_8.</text> <url>https://doi.org/10.1007/978-3-642-40537-2_8</url> </reference> <reference refNo="6"> <text>A. Brunello, G. Sciavicco, and I. E. Stan. Interval temporal logic decision tree learning. In Proceedings of the 16th European Conference on Logics in Artificial Intelligence (JELIA), volume 11468 of LNCS, pages 778-793. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-19570-0_50.</text> <url>https://doi.org/10.1007/978-3-030-19570-0_50</url> </reference> <reference refNo="7"> <text>J. J. Buckley and Y. Hayashi. Fuzzy neural networks: A survey. Fuzzy Sets and Systems, 66:1-13, 1994.</text> <url/> </reference> <reference refNo="8"> <text>C. C. Chang. Algebraic analysis of many valued logics. Transactions of the American Mathematical society, 88(2):467-490, 1958.</text> <url/> </reference> <reference refNo="9"> <text>Y. Chen, T. Wang, B. Wang, and Z. Li. A survey of fuzzy decision tree classifier. Fuzzy Information and Engineering, 1(2):149-159, 2009.</text> <url/> </reference> <reference refNo="10"> <text>P. Cintula, P. Hájek, and C. Noguera, editors. Handbook of Mathematical Fuzzy Logic, volume 37-38 of Studies in Logic. Mathematical Logic and Foundation. College publications, 2011.</text> <url/> </reference> <reference refNo="11"> <text>W. Conradie, D. Della Monica, E. Muñoz-Velasco, and G. Sciavicco. An approach to fuzzy modal logic of time intervals. In Proc. of the 24th European Conference on Artificial Intelligence (ECAI), volume 325 of FAIA, pages 696-703. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200156.</text> <url>https://doi.org/10.3233/FAIA200156</url> </reference> <reference refNo="12"> <text>W. Conradie, D. Della Monica, E. Muñoz-Velasco, G. Sciavicco, and I. E. Stan. Fuzzy Halpern and Shoham’s interval temporal logics. Fuzzy Sets and Systems, 456:107-124, 2023. URL: https://doi.org/10.1016/J.FSS.2022.05.014.</text> <url>https://doi.org/10.1016/J.FSS.2022.05.014</url> </reference> <reference refNo="13"> <text>W. Conradie, R. Monego, E. Muñoz-Velasco, G. Sciavicco, and I. E. Stan. A sound and complete tableau system for fuzzy Halpern and Shoham’s interval temporal logic. In Proc. of the 30th International Symposium on Temporal Representation and Reasoning (TIME), volume 278 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl, 2023. URL: https://doi.org/10.4230/LIPICS.TIME.2023.9.</text> <url>https://doi.org/10.4230/LIPICS.TIME.2023.9</url> </reference> <reference refNo="14"> <text>S. Dutta. An event based fuzzy temporal logic. In Proc. of the 18th International Symposium on Multiple-Valued Logic, pages 64-71, 1988.</text> <url/> </reference> <reference refNo="15"> <text>L. Esakia, G. Bezhanishvili, W. H. Holliday, and A. Evseev. Heyting Algebras: Duality Theory. Springer, 2019.</text> <url/> </reference> <reference refNo="16"> <text>M. Fitting. Many-valued modal logics. Fundamenta Informaticae, 15(3-4):235-254, 1991.</text> <url/> </reference> <reference refNo="17"> <text>M. Fitting. Tableaus for many-valued modal logic. Studia Logica, 55(1):63-87, 1995. URL: https://doi.org/10.1007/BF01053032.</text> <url>https://doi.org/10.1007/BF01053032</url> </reference> <reference refNo="18"> <text>A. Frigeri, L. Pasquale, and P. Spoletini. Fuzzy time in linear temporal logic. ACM Transactions on Computational Logic, 15:1-22, 2014. URL: https://doi.org/10.1145/2629606.</text> <url>https://doi.org/10.1145/2629606</url> </reference> <reference refNo="19"> <text>V. Goranko, A. Montanari, P. Sala, and G. Sciavicco. A general tableau method for propositional interval temporal logics: Theory and implementation. Journal of Applied Logics, 4(3):305-330, 2006. URL: https://doi.org/10.1016/J.JAL.2005.06.012.</text> <url>https://doi.org/10.1016/J.JAL.2005.06.012</url> </reference> <reference refNo="20"> <text>V. Goranko, A. Montanari, and G. Sciavicco. Propositional interval neighborhood temporal logics. Journal of Universal Computer Science, 9(9):1137-1167, 2003. URL: https://doi.org/10.3217/JUCS-009-09-1137.</text> <url>https://doi.org/10.3217/JUCS-009-09-1137</url> </reference> <reference refNo="21"> <text>V. Goranko, A. Montanari, and G. Sciavicco. A road map of interval temporal logics and duration calculi. Journal of Applied Non-Classical Logics, 14(1-2):9-54, 2004. URL: https://doi.org/10.3166/JANCL.14.9-54.</text> <url>https://doi.org/10.3166/JANCL.14.9-54</url> </reference> <reference refNo="22"> <text>P. Hájek. The Metamathematics of Fuzzy Logic. Kluwer, 1998.</text> <url/> </reference> <reference refNo="23"> <text>J. Y. Halpern and Y. Shoham. A Propositional Modal Logic of Time Intervals. Journal of the ACM, 38(4):935-962, 1991. URL: https://doi.org/10.1145/115234.115351.</text> <url>https://doi.org/10.1145/115234.115351</url> </reference> <reference refNo="24"> <text>L. I. Kuncheva. Fuzzy Classifier Design, volume 49 of Studies in Fuzziness and Soft Computing. Springer, 2000. URL: https://doi.org/10.1007/978-3-7908-1850-5.</text> <url>https://doi.org/10.1007/978-3-7908-1850-5</url> </reference> <reference refNo="25"> <text>S. Kundu. Similarity relations, fuzzy linear orders, and fuzzy partial orders. Fuzzy Sets and Systems, 109(3):419-428, 2000. URL: https://doi.org/10.1016/S0165-0114(97)00370-9.</text> <url>https://doi.org/10.1016/S0165-0114(97)00370-9</url> </reference> <reference refNo="26"> <text>K. B. Lamine and F. Kabanza. Using fuzzy temporal logic for monitoring behavior-based mobile robots. In Proc. of the IASTED International Conference, Robotics and Applications, pages 116-121, 2000.</text> <url/> </reference> <reference refNo="27"> <text>F. Manzella, G. Pagliarini, A. Paparella, G. Sciavicco, and I. E. Stan. Sole.jl - Symbolic Learning in Julia. https://github.com/aclai-lab/Sole.jl, 2024.</text> <url>https://github.com/aclai-lab/Sole.jl</url> </reference> <reference refNo="28"> <text>F. Manzella, G. Pagliarini, G. Sciavicco, and I. E. Stan. Interval Temporal Random Forests with an Application to COVID-19 Diagnosis. In Proceedings of the 28th International Symposium on Temporal Representation and Reasoning (TIME), volume 206 of LIPIcs, pages 7:1-7:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPICS.TIME.2021.7.</text> <url>https://doi.org/10.4230/LIPICS.TIME.2021.7</url> </reference> <reference refNo="29"> <text>E. Muñoz-Velasco, M. Pelegrín-Garcí, P. Sala, G. Sciavicco, and I. E. Stan. On coarser interval temporal logics. Artificial Intelligence, 266:1-26, 2019. URL: https://doi.org/10.1016/J.ARTINT.2018.09.001.</text> <url>https://doi.org/10.1016/J.ARTINT.2018.09.001</url> </reference> <reference refNo="30"> <text>S. Ovchinnikov. Similarity relations, fuzzy partitions, and fuzzy orderings. Fuzzy Sets and Systems, 40(1):107-126, 1991.</text> <url/> </reference> <reference refNo="31"> <text>A. Rose. Formalisations of further ℵ₀-valued Łukasiewicz propositional calculi. Journal of Symbolic Logic, 43(2):207-210, 1978. URL: https://doi.org/10.2307/2272818.</text> <url>https://doi.org/10.2307/2272818</url> </reference> <reference refNo="32"> <text>G. Sciavicco and I. E. Stan. Knowledge extraction with interval temporal logic decision trees. In Proceedings of the 27th International Symposium on Temporal Representation and Reasoning (TIME), volume 178 of LIPIcs, pages 9:1-9:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPICS.TIME.2020.9.</text> <url>https://doi.org/10.4230/LIPICS.TIME.2020.9</url> </reference> <reference refNo="33"> <text>H. Thiele and S. Kalenka. On fuzzy temporal logic. In Proc. of the 2nd International Conference on Fuzzy Systems, pages 1027-1032. IEEE, 1993.</text> <url/> </reference> <reference refNo="34"> <text>L. A. Zadeh. Similarity relations and fuzzy orderings. Information Sciences, 3(2):177-200, 1971. URL: https://doi.org/10.1016/S0020-0255(71)80005-1.</text> <url>https://doi.org/10.1016/S0020-0255(71)80005-1</url> </reference> <copyright>Guillermo Badia, Carles Noguera, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="8"> <title>A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty</title> <abstract>Simple Temporal Networks with Uncertainty (STNU) are a well-known constraint-based model expressing sets of activities (e.g., a schedule or a plan) related by temporal constraints, each having possible durations in the form of convex intervals. Uncertainty comes from some of these durations being contingent, i.e., the agent executing the plan cannot decide the actual duration at execution time. To check that execution will satisfy all the constraints, three levels of controllability exist: the Strong and Dynamic Controllability (SC/DC) has proven both useful in practice and provable in polynomial time, while Weak Controllability (WC) is co-NP-complete and has been left aside. Moreover, controllability checking algorithms are propagation strategies, which have the usual drawback, in case of failure, to prove unable to locate the contingents that explain the source of non-controllability. This paper has three contributions: (1) it substantiates the usefulness of WC in multi-agent systems (MAS) where another agent controls a contingent, and agents agree just before execution on the durations; (2) it provides a new WC-checking algorithm whose performance in practice depends on the network structure and is faster in loosely connected ones; (3) it provides the failing cycles in the network that explain non-WC.</abstract> <keyword>Temporal constraints satisfaction</keyword> <keyword>uncertainty</keyword> <keyword>STNU</keyword> <keyword>Controllability checking</keyword> <keyword>Explainable inconsistency</keyword> <keyword>Multi-agent planning</keyword> <subjectClassification acmID="10010147">Computing methodologies</subjectClassification> <pages>8:1-8:15</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Ajdin</firstName> <lastName>Sumic</lastName> <name>Ajdin Sumic</name> <affiliation>Technological University of Tarbes, France</affiliation> <homepageUrl/> <orcid/> </author> <author> <firstName>Thierry</firstName> <lastName>Vidal</lastName> <name>Thierry Vidal</name> <affiliation>Technological University of Tarbes, France</affiliation> <homepageUrl/> <orcid/> </author> <doi>10.4230/LIPIcs.TIME.2024.8</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Shyan Akmal, Savana Ammons, Hemeng Li, and James C Boerkoel Jr. Quantifying degrees of controllability in temporal networks with uncertainty. In Proceedings of the International Conference on Automated Planning and Scheduling, 2019.</text> <url/> </reference> <reference refNo="2"> <text>Shyan Akmal, Savana Ammons, Hemeng Li, Michael Gao, Lindsay Popowski, and James C. Boerkoel. Quantifying controllability in temporal networks with uncertainty. Artificial Intelligence, 2020.</text> <url/> </reference> <reference refNo="3"> <text>Arthur Bit-Monnot and Paul Morris. Dynamic controllability of temporal plans in uncertain and partially observable environments. J. Artif. Intell. Res., 2023. URL: https://doi.org/10.1613/JAIR.1.13065.</text> <url>https://doi.org/10.1613/JAIR.1.13065</url> </reference> <reference refNo="4"> <text>Alessandro Cimatti, Andrea Micheli, and Marco Roveri. Solving temporal problems using smt: weak controllability. In Proceedings of the AAAI Conference on Artificial Intelligence, 2012.</text> <url/> </reference> <reference refNo="5"> <text>Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 1991.</text> <url/> </reference> <reference refNo="6"> <text>Malik Ghallab and A. Mounir Alaoui. Managing efficiently temporal relations through indexed spanning trees. In Proceedings of the 11th International Joint Conference on Artificial Intelligence. Detroit, MI, USA, August 1989, pages 1297-1303. Morgan Kaufmann, 1989. URL: http://ijcai.org/Proceedings/89-2/Papers/072.pdf.</text> <url>http://ijcai.org/Proceedings/89-2/Papers/072.pdf</url> </reference> <reference refNo="7"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the rul dynamic-controllability-checking algorithm for simple temporal networks with uncertainty. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.</text> <url/> </reference> <reference refNo="8"> <text>Jsen-Shung Lin, Chin-Chia Jane, and John Yuan. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 1995. URL: https://doi.org/10.1002/NET.3230250306.</text> <url>https://doi.org/10.1002/NET.3230250306</url> </reference> <reference refNo="9"> <text>Josef Lubas, Marco Franceschetti, and Johann Eder. Resolving conflicts in process models with temporal constraints. In Proceedings of the ER Forum and PhD Symposium, 2022.</text> <url/> </reference> <reference refNo="10"> <text>Paul Morris. A structural characterization of temporal dynamic controllability. In Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings, volume 4204 of Lecture Notes in Computer Science, pages 375-389. Springer, 2006. URL: https://doi.org/10.1007/11889205_28.</text> <url>https://doi.org/10.1007/11889205_28</url> </reference> <reference refNo="11"> <text>Paul Morris. Dynamic controllability and dispatchability relationships. In Integration of AI and OR Techniques in Constraint Programming - 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07046-9_33.</text> <url>https://doi.org/10.1007/978-3-319-07046-9_33</url> </reference> <reference refNo="12"> <text>Paul H. Morris and Nicola Muscettola. Managing temporal uncertainty through waypoint controllability. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages, pages 1253-1258. Morgan Kaufmann, 1999. URL: http://ijcai.org/Proceedings/99-2/Papers/083.pdf.</text> <url>http://ijcai.org/Proceedings/99-2/Papers/083.pdf</url> </reference> <reference refNo="13"> <text>Ajdin Sumic, Alessandro Cimatti, Andrea Micheli, and Thierry Vidal. SMT-based repair of disjunctive temporal networks with uncertainty: Strong and weak controllability. In Proceedings of the The 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2024), 2024.</text> <url/> </reference> <reference refNo="14"> <text>Thierry Vidal and Hélène Fargier. Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell., 11(1):23-45, 1999. URL: https://doi.org/10.1080/095281399146607.</text> <url>https://doi.org/10.1080/095281399146607</url> </reference> <copyright>Ajdin Sumic and Thierry Vidal</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="9"> <title>A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty</title> <abstract>Temporal constraint networks are data structures for representing and reasoning about time (e.g., temporal constraints among actions in a plan). Finding and computing negative cycles in temporal networks is important for planning and scheduling applications since it is the first step toward resolving inconsistent networks. For Simple Temporal Networks (STNs), the problem reduces to finding simple negative cycles (i.e., no repeat nodes), resulting in numerous efficient algorithms. For Simple Temporal Networks with Uncertainty (STNUs), which accommodate actions with uncertain durations, the situation is more complex because the characteristic of a non-dynamically controllable (non-DC) network is a so-called semi-reducible negative (SRN) cycle, which can have repeat edges and, in the worst case, an exponential number of occurrences of such edges. Algorithms for computing SRN cycles in non-DC STNUs that have been presented so far are based on older, less efficient DC-checking algorithms. In addition, the issue of repeated edges has either been ignored or given scant attention. This paper presents a new, faster algorithm for identifying SRN cycles in non-DC STNUs. Its worst-case time complexity is O(mn + k²n + knlog n), where n is the number of timepoints, m is the number of constraints, and k is the number of actions with uncertain durations. This complexity is the same as that of the fastest DC-checking algorithm for STNUs. It avoids an exponential blow-up by efficiently dealing with repeated structures and outputting a compact representation of the SRN cycle it finds. The space required to compactly store accumulated path information while avoiding redundant storage of repeated edges is O(mk + k²n). An empirical evaluation demonstrates the effectiveness of the new algorithm on an existing benchmark.</abstract> <keyword>Temporal constraint networks</keyword> <keyword>overconstrained networks</keyword> <keyword>negative cycles</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <subjectClassification acmID="10003752.10003809.10003635.10010038">Theory of computation~Dynamic graph algorithms</subjectClassification> <pages>9:1-9:15</pages> <category>Regular Paper</category> <supplements> <url category="Software" subCategory="Source code">https://profs.scienze.univr.it/~posenato/software/cstnu/</url> </supplements> <acknowledgements/> <author> <firstName>Luke</firstName> <lastName>Hunsberger</lastName> <name>Luke Hunsberger</name> <affiliation>Vassar College, Poughkeepsie, NY, USA</affiliation> <homepageUrl>https://www.cs.vassar.edu/~hunsberg</homepageUrl> <orcid>https://orcid.org/0009-0005-8603-4803</orcid> </author> <author> <firstName>Roberto</firstName> <lastName>Posenato</lastName> <name>Roberto Posenato</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl>https://www.di.univr.it/?ent=persona&amp;id=102</homepageUrl> <orcid>https://orcid.org/0000-0003-0944-0419</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.9</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Shyan Akmal, Savanna Ammons, Hemeng Li, and James C. Boerkoel, Jr. Quantifying degrees of controllability in temporal networks with uncertainty. In 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), pages 22-30, 2019. URL: https://ojs.aaai.org/index.php/ICAPS/article/view/3456, URL: https://doi.org/10.1609/icaps.v29i1.3456.</text> <url>https://doi.org/10.1609/icaps.v29i1.3456</url> </reference> <reference refNo="2"> <text>Nikhil Bhargava, Tiago Vaquero, and Brian C. Williams. Faster conflict generation for dynamic controllability. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17), pages 4280-4286, 2017. URL: https://doi.org/10.24963/ijcai.2017/598.</text> <url>https://doi.org/10.24963/ijcai.2017/598</url> </reference> <reference refNo="3"> <text>Massimo Cairo, Luke Hunsberger, and Romeo Rizzi. Faster Dynamic Controllablity Checking for Simple Temporal Networks with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME-2018), volume 120 of LIPIcs, pages 8:1-8:16, 2018. URL: https://doi.org/10.4230/LIPIcs.TIME.2018.8.</text> <url>https://doi.org/10.4230/LIPIcs.TIME.2018.8</url> </reference> <reference refNo="4"> <text>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022. URL: https://mitpress.mit.edu/9780262046305/introduction-to- algorithms.</text> <url>https://mitpress.mit.edu/9780262046305/introduction-to- algorithms</url> </reference> <reference refNo="5"> <text>Johann Eder, Marco Franceschetti, and Josef Lubas. Dynamic Controllability of Processes without Surprises. Applied Sciences, 12(3):1461, January 2022. URL: https://doi.org/10.3390/app12031461.</text> <url>https://doi.org/10.3390/app12031461</url> </reference> <reference refNo="6"> <text>Cheng Fang, Andrew J. Wang, and Brian C. Williams. Chance-constrained Static Schedules for Temporally Probabilistic Plans. Journal of Artificial Intelligence Research, 75:1323-1372, 2022. URL: https://doi.org/10.1613/jair.1.13636.</text> <url>https://doi.org/10.1613/jair.1.13636</url> </reference> <reference refNo="7"> <text>Luke Hunsberger. Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In 16th International Symposium on Temporal Representation and Reasoning (TIME-2009), pages 155-162, 2009. URL: https://doi.org/10.1109/TIME.2009.25.</text> <url>https://doi.org/10.1109/TIME.2009.25</url> </reference> <reference refNo="8"> <text>Luke Hunsberger. Magic Loops in Simple Temporal Networks with Uncertainty-Exploiting Structure to Speed Up Dynamic Controllability Checking. In 5th International Conference on Agents and Artificial Intelligence (ICAART-2013), volume 2, pages 157-170, 2013. URL: https://doi.org/10.5220/0004260501570170.</text> <url>https://doi.org/10.5220/0004260501570170</url> </reference> <reference refNo="9"> <text>Luke Hunsberger. Magic Loops and the Dynamic Controllability of Simple Temporal Networks with Uncertainty. In Joaquim Filipe and Ana Fred, editors, Agents and Artificial Intelligence, volume 449 of Communications in Computer and Information Science (CCIS), pages 332-350, 2014. URL: https://doi.org/10.1007/978-3-662-44440-5_20.</text> <url>https://doi.org/10.1007/978-3-662-44440-5_20</url> </reference> <reference refNo="10"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the RUL^- Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty. In 36th AAAI Conference on Artificial Intelligence (AAAI-22), volume 36-9, pages 9776-9785. AAAI Pres, 2022. URL: https://doi.org/10.1609/aaai.v36i9.21213.</text> <url>https://doi.org/10.1609/aaai.v36i9.21213</url> </reference> <reference refNo="11"> <text>Erez Karpas, Steven J. Levine, Peng Yu, and Brian C. Williams. Robust Execution of Plans for Human-Robot Teams. In 25th Int. Conf. on Automated Planning and Scheduling (ICAPS-15), volume 25, pages 342-346, 2015. URL: https://doi.org/10.1609/icaps.v25i1.13698.</text> <url>https://doi.org/10.1609/icaps.v25i1.13698</url> </reference> <reference refNo="12"> <text>Paul Morris. A Structural Characterization of Temporal Dynamic Controllability. In Principles and Practice of Constraint Programming (CP-2006), volume 4204, pages 375-389, 2006. URL: https://doi.org/10.1007/11889205_28.</text> <url>https://doi.org/10.1007/11889205_28</url> </reference> <reference refNo="13"> <text>Paul Morris. Dynamic controllability and dispatchability relationships. In Int. Conf. on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR-2014), volume 8451 of LNCS, pages 464-479. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07046-9_33.</text> <url>https://doi.org/10.1007/978-3-319-07046-9_33</url> </reference> <reference refNo="14"> <text>Paul Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In 17th Int. Joint Conf. on Artificial Intelligence (IJCAI-2001), volume 1, pages 494-499, 2001. URL: https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf.</text> <url>https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf</url> </reference> <reference refNo="15"> <text>Jun Peng, Jingwei Zhu, and Liang Zhang. Generalizing STNU to Model Non-functional Constraints for Business Processes. In 2022 International Conference on Service Science (ICSS), pages 104-111. IEEE, May 2022. URL: https://doi.org/10.1109/ICSS55994.2022.00024.</text> <url>https://doi.org/10.1109/ICSS55994.2022.00024</url> </reference> <reference refNo="16"> <text>Roberto Posenato. STNU Benchmark version 2020, 2020. Last access 2022-12-01. URL: https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html.</text> <url>https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html</url> </reference> <reference refNo="17"> <text>Roberto Posenato. CSTNU Tool: A Java library for checking temporal networks. SoftwareX, 17:100905, 2022. URL: https://doi.org/10.1016/j.softx.2021.100905.</text> <url>https://doi.org/10.1016/j.softx.2021.100905</url> </reference> <reference refNo="18"> <text>Christoph Strassmair and Nicholas Kenelm Taylor. Human Robot Collaboration in Production Environments. In 23rd IEEE International Symposium on Robot and Human Interactive Communication 2014, 2014. URL: https://researchportal.hw.ac.uk/en/publications/human-robot- collaboration-in-production-environments.</text> <url>https://researchportal.hw.ac.uk/en/publications/human-robot- collaboration-in-production-environments</url> </reference> <reference refNo="19"> <text>Robert Endre Tarjan. Shortest Paths. Technical report, AT&amp;T Bell Laboratories, 1981.</text> <url/> </reference> <reference refNo="20"> <text>Ioannis Tsamardinos. A probabilistic approach to robust execution of temporal plans with uncertainty. In Methods and Applications of Artificial Intelligence (SETN 2002), volume 2308 of Lecture Notes in Artificial Intelligence (LNAI), pages 97-108, 2002. URL: https://doi.org/10.1007/3-540-46014-4_10.</text> <url>https://doi.org/10.1007/3-540-46014-4_10</url> </reference> <reference refNo="21"> <text>Andrew J. Wang. Risk-bounded Dynamic Scheduling of Temporal Plans. PhD thesis, Massachusetts Institute of Technology, 2022. URL: https://hdl.handle.net/1721.1/147542.</text> <url>https://hdl.handle.net/1721.1/147542</url> </reference> <reference refNo="22"> <text>Peng Yu, Cheng Fang, and Brian Charles Williams. Resolving uncontrollable conditional temporal problems using continuous relaxations. In 24th International Conference on Automated Planning and Scheduling, ICAPS 2014. AAAI, 2014. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7895, URL: https://doi.org/10.1609/icaps.v24i1.13623.</text> <url>https://doi.org/10.1609/icaps.v24i1.13623</url> </reference> <reference refNo="23"> <text>Peng Yu, Brian C. Williams, Cheng Fang, Jing Cui, and Patrick Haslum. Resolving over-constrained temporal problems with uncertainty through conflict-directed relaxation. Journal of Artificial Intelligence Research, 60:425-490, 2017. URL: https://doi.org/10.1613/jair.5431.</text> <url>https://doi.org/10.1613/jair.5431</url> </reference> <copyright>Luke Hunsberger and Roberto Posenato</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="10"> <title>What Killed the Cat? Towards a Logical Formalization of Curiosity (And Suspense, and Surprise) in Narratives</title> <abstract>We provide a unified framework in which the three emotions at the heart of narrative tension (curiosity, suspense and surprise) are formalized. This framework is built on non-monotonic reasoning which allows us to compactly represent the default behavior of the world and to simulate the affective evolution of an agent receiving a story. After formalizing the notions of awareness, curiosity, surprise and suspense, we explore the properties induced by our definitions and study the computational complexity of detecting them. We finally propose means to evaluate these emotions’ intensity for a given agent listening to a story.</abstract> <keyword>Knowledge Representation</keyword> <keyword>Narration</keyword> <keyword>Cognition</keyword> <subjectClassification acmID="10003752.10010070">Theory of computation~Theory and algorithms for application domains</subjectClassification> <pages>10:1-10:16</pages> <category>Regular Paper</category> <acknowledgements>The authors want to thank the anonymous reviewers for their relevant suggestions that helped them to improve the paper.</acknowledgements> <author> <firstName>Florence</firstName> <lastName>Dupin de Saint-Cyr</lastName> <name>Florence Dupin de Saint-Cyr</name> <affiliation>Lab-STICC CNRS UMR 6285, ENIB, Brest, France</affiliation> <affiliation>IRIT, Université de Toulouse, France</affiliation> <homepageUrl>http://www.irit.fr/~florence.bannay</homepageUrl> <orcid>https://orcid.org/0000-0001-7891-9920</orcid> </author> <author> <firstName>Anne-Gwenn</firstName> <lastName>Bosser</lastName> <name>Anne-Gwenn Bosser</name> <affiliation>Lab-STICC CNRS UMR 6285, ENIB, Brest, France</affiliation> <homepageUrl>https://labsticc.fr/fr/annuaire/bosser-anne-gwenn</homepageUrl> <orcid>https://orcid.org/0000-0002-0442-2660</orcid> </author> <author> <firstName>Benjamin</firstName> <lastName>Callac</lastName> <name>Benjamin Callac</name> <affiliation>Lab-STICC CNRS UMR 6285, Université de Bretagne Occidentale, Brest, France</affiliation> <homepageUrl/> <orcid/> </author> <author> <firstName>Eric</firstName> <lastName>Maisel</lastName> <name>Eric Maisel</name> <affiliation>Lab-STICC CNRS UMR 6285, ENIB, Brest, France</affiliation> <homepageUrl/> <orcid/> </author> <doi>10.4230/LIPIcs.TIME.2024.10</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Carole Adam, Andreas Herzig, and Dominique Longin. A logical formalization of the OCC theory of emotions. Synthese, 168(2):201-248, May 2009. URL: https://doi.org/10.1007/s11229-009-9460-9.</text> <url>https://doi.org/10.1007/s11229-009-9460-9</url> </reference> <reference refNo="2"> <text>Carlos E Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. The journal of symbolic logic, 50(2):510-530, 1985. URL: https://doi.org/10.2307/2274239.</text> <url>https://doi.org/10.2307/2274239</url> </reference> <reference refNo="3"> <text>Guillaume Aucher and Thomas Bolander. Undecidability in epistemic planning. In F. Rossi, editor, Proc. of Int. Joint Conf. on Artificial Intelligence (IJCAI'2013), pages 27-33, Beijing, China, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6903.</text> <url>http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6903</url> </reference> <reference refNo="4"> <text>Heather Barber and Daniel Kudenko. Generation of dilemma-based interactive narratives with a changeable story goal. In 2nd International Conference on INtelligent TEchnologies for interactive enterTAINment. ICST, May 2010. URL: https://doi.org/10.4108/ICST.INTETAIN2008.2477.</text> <url>https://doi.org/10.4108/ICST.INTETAIN2008.2477</url> </reference> <reference refNo="5"> <text>Raphaël Baroni. La tension narrative: suspense, curiosité et surprise. Poétique. Éd. du Seuil, Paris, 2007.</text> <url/> </reference> <reference refNo="6"> <text>Salem Benferhat, Claudette Cayrol, Didier Dubois, Jérôme Lang, and Henri Prade. Inconsistency management and prioritized syntax-based entailment. In Proc. of Int. Joint. Conf. on Artificial Intelligence (IJCAI'93), volume 93, pages 640-645, 1993.</text> <url/> </reference> <reference refNo="7"> <text>Salem Benferhat, Didier Dubois, and Henri Prade. Nonmonotonic reasoning, conditional objects and possibility theory. Artif. Intell., 92(1-2):259-276, 1997. URL: https://doi.org/10.1016/S0004-3702(97)00012-X.</text> <url>https://doi.org/10.1016/S0004-3702(97)00012-X</url> </reference> <reference refNo="8"> <text>Thomas Bolander and Mikkel Birkegaard Andersen. Epistemic planning for single-and multi-agent systems. Journal of Applied Non-Classical Logics, 21(1):9-34, 2011. URL: https://doi.org/10.3166/JANCL.21.9-34.</text> <url>https://doi.org/10.3166/JANCL.21.9-34</url> </reference> <reference refNo="9"> <text>Lorenzo Bonoli. Raphaël Baroni, La tension narrative. Suspense, curiosité, surprise, Paris, Seuil, 2007. Cahiers de Narratologie. Analyse et théorie narratives, 14, February 2008. URL: https://doi.org/10.4000/narratologie.608.</text> <url>https://doi.org/10.4000/narratologie.608</url> </reference> <reference refNo="10"> <text>Anne-Gwenn Bosser, Marc Cavazza, and Ronan Champagnat. Linear Logic for Non-Linear Storytelling. ECAI 2010, pages 713-718, 2010. Publisher: IOS Press. URL: https://doi.org/10.3233/978-1-60750-606-5-713.</text> <url>https://doi.org/10.3233/978-1-60750-606-5-713</url> </reference> <reference refNo="11"> <text>Tom Bylander. The computational complexity of propositional strips planning. Artificial Intelligence, 69(1-2):165-204, 1994. URL: https://doi.org/10.1016/0004-3702(94)90081-7.</text> <url>https://doi.org/10.1016/0004-3702(94)90081-7</url> </reference> <reference refNo="12"> <text>Rogelio E. Cardona-Rivera, Bradley A. Cassell, Stephen G. Ware, and R. Michael Young. Indexter : A Computational Model of the Event-Indexing Situation Model for Characterizing Narratives, 2012.</text> <url/> </reference> <reference refNo="13"> <text>Rogelio E. Cardona-Rivera, Arnav Jhala, Julie Porteous, and R. Michael Young. The story so far on narrative planning. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1):489-499, May 2024. URL: https://doi.org/10.1609/icaps.v34i1.31509.</text> <url>https://doi.org/10.1609/icaps.v34i1.31509</url> </reference> <reference refNo="14"> <text>Noël Carroll. Narrative closure. Philosophical Studies, 135(1):1-15, August 2007. URL: https://doi.org/10.1007/s11098-007-9097-9.</text> <url>https://doi.org/10.1007/s11098-007-9097-9</url> </reference> <reference refNo="15"> <text>Yun-Gyung Cheong and R. Michael Young. Suspenser: A Story Generation System for Suspense. IEEE Transactions on Computational Intelligence and AI in Games, 7(1):39-52, March 2015. URL: https://doi.org/10.1109/TCIAIG.2014.2323894.</text> <url>https://doi.org/10.1109/TCIAIG.2014.2323894</url> </reference> <reference refNo="16"> <text>Christophe Dousson and Pierre Le Maigat. Chronicle recognition improvement using temporal focusing and hierarchization. In IJCAI, volume 7, pages 324-329. Citeseer, 2007. URL: http://ijcai.org/Proceedings/07/Papers/050.pdf.</text> <url>http://ijcai.org/Proceedings/07/Papers/050.pdf</url> </reference> <reference refNo="17"> <text>Florence Dupin de Saint-Cyr. Scenario Update Applied to Causal Reasoning. In Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference, KR 2008, pages 188-197, January 2008. URL: http://www.aaai.org/Library/KR/2008/kr08-019.php.</text> <url>http://www.aaai.org/Library/KR/2008/kr08-019.php</url> </reference> <reference refNo="18"> <text>Florence Dupin de Saint-Cyr, Andreas Herzig, Jérôme Lang, and Pierre Marquis. Reasoning About Action and Change. In Pierre Marquis, Odile Papini, and Henri Prade, editors, A Guided Tour of Artificial Intelligence Research, volume 1 / 3 of Knowledge Representation, Reasoning and Learning, pages 487-518. Springer International Publishing, May 2020. URL: https://doi.org/10.1007/978-3-030-06164-7_15.</text> <url>https://doi.org/10.1007/978-3-030-06164-7_15</url> </reference> <reference refNo="19"> <text>Florence Dupin De Saint-Cyr and Jérôme Lang. Belief extrapolation (or how to reason about observations and unpredicted change). Artificial Intelligence, 175(2):760-790, February 2011. URL: https://doi.org/10.1016/j.artint.2010.11.002.</text> <url>https://doi.org/10.1016/j.artint.2010.11.002</url> </reference> <reference refNo="20"> <text>Florence Dupin de Saint-Cyr and Henri Prade. Belief revision and incongruity: Is it a joke? Journal of Applied Non-Classical Logics, 33(3-4):467-494, October 2023. URL: https://doi.org/10.1080/11663081.2023.2244379.</text> <url>https://doi.org/10.1080/11663081.2023.2244379</url> </reference> <reference refNo="21"> <text>Thomas Eiter and Thomas Lukasiewicz. Default reasoning from conditional knowledge bases: Complexity and tractable cases. Artificial Intelligence, 124(2):169-241, 2000. URL: https://doi.org/10.1016/S0004-3702(00)00073-4.</text> <url>https://doi.org/10.1016/S0004-3702(00)00073-4</url> </reference> <reference refNo="22"> <text>Paul Ekman. An argument for basic emotions. Cognition and Emotion, 6(3-4):169-200, May 1992. URL: https://doi.org/10.1080/02699939208411068.</text> <url>https://doi.org/10.1080/02699939208411068</url> </reference> <reference refNo="23"> <text>Jeffrey Ely, Alexander Frankel, and Emir Kamenica. Suspense and Surprise. Journal of Political Economy, 123(1):215-260, February 2015. URL: https://doi.org/10.1086/677350.</text> <url>https://doi.org/10.1086/677350</url> </reference> <reference refNo="24"> <text>Joseph Jeffrey Finger. Exploiting constraints in design synthesis. PhD thesis, Stanford University, Stanford, CA, 1987.</text> <url/> </reference> <reference refNo="25"> <text>Gerard Genette. Nouveau Discours du Récit. Seuil, 1983.</text> <url/> </reference> <reference refNo="26"> <text>Moisés Goldszmidt and Judea Pearl. On the consistency of defeasible databases. Artificial Intelligence, 52(2):121-149, 1991. URL: https://doi.org/10.1016/0004-3702(91)90039-M.</text> <url>https://doi.org/10.1016/0004-3702(91)90039-M</url> </reference> <reference refNo="27"> <text>Melanie Green and Timothy Brock. The Role of Transportation in the Persuasiveness of Public Narrative. Journal of personality and social psychology, 79:701-21, November 2000. URL: https://doi.org/10.1037/0022-3514.79.5.701.</text> <url>https://doi.org/10.1037/0022-3514.79.5.701</url> </reference> <reference refNo="28"> <text>Joseph Y. Halpern. Alternative Semantics for Unawareness. Games and Economic Behavior, 37(2):321-339, November 2001. URL: https://doi.org/10.1006/game.2000.0832.</text> <url>https://doi.org/10.1006/game.2000.0832</url> </reference> <reference refNo="29"> <text>Kaarlo Jaakko Juhani Hintikka. Knowledge and belief: An introduction to the logic of the two notions. Cornell University Press, Ithaca and London, 1962.</text> <url/> </reference> <reference refNo="30"> <text>Hirofumi Katsuno and Alberto O Mendelzon. On the difference between updating a knowledge base and revising it. KR, 91:387-394, 1991.</text> <url/> </reference> <reference refNo="31"> <text>Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial intelligence, 44(1-2):167-207, 1990. URL: https://doi.org/10.1016/0004-3702(90)90101-5.</text> <url>https://doi.org/10.1016/0004-3702(90)90101-5</url> </reference> <reference refNo="32"> <text>Daniel Lehmann. Another perspective on default reasoning. Annals of mathematics and artificial intelligence, 15:61-82, 1995. URL: https://doi.org/10.1007/BF01535841.</text> <url>https://doi.org/10.1007/BF01535841</url> </reference> <reference refNo="33"> <text>Emiliano Lorini and Cristiano Castelfranchi. The cognitive structure of surprise: looking for basic principles. Topoi, 26(1):133-149, 2007.</text> <url/> </reference> <reference refNo="34"> <text>Emiliano Lorini and François Schwarzentruber. A logic for reasoning about counterfactual emotions. Artificial Intelligence, 175(3):814-847, March 2011. URL: https://doi.org/10.1016/j.artint.2010.11.022.</text> <url>https://doi.org/10.1016/j.artint.2010.11.022</url> </reference> <reference refNo="35"> <text>Chris Martens. Ceptre: A language for modeling generative interactive systems. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 11, pages 51-57, 2015. URL: http://www.aaai.org/ocs/index.php/AIIDE/AIIDE15/paper/view/11536.</text> <url>http://www.aaai.org/ocs/index.php/AIIDE/AIIDE15/paper/view/11536</url> </reference> <reference refNo="36"> <text>Lawrence J. Mazlack. Granular causality speculations. In IEEE Annual Meeting of the Fuzzy Information, 2004. Processing NAFIPS '04., volume 2, pages 690-695 Vol.2, 2004. URL: https://doi.org/10.1109/NAFIPS.2004.1337385.</text> <url>https://doi.org/10.1109/NAFIPS.2004.1337385</url> </reference> <reference refNo="37"> <text>John McCarthy. Epistemological problems of artificial intelligence. In Proc. Int. Joint Conf on Artificial Intelligence (IJCAI'77), pages 1038-1044. Elsevier, 1977. URL: http://ijcai.org/Proceedings/77-2/Papers/094.pdf.</text> <url>http://ijcai.org/Proceedings/77-2/Papers/094.pdf</url> </reference> <reference refNo="38"> <text>John McCarthy and Patrick J Hayes. Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence, 4:463-502, 1969.</text> <url/> </reference> <reference refNo="39"> <text>Salvatore Modica and Aldo Rustichini. Awareness and partitional information structures. Theory and decision, 37:107-124, 1994.</text> <url/> </reference> <reference refNo="40"> <text>Emma Norling. Capturing the quake player: Using a BDI agent to model human behaviour. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1080-1081, Melbourne Australia, July 2003. ACM. URL: https://doi.org/10.1145/860575.860805.</text> <url>https://doi.org/10.1145/860575.860805</url> </reference> <reference refNo="41"> <text>Andrew Ortony, Gerald L Clore, and Allan Collins. The cognitive structure of emotions. Cambridge university press, 2022.</text> <url/> </reference> <reference refNo="42"> <text>Judea Pearl. System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In Proc. 3rd Conf. on Theoretical Aspects of Reasoning about Knowledge, pages 121-135, 1990.</text> <url/> </reference> <reference refNo="43"> <text>David Pizzi, Fred Charles, Jean-Luc Lugrin, and Marc Cavazza. Interactive Storytelling with Literary Feelings, April 2007. URL: https://doi.org/10.1007/978-3-540-74889-2_55.</text> <url>https://doi.org/10.1007/978-3-540-74889-2_55</url> </reference> <reference refNo="44"> <text>Robert Plutchik. A general psychoevolutionary theory of emotion. In Theories of emotion, pages 3-33. Elsevier, 1980.</text> <url/> </reference> <reference refNo="45"> <text>Vladimir Propp. Morphology of the Folktale: Second Edition. University of Texas Press, 1968. URL: https://doi.org/10.7560/783911.</text> <url>https://doi.org/10.7560/783911</url> </reference> <reference refNo="46"> <text>Raymond Reiter. A logic for default reasoning. Artificial intelligence, 13(1-2):81-132, 1980. URL: https://doi.org/10.1016/0004-3702(80)90014-4.</text> <url>https://doi.org/10.1016/0004-3702(80)90014-4</url> </reference> <reference refNo="47"> <text>Jessica Rivera-Villicana, Fabio Zambetta, James Harland, and Marsha Berry. Using BDI to Model Players Behaviour in an Interactive Fiction Game. In Frank Nack and Andrew S. Gordon, editors, Interactive Storytelling, volume 10045, pages 209-220. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-48279-8_19.</text> <url>https://doi.org/10.1007/978-3-319-48279-8_19</url> </reference> <reference refNo="48"> <text>George Lennox Sharman Shackle. Decision, Order and Time in Human Affairs. (2nd edition), Cambridge University Press, UK, 1961.</text> <url/> </reference> <reference refNo="49"> <text>Khaled Skander Ben Slimane, Alexis Comte, Olivier Gasquet, Abdelwahab Heba, Olivier Lezaud, Frederic Maris, and Maël Valais. Twist your logic with touist. CoRR, abs/1507.03663, 2015. URL: https://arxiv.org/abs/1507.03663.</text> <url>https://arxiv.org/abs/1507.03663</url> </reference> <reference refNo="50"> <text>Tran Cao Son, Enrico Pontelli, Marcello Balduccini, and Torsten Schaub. Answer set planning: a survey. Theory and Practice of Logic Programming, 23(1):226-298, 2023. URL: https://doi.org/10.1017/S1471068422000072.</text> <url>https://doi.org/10.1017/S1471068422000072</url> </reference> <reference refNo="51"> <text>Meir Sternberg. How Narrativity Makes a Difference. Narrative, 9(2):115-122, 2001. URL: https://arxiv.org/abs/20107236.</text> <url>https://arxiv.org/abs/20107236</url> </reference> <reference refNo="52"> <text>David Thue and Vadim Bulitko. Modelling goal-directed players in digital games. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 2, pages 86-91, 2006. URL: http://www.aaai.org/Library/AIIDE/2006/aiide06-018.php.</text> <url>http://www.aaai.org/Library/AIIDE/2006/aiide06-018.php</url> </reference> <reference refNo="53"> <text>Tom Trabasso and Linda L Sperry. Causal relatedness and importance of story events. Journal of Memory and Language, 24(5):595-611, October 1985. URL: https://doi.org/10.1016/0749-596X(85)90048-8.</text> <url>https://doi.org/10.1016/0749-596X(85)90048-8</url> </reference> <reference refNo="54"> <text>Johan Van Benthem and Fernando R Velázquez-Quesada. The dynamics of awareness. Synthese, 177:5-27, 2010. URL: https://doi.org/10.1007/S11229-010-9764-9.</text> <url>https://doi.org/10.1007/S11229-010-9764-9</url> </reference> <reference refNo="55"> <text>Marianne Winslett. Updating Logical Databases. Cambridge University Press, 1990.</text> <url/> </reference> <copyright>Florence Dupin de Saint-Cyr, Anne-Gwenn Bosser, Benjamin Callac, and Eric Maisel</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="11"> <title>Faster Algorithm for Converting an STNU into Minimal Dispatchable Form</title> <abstract>A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about temporal constraints on activities, including those with uncertain durations. An STNU is dispatchable if it can be flexibly and efficiently executed in real time while guaranteeing that all relevant constraints are satisfied. The number of edges in a dispatchable network affects the computational work that must be done during real-time execution. Recent work presented an O(k n³)-time algorithm for converting a dispatchable STNU into an equivalent dispatchable network having a minimal number of edges, where n is the number of timepoints and k is the number of actions with uncertain durations. This paper presents a modification of that algorithm, making it an order of magnitude faster, down to O(n³). Given that in typical applications k = O(n), this represents an effective order-of-magnitude reduction from O(n⁴) to O(n³).</abstract> <keyword>Temporal constraint networks</keyword> <keyword>dispatchable networks</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <subjectClassification acmID="10003752.10003809.10003635.10010038">Theory of computation~Dynamic graph algorithms</subjectClassification> <pages>11:1-11:14</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Luke</firstName> <lastName>Hunsberger</lastName> <name>Luke Hunsberger</name> <affiliation>Vassar College, Poughkeepsie, NY, USA</affiliation> <homepageUrl>https://www.cs.vassar.edu/~hunsberg</homepageUrl> <orcid>https://orcid.org/0009-0005-8603-4803</orcid> </author> <author> <firstName>Roberto</firstName> <lastName>Posenato</lastName> <name>Roberto Posenato</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl>https://www.di.univr.it/?ent=persona&amp;id=102</homepageUrl> <orcid>https://orcid.org/0000-0003-0944-0419</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.11</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Massimo Cairo, Luke Hunsberger, and Romeo Rizzi. Faster Dynamic Controllablity Checking for Simple Temporal Networks with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME-2018), volume 120 of LIPIcs, pages 8:1-8:16, 2018. URL: https://doi.org/10.4230/LIPIcs.TIME.2018.8.</text> <url>https://doi.org/10.4230/LIPIcs.TIME.2018.8</url> </reference> <reference refNo="2"> <text>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022. URL: https://mitpress.mit.edu/9780262046305/introduction-to- algorithms.</text> <url>https://mitpress.mit.edu/9780262046305/introduction-to- algorithms</url> </reference> <reference refNo="3"> <text>Rina Dechter, Itay Meiri, and J. Pearl. Temporal Constraint Networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.</text> <url>https://doi.org/10.1016/0004-3702(91)90006-6</url> </reference> <reference refNo="4"> <text>Luke Hunsberger. Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In 16th International Symposium on Temporal Representation and Reasoning (TIME-2009), pages 155-162, 2009. URL: https://doi.org/10.1109/TIME.2009.25.</text> <url>https://doi.org/10.1109/TIME.2009.25</url> </reference> <reference refNo="5"> <text>Luke Hunsberger. Efficient execution of dynamically controllable simple temporal networks with uncertainty. Acta Informatica, 53(2):89-147, 2015. URL: https://doi.org/10.1007/s00236-015-0227-0.</text> <url>https://doi.org/10.1007/s00236-015-0227-0</url> </reference> <reference refNo="6"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the RUL^- Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty. In 36th AAAI Conference on Artificial Intelligence (AAAI-22), volume 36-9, pages 9776-9785. AAAI Pres, 2022. URL: https://doi.org/10.1609/aaai.v36i9.21213.</text> <url>https://doi.org/10.1609/aaai.v36i9.21213</url> </reference> <reference refNo="7"> <text>Luke Hunsberger and Roberto Posenato. A Faster Algorithm for Converting Simple Temporal Networks with Uncertainty into Dispatchable Form. Information and Computation, 293(105063):1-21, 2023. URL: https://doi.org/10.1016/j.ic.2023.105063.</text> <url>https://doi.org/10.1016/j.ic.2023.105063</url> </reference> <reference refNo="8"> <text>Luke Hunsberger and Roberto Posenato. Converting Simple Temporal Networks with Uncertainty into Minimal Equivalent Dispatchable Form. In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024), volume 34, pages 290-300, 2024. URL: https://doi.org/10.1609/icaps.v34i1.31487.</text> <url>https://doi.org/10.1609/icaps.v34i1.31487</url> </reference> <reference refNo="9"> <text>Luke Hunsberger and Roberto Posenato. Foundations of Dispatchability for Simple Temporal Networks with Uncertainty. In 16th International Conference on Agents and Artificial Intelligence (ICAART 2024), volume 2, pages 253-263. SCITEPRESS, 2024. URL: https://doi.org/10.5220/0012360000003636.</text> <url>https://doi.org/10.5220/0012360000003636</url> </reference> <reference refNo="10"> <text>Paul Morris. A Structural Characterization of Temporal Dynamic Controllability. In Principles and Practice of Constraint Programming (CP-2006), volume 4204, pages 375-389, 2006. URL: https://doi.org/10.1007/11889205_28.</text> <url>https://doi.org/10.1007/11889205_28</url> </reference> <reference refNo="11"> <text>Paul Morris. Dynamic controllability and dispatchability relationships. In Int. Conf. on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR-2014), volume 8451 of LNCS, pages 464-479. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07046-9_33.</text> <url>https://doi.org/10.1007/978-3-319-07046-9_33</url> </reference> <reference refNo="12"> <text>Paul Morris. The Mathematics of Dispatchability Revisited. In 26th International Conference on Automated Planning and Scheduling (ICAPS-2016), pages 244-252, 2016. URL: https://doi.org/10.1609/icaps.v26i1.13739.</text> <url>https://doi.org/10.1609/icaps.v26i1.13739</url> </reference> <reference refNo="13"> <text>Paul Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In 17th Int. Joint Conf. on Artificial Intelligence (IJCAI-2001), volume 1, pages 494-499, 2001. URL: https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf.</text> <url>https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf</url> </reference> <reference refNo="14"> <text>Nicola Muscettola, Paul H. Morris, and Ioannis Tsamardinos. Reformulating temporal plans for efficient execution. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning, KR'98, pages 444-452, 1998.</text> <url/> </reference> <reference refNo="15"> <text>Roberto Posenato. STNU Benchmark version 2020, 2020. Last access 2022-12-01. URL: https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html.</text> <url>https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html</url> </reference> <reference refNo="16"> <text>Ioannis Tsamardinos, Nicola Muscettola, and Paul Morris. Fast Transformation of Temporal Plans for Efficient Execution. In 15th National Conf. on Artificial Intelligence (AAAI-1998), pages 254-261, 1998. URL: https://cdn.aaai.org/AAAI/1998/AAAI98-035.pdf.</text> <url>https://cdn.aaai.org/AAAI/1998/AAAI98-035.pdf</url> </reference> <copyright>Luke Hunsberger and Roberto Posenato</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="12"> <title>Robust Execution of Probabilistic STNs</title> <abstract>A Probabilistic Simple Temporal Network (PSTN) is a formalism for representing and reasoning about actions subject to temporal constraints, where some action durations may be uncontrollable, modeled using continuous probability density functions. Recent work aims to manage this kind of uncertainty during execution by approximating a PSTN by a Simple Temporal Network with Uncertainty (STNU) (for which well-known execution strategies exist) and using an STNU execution strategy to execute the PSTN, hoping that its probabilistic action durations will not cause any constraint violations.&#13; This paper presents significant improvements to the robust execution of PSTNs. Our approach is based on a recent, faster algorithm for finding negative cycles in non-DC STNUs. We also formally prove that many of the constraints included in others' work are unnecessary and that our algorithm can take advantage of a flexible real-time execution algorithm to react to observations of contingent durations that may fall outside the fixed STNU bounds. The paper presents an empirical evaluation of our approach that provides evidence of its effectiveness in robustly executing PSTNs derived from a publicly available benchmark.</abstract> <keyword>Temporal constraint networks</keyword> <keyword>probabilistic durations</keyword> <keyword>dispatchable networks</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <subjectClassification acmID="10003752.10003809.10003635.10010038">Theory of computation~Dynamic graph algorithms</subjectClassification> <pages>12:1-12:19</pages> <category>Regular Paper</category> <supplements> <url category="Software" subCategory="Source code">https://profs.scienze.univr.it/~posenato/software/cstnu/</url> </supplements> <acknowledgements/> <author> <firstName>Luke</firstName> <lastName>Hunsberger</lastName> <name>Luke Hunsberger</name> <affiliation>Vassar College, Poughkeepsie, NY, USA</affiliation> <homepageUrl>https://www.cs.vassar.edu/~hunsberg</homepageUrl> <orcid>https://orcid.org/0009-0005-8603-4803</orcid> </author> <author> <firstName>Roberto</firstName> <lastName>Posenato</lastName> <name>Roberto Posenato</name> <affiliation>University of Verona, Italy</affiliation> <homepageUrl>https://www.di.univr.it/?ent=persona&amp;id=102</homepageUrl> <orcid>https://orcid.org/0000-0003-0944-0419</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.12</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Nikhil Bhargava. Multi-Agent Coordination under Uncertain Communication. 33rd AAAI Conference on Artificial Intelligence (AAAI-19), 33(1):9878-9879, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33019878.</text> <url>https://doi.org/10.1609/aaai.v33i01.33019878</url> </reference> <reference refNo="2"> <text>Massimo Cairo, Luke Hunsberger, and Romeo Rizzi. Faster Dynamic Controllablity Checking for Simple Temporal Networks with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME-2018), volume 120 of LIPIcs, pages 8:1-8:16, 2018. URL: https://doi.org/10.4230/LIPIcs.TIME.2018.8.</text> <url>https://doi.org/10.4230/LIPIcs.TIME.2018.8</url> </reference> <reference refNo="3"> <text>Rosy Chen, Yiran Ma, Siqi Wu, and James C. Boerkoel, Jr. Sensitivity analysis for dynamic control of pstns with skewed distributions. In 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), volume 33, pages 95-99, 2023. URL: https://doi.org/10.1609/icaps.v33i1.27183.</text> <url>https://doi.org/10.1609/icaps.v33i1.27183</url> </reference> <reference refNo="4"> <text>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022. URL: https://mitpress.mit.edu/9780262046305/introduction-to- algorithms.</text> <url>https://mitpress.mit.edu/9780262046305/introduction-to- algorithms</url> </reference> <reference refNo="5"> <text>Rina Dechter, Itay Meiri, and J. Pearl. Temporal Constraint Networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.</text> <url>https://doi.org/10.1016/0004-3702(91)90006-6</url> </reference> <reference refNo="6"> <text>Maya Abo Dominguez, William La, and James C. Boerkoel Jr. Modeling human temporal uncertainty in human-agent teams. CoRR, abs/2010.04849, 2020. URL: https://arxiv.org/abs/2010.04849,</text> <url>https://arxiv.org/abs/2010.04849</url> </reference> <reference refNo="7"> <text>Cheng Fang, Peng Yu, and Brian C. Williams. Chance-constrained probabilistic simple temporal problems. In 28th AAAI Conference on Artificial Intelligence (AAAI-2014), volume 3, pages 2264-2270, 2014. URL: https://doi.org/10.1609/aaai.v28i1.9048.</text> <url>https://doi.org/10.1609/aaai.v28i1.9048</url> </reference> <reference refNo="8"> <text>Michael Gao, Lindsay Popowski, and James C. Boerkoel, Jr. Dynamic Control of Probabilistic Simple Temporal Networks. In 34th AAAI Conference on Artificial Intelligence (AAAI-20), volume 34, pages 9851-9858, 2020. URL: https://doi.org/10.1609/aaai.v34i06.6538.</text> <url>https://doi.org/10.1609/aaai.v34i06.6538</url> </reference> <reference refNo="9"> <text>Philip E. Gill, Walter Murray, and Michael A. Saunders. Snopt: An sqp algorithm for large-scale constrained optimization. SIAM Review, 47(1):99-131, 2005. URL: https://doi.org/10.1137/S0036144504446096.</text> <url>https://doi.org/10.1137/S0036144504446096</url> </reference> <reference refNo="10"> <text>Luke Hunsberger. Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In 16th International Symposium on Temporal Representation and Reasoning (TIME-2009), pages 155-162, 2009. URL: https://doi.org/10.1109/TIME.2009.25.</text> <url>https://doi.org/10.1109/TIME.2009.25</url> </reference> <reference refNo="11"> <text>Luke Hunsberger. Magic Loops in Simple Temporal Networks with Uncertainty-Exploiting Structure to Speed Up Dynamic Controllability Checking. In 5th International Conference on Agents and Artificial Intelligence (ICAART-2013), volume 2, pages 157-170, 2013. URL: https://doi.org/10.5220/0004260501570170.</text> <url>https://doi.org/10.5220/0004260501570170</url> </reference> <reference refNo="12"> <text>Luke Hunsberger. Magic Loops and the Dynamic Controllability of Simple Temporal Networks with Uncertainty. In Joaquim Filipe and Ana Fred, editors, Agents and Artificial Intelligence, volume 449 of Communications in Computer and Information Science (CCIS), pages 332-350, 2014. URL: https://doi.org/10.1007/978-3-662-44440-5_20.</text> <url>https://doi.org/10.1007/978-3-662-44440-5_20</url> </reference> <reference refNo="13"> <text>Luke Hunsberger. Efficient execution of dynamically controllable simple temporal networks with uncertainty. Acta Informatica, 53(2):89-147, 2015. URL: https://doi.org/10.1007/s00236-015-0227-0.</text> <url>https://doi.org/10.1007/s00236-015-0227-0</url> </reference> <reference refNo="14"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the RUL^- Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty. In 36th AAAI Conference on Artificial Intelligence (AAAI-22), volume 36-9, pages 9776-9785. AAAI Pres, 2022. URL: https://doi.org/10.1609/aaai.v36i9.21213.</text> <url>https://doi.org/10.1609/aaai.v36i9.21213</url> </reference> <reference refNo="15"> <text>Luke Hunsberger and Roberto Posenato. A Faster Algorithm for Converting Simple Temporal Networks with Uncertainty into Dispatchable Form. Information and Computation, 293(105063):1-21, 2023. URL: https://doi.org/10.1016/j.ic.2023.105063.</text> <url>https://doi.org/10.1016/j.ic.2023.105063</url> </reference> <reference refNo="16"> <text>Luke Hunsberger and Roberto Posenato. A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty. In The 31st International Symposium on Temporal Representation and Reasoning (TIME-2024), volume 318 of LIPIcs, 2024. URL: https://doi.org/10.4230/LIPIcs.TIME.2024.8.</text> <url>https://doi.org/10.4230/LIPIcs.TIME.2024.8</url> </reference> <reference refNo="17"> <text>Luke Hunsberger and Roberto Posenato. Converting Simple Temporal Networks with Uncertainty into Minimal Equivalent Dispatchable Form. In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024), volume 34, pages 290-300, 2024. URL: https://doi.org/10.1609/icaps.v34i1.31487.</text> <url>https://doi.org/10.1609/icaps.v34i1.31487</url> </reference> <reference refNo="18"> <text>Luke Hunsberger and Roberto Posenato. Foundations of Dispatchability for Simple Temporal Networks with Uncertainty. In 16th International Conference on Agents and Artificial Intelligence (ICAART 2024), volume 2, pages 253-263. SCITEPRESS, 2024. URL: https://doi.org/10.5220/0012360000003636.</text> <url>https://doi.org/10.5220/0012360000003636</url> </reference> <reference refNo="19"> <text>Erez Karpas, Steven J. Levine, Peng Yu, and Brian C. Williams. Robust Execution of Plans for Human-Robot Teams. In 25th Int. Conf. on Automated Planning and Scheduling (ICAPS-15), volume 25, pages 342-346, 2015. URL: https://doi.org/10.1609/icaps.v25i1.13698.</text> <url>https://doi.org/10.1609/icaps.v25i1.13698</url> </reference> <reference refNo="20"> <text>Dimitri Kececioglu et al. Reliability Engineering Handbook, volume 1. DEStech Publications, Inc, 2002.</text> <url/> </reference> <reference refNo="21"> <text>Paul Morris. A Structural Characterization of Temporal Dynamic Controllability. In Principles and Practice of Constraint Programming (CP-2006), volume 4204, pages 375-389, 2006. URL: https://doi.org/10.1007/11889205_28.</text> <url>https://doi.org/10.1007/11889205_28</url> </reference> <reference refNo="22"> <text>Paul Morris. Dynamic controllability and dispatchability relationships. In Int. Conf. on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR-2014), volume 8451 of LNCS, pages 464-479. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07046-9_33.</text> <url>https://doi.org/10.1007/978-3-319-07046-9_33</url> </reference> <reference refNo="23"> <text>Paul Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In 17th Int. Joint Conf. on Artificial Intelligence (IJCAI-2001), volume 1, pages 494-499, 2001. URL: https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf.</text> <url>https://www.ijcai.org/Proceedings/01/IJCAI-2001-e.pdf</url> </reference> <reference refNo="24"> <text>Nicola Muscettola, Paul H. Morris, and Ioannis Tsamardinos. Reformulating temporal plans for efficient execution. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning, KR'98, pages 444-452, 1998.</text> <url/> </reference> <reference refNo="25"> <text>Roberto Posenato. STNU Benchmark version 2020, 2020. Last access 2022-12-01. URL: https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html.</text> <url>https://profs.scienze.univr.it/~posenato/software/cstnu/ benchmarkWrapper.html</url> </reference> <reference refNo="26"> <text>Roberto Posenato. CSTNU Tool: A Java library for checking temporal networks. SoftwareX, 17:100905, 2022. URL: https://doi.org/10.1016/j.softx.2021.100905.</text> <url>https://doi.org/10.1016/j.softx.2021.100905</url> </reference> <reference refNo="27"> <text>Ioannis Tsamardinos. A probabilistic approach to robust execution of temporal plans with uncertainty. In Methods and Applications of Artificial Intelligence (SETN 2002), volume 2308 of Lecture Notes in Artificial Intelligence (LNAI), pages 97-108, 2002. URL: https://doi.org/10.1007/3-540-46014-4_10.</text> <url>https://doi.org/10.1007/3-540-46014-4_10</url> </reference> <reference refNo="28"> <text>Ioannis Tsamardinos, Nicola Muscettola, and Paul Morris. Fast Transformation of Temporal Plans for Efficient Execution. In 15th National Conf. on Artificial Intelligence (AAAI-1998), pages 254-261, 1998. URL: https://cdn.aaai.org/AAAI/1998/AAAI98-035.pdf.</text> <url>https://cdn.aaai.org/AAAI/1998/AAAI98-035.pdf</url> </reference> <reference refNo="29"> <text>Thierry Vidal and Hélène Fargier. Handling contingency in temporal constraint networks: from consistency to controllabilities. J. of Experimental &amp; Theoretical Artificial Intelligence, 11(1):23-45, 1999. URL: https://doi.org/10.1080/095281399146607.</text> <url>https://doi.org/10.1080/095281399146607</url> </reference> <reference refNo="30"> <text>Andrew Wang and Brian C. Williams. Chance-Constrained Scheduling via Conflict-Directed Risk Allocation. In 29th Conference on Artificial Intelligence (AAAI-2015), volume 29, 2015. URL: https://doi.org/10.1609/aaai.v29i1.9693.</text> <url>https://doi.org/10.1609/aaai.v29i1.9693</url> </reference> <reference refNo="31"> <text>Andrew J. Wang. Risk-bounded Dynamic Scheduling of Temporal Plans. PhD thesis, Massachusetts Institute of Technology, 2022. URL: https://hdl.handle.net/1721.1/147542.</text> <url>https://hdl.handle.net/1721.1/147542</url> </reference> <reference refNo="32"> <text>Peifeng Yin, Ping Luo, Wang-Chien Lee, and Min Wang. Silence is also evidence: interpreting dwell time for recommendation from psychological perspective. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, pages 989-997, 2013. URL: https://doi.org/10.1145/2487575.2487663.</text> <url>https://doi.org/10.1145/2487575.2487663</url> </reference> <reference refNo="33"> <text>Peng Yu, Cheng Fang, and Brian Charles Williams. Resolving uncontrollable conditional temporal problems using continuous relaxations. In 24th International Conference on Automated Planning and Scheduling, ICAPS 2014. AAAI, 2014. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7895, URL: https://doi.org/10.1609/icaps.v24i1.13623.</text> <url>https://doi.org/10.1609/icaps.v24i1.13623</url> </reference> <copyright>Luke Hunsberger and Roberto Posenato</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="13"> <title>Introducing Interdependent Simple Temporal Networks with Uncertainty for Multi-Agent Temporal Planning</title> <abstract>Simple Temporal Networks with Uncertainty are a powerful and widely used formalism for representing and reasoning over convex temporal constraints in the presence of uncertainty called contingent constraints. Since their introduction, they have been used in planning and scheduling applications to model situations where the scheduling agent does not control some activity durations or event timings. What needs to be checked is then the controllability of the network, i.e., that there is a valid execution strategy whatever the values of the contingents. This paper considers a new type of multi-agent extension, where, as opposed to previous works, each agent manages its own separate STNU, and the control over activity durations is shared among the agents: what is called here a contract is a mutual constraint controllable for some agent and contingent for others. We will propose a semantically enriched version of STNUs that will be composed into a global Multi-agent Interdependent STNUs model. Then, controllability issues will be revisited, and we will focus on the repair problem, i.e., how to regain failed controllability by shrinking some of the shared contract durations, here in a centralized manner.</abstract> <keyword>Temporal constraints satisfaction</keyword> <keyword>uncertainty</keyword> <keyword>STNU</keyword> <keyword>Controllability checking</keyword> <keyword>Explainable inconsistency</keyword> <keyword>Multi-agent planning</keyword> <subjectClassification acmID="10010147">Computing methodologies</subjectClassification> <pages>13:1-13:14</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Ajdin</firstName> <lastName>Sumic</lastName> <name>Ajdin Sumic</name> <affiliation>Technological University of Tarbes, France</affiliation> <homepageUrl/> <orcid/> </author> <author> <firstName>Thierry</firstName> <lastName>Vidal</lastName> <name>Thierry Vidal</name> <affiliation>Technological University of Tarbes, France</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-4369-5749</orcid> </author> <author> <firstName>Andrea</firstName> <lastName>Micheli</lastName> <name>Andrea Micheli</name> <affiliation>Fundazione Bruno Kessler, Trento, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-6370-1061</orcid> </author> <author> <firstName>Alessandro</firstName> <lastName>Cimatti</lastName> <name>Alessandro Cimatti</name> <affiliation>Fundazione Bruno Kessler, Trento, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-1315-6990</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.13</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Arthur Bit-Monnot, Malik Ghallab, Félix Ingrand, and David E. Smith. FAPE: a constraint-based planner for generative and hierarchical temporal planning. CoRR, abs/2010.13121, 2020. URL: https://arxiv.org/abs/2010.13121.</text> <url>https://arxiv.org/abs/2010.13121</url> </reference> <reference refNo="2"> <text>James C. Boerkoel and Edmund H. Durfee. Distributed reasoning for multiagent simple temporal problems. J. Artif. Intell. Res., 47:95-156, 2013. URL: https://doi.org/10.1613/JAIR.3840.</text> <url>https://doi.org/10.1613/JAIR.3840</url> </reference> <reference refNo="3"> <text>Guillaume Casanova, Cédric Pralet, Charles Lesire, and Thierry Vidal. Solving dynamic controllability problem of multi-agent plans with uncertainty using mixed integer linear programming. In Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hüllermeier, Virginia Dignum, Frank Dignum, and Frank van Harmelen, editors, ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence and Applications, pages 930-938. IOS Press, 2016. URL: https://doi.org/10.3233/978-1-61499-672-9-930.</text> <url>https://doi.org/10.3233/978-1-61499-672-9-930</url> </reference> <reference refNo="4"> <text>Amedeo Cesta, Angelo Oddi, and Stephen F. Smith. A constraint-based method for project scheduling with time windows. J. Heuristics, 8(1):109-136, 2002. URL: https://doi.org/10.1023/A:1013617802515.</text> <url>https://doi.org/10.1023/A:1013617802515</url> </reference> <reference refNo="5"> <text>Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.</text> <url>https://doi.org/10.1016/0004-3702(91)90006-6</url> </reference> <reference refNo="6"> <text>Marco Gario and Andrea Micheli. pysmt: a solver-agnostic library for fast prototyping of smt-based algorithms. In SMT Workshop, 2015.</text> <url/> </reference> <reference refNo="7"> <text>Luke Hunsberger. Algorithms for a temporal decoupling problem in multi-agent planning. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada, pages 468-475, 2002. URL: http://www.aaai.org/Library/AAAI/2002/aaai02-071.php.</text> <url>http://www.aaai.org/Library/AAAI/2002/aaai02-071.php</url> </reference> <reference refNo="8"> <text>Luke Hunsberger. Distributing the control of a temporal network among multiple agents. In The Second International Joint Conference on Autonomous Agents &amp; Multiagent Systems, AAMAS 2003, July 14-18, 2003, Melbourne, Victoria, Australia, Proceedings, pages 899-906, 2003. URL: https://doi.org/10.1145/860575.860720.</text> <url>https://doi.org/10.1145/860575.860720</url> </reference> <reference refNo="9"> <text>Luke Hunsberger and Roberto Posenato. Speeding up the rulasciimacron dynamic-controllability-checking algorithm for simple temporal networks with uncertainty. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 9776-9785. AAAI Press, 2022. URL: https://doi.org/10.1609/AAAI.V36I9.21213.</text> <url>https://doi.org/10.1609/AAAI.V36I9.21213</url> </reference> <reference refNo="10"> <text>Josef Lubas, Marco Franceschetti, and Johann Eder. Resolving conflicts in process models with temporal constraints. In Proceedings of the ER Forum and PhD Symposium, 2022.</text> <url/> </reference> <reference refNo="11"> <text>Paul H Morris and Nicola Muscettola. Temporal dynamic controllability revisited. In Aaai, pages 1193-1198, 2005. URL: http://www.aaai.org/Library/AAAI/2005/aaai05-189.php.</text> <url>http://www.aaai.org/Library/AAAI/2005/aaai05-189.php</url> </reference> <reference refNo="12"> <text>Roberto Posenato and Carlo Combi. Adding flexibility to uncertainty: Flexible simple temporal networks with uncertainty (ftnu). Information Sciences, 584:784-807, 2022. URL: https://doi.org/10.1016/J.INS.2021.10.008.</text> <url>https://doi.org/10.1016/J.INS.2021.10.008</url> </reference> <reference refNo="13"> <text>Roberto Sebastiani and Silvia Tomasi. Optimization modulo theories with linear rational costs. ACM Trans. Comput. Log., 16(2):12:1-12:43, 2015. URL: https://doi.org/10.1145/2699915.</text> <url>https://doi.org/10.1145/2699915</url> </reference> <reference refNo="14"> <text>Ajdin Sumic, Alessandro Cimatti, Andrea Micheli, and Thierry Vidal. SMT-based repair of disjunctive temporal networks with uncertainty: Strong and weak controllability. In Proceedings of the The 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2024), 2024.</text> <url/> </reference> <reference refNo="15"> <text>Alessandro Valentini, Andrea Micheli, and Alessandro Cimatti. Temporal planning with intermediate conditions and effects. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020,, pages 9975-9982, 2020. URL: https://doi.org/10.1609/AAAI.V34I06.6553.</text> <url>https://doi.org/10.1609/AAAI.V34I06.6553</url> </reference> <reference refNo="16"> <text>Gérard Verfaillie, Cédric Pralet, and Michel Lemaître. How to model planning and scheduling problems using constraint networks on timelines. Knowl. Eng. Rev., 25(3):319-336, 2010. URL: https://doi.org/10.1017/S0269888910000172.</text> <url>https://doi.org/10.1017/S0269888910000172</url> </reference> <reference refNo="17"> <text>Thierry Vidal and Hélène Fargier. Handling contingency in temporal constraint networks: from consistency to controllabilities. Journal of Experimental &amp; Theoretical Artificial Intelligence, 11(1):23-45, 1999. URL: https://doi.org/10.1080/095281399146607.</text> <url>https://doi.org/10.1080/095281399146607</url> </reference> <reference refNo="18"> <text>Yuening Zhang and Brian C. Williams. Privacy-preserving algorithm for decoupling of multi-agent plans with uncertainty. In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling, ICAPS 2021, Guangzhou, China (virtual), August 2-13, 2021, pages 426-434. AAAI Press, 2021. URL: https://ojs.aaai.org/index.php/ICAPS/article/view/15988.</text> <url>https://ojs.aaai.org/index.php/ICAPS/article/view/15988</url> </reference> <copyright>Ajdin Sumic, Thierry Vidal, Andrea Micheli, and Alessandro Cimatti</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="14"> <title>Learning Temporal Properties from Event Logs via Sequential Analysis</title> <abstract>In this work, we present a novel approach to learning Linear Temporal Logic (LTL) formulae from event logs by leveraging statistical techniques from sequential analysis. In particular, we employ the Sequential Probability Ratio Test (SPRT), using Trace Alignment to quantify the discrepancy between a trace and a candidate LTL formula. We then test the proposed approach in a controlled experimental setting and highlight its advantages, which include robustness to noise and data efficiency.</abstract> <keyword>Process Mining</keyword> <keyword>Declarative Process Discovery</keyword> <keyword>Trace Alignment</keyword> <keyword>Sequential Analysis</keyword> <subjectClassification acmID="10003752.10003790.10003793">Theory of computation~Modal and temporal logics</subjectClassification> <subjectClassification acmID="10010405.10010406.10010412">Applied computing~Business process management</subjectClassification> <pages>14:1-14:14</pages> <category>Regular Paper</category> <funding>This project has been funded by the French government as part of France 2030 (Grant agreement n°ANR-19-PI3A-0004) and by the European Union - Next Generation EU as part of the France Relance.</funding> <acknowledgements/> <author> <firstName>Francesco</firstName> <lastName>Chiariello</lastName> <name>Francesco Chiariello</name> <affiliation>IRIT, ANITI, University of Toulouse, France</affiliation> <homepageUrl>https://francescochiariello.me/</homepageUrl> <orcid>https://orcid.org/0000-0001-7855-7480</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.14</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Simone Agostinelli, Francesco Chiariello, Fabrizio Maria Maggi, Andrea Marrella, and Fabio Patrizi. Process mining meets model learning: Discovering deterministic finite state automata from event logs for business process analysis. Inf. Syst., 114:102180, 2023. URL: https://doi.org/10.1016/J.IS.2023.102180.</text> <url>https://doi.org/10.1016/J.IS.2023.102180</url> </reference> <reference refNo="2"> <text>Iris Beerepoot, Claudio Di Ciccio, Hajo A. Reijers, Stefanie Rinderle-Ma, Wasana Bandara, Andrea Burattin, Diego Calvanese, Tianwa Chen, Izack Cohen, Benoît Depaire, Gemma Di Federico, Marlon Dumas, Christopher G. J. van Dun, Tobias Fehrer, Dominik Andreas Fischer, Avigdor Gal, Marta Indulska, Vatche Isahagian, Christopher Klinkmüller, Wolfgang Kratsch, Henrik Leopold, Amy Van Looy, Hugo A. López, Sanja Lukumbuzya, Jan Mendling, Lara Meyers, Linda Moder, Marco Montali, Vinod Muthusamy, Manfred Reichert, Yara Rizk, Michael Rosemann, Maximilian Röglinger, Shazia Sadiq, Ronny Seiger, Tijs Slaats, Mantas Simkus, Ida Asadi Someh, Barbara Weber, Ingo Weber, Mathias Weske, and Francesca Zerbato. The biggest business process management problems to solve before we die. Comput. Ind., 146:103837, 2023. URL: https://doi.org/10.1016/J.COMPIND.2022.103837.</text> <url>https://doi.org/10.1016/J.COMPIND.2022.103837</url> </reference> <reference refNo="3"> <text>Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. Answer set programming at a glance. Commun. ACM, 54(12):92-103, 2011. URL: https://doi.org/10.1145/2043174.2043195.</text> <url>https://doi.org/10.1145/2043174.2043195</url> </reference> <reference refNo="4"> <text>Alberto Camacho and Sheila A. McIlraith. Learning interpretable models expressed in linear temporal logic. In ICAPS, pages 621-630. AAAI Press, 2019. URL: https://ojs.aaai.org/index.php/ICAPS/article/view/3529.</text> <url>https://ojs.aaai.org/index.php/ICAPS/article/view/3529</url> </reference> <reference refNo="5"> <text>Francesco Chiariello, Fabrizio Maria Maggi, and Fabio Patrizi. Asp-based declarative process mining. In AAAI, pages 5539-5547. AAAI Press, 2022. URL: https://doi.org/10.1609/AAAI.V36I5.20493.</text> <url>https://doi.org/10.1609/AAAI.V36I5.20493</url> </reference> <reference refNo="6"> <text>Francesco Chiariello, Fabrizio Maria Maggi, and Fabio Patrizi. A tool for compiling declarative process mining problems in ASP. Softw. Impacts, 14:100435, 2022. URL: https://doi.org/10.1016/J.SIMPA.2022.100435.</text> <url>https://doi.org/10.1016/J.SIMPA.2022.100435</url> </reference> <reference refNo="7"> <text>Francesco Chiariello, Fabrizio Maria Maggi, and Fabio Patrizi. From LTL on process traces to finite-state automata. In BPM (Demos / Resources Forum), volume 3469 of CEUR Workshop Proceedings, pages 127-131. CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3469/paper-23.pdf.</text> <url>https://ceur-ws.org/Vol-3469/paper-23.pdf</url> </reference> <reference refNo="8"> <text>Giuseppe De Giacomo, Riccardo De Masellis, and Marco Montali. Reasoning on LTL on finite traces: Insensitivity to infiniteness. In AAAI, pages 1027-1033. AAAI Press, 2014. URL: https://doi.org/10.1609/AAAI.V28I1.8872.</text> <url>https://doi.org/10.1609/AAAI.V28I1.8872</url> </reference> <reference refNo="9"> <text>Giuseppe De Giacomo, Francesco Fuggitti, Fabrizio Maria Maggi, Andrea Marrella, and Fabio Patrizi. A tool for declarative trace alignment via automated planning. Softw. Impacts, 16:100505, 2023. URL: https://doi.org/10.1016/J.SIMPA.2023.100505.</text> <url>https://doi.org/10.1016/J.SIMPA.2023.100505</url> </reference> <reference refNo="10"> <text>Giuseppe De Giacomo, Fabrizio Maria Maggi, Andrea Marrella, and Fabio Patrizi. On the disruptive effectiveness of automated planning for ltlf-based trace alignment. In AAAI, pages 3555-3561. AAAI Press, 2017. URL: https://doi.org/10.1609/AAAI.V31I1.11020.</text> <url>https://doi.org/10.1609/AAAI.V31I1.11020</url> </reference> <reference refNo="11"> <text>Giuseppe De Giacomo and Moshe Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. In IJCAI, pages 854-860. IJCAI/AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6997.</text> <url>http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6997</url> </reference> <reference refNo="12"> <text>Massimiliano de Leoni, Fabrizio Maria Maggi, and Wil M. P. van der Aalst. An alignment-based framework to check the conformance of declarative process models and to preprocess event-log data. Inf. Syst., 47:258-277, 2015. URL: https://doi.org/10.1016/J.IS.2013.12.005.</text> <url>https://doi.org/10.1016/J.IS.2013.12.005</url> </reference> <reference refNo="13"> <text>Claudio Di Ciccio, Fabrizio Maria Maggi, Marco Montali, and Jan Mendling. Ensuring model consistency in declarative process discovery. In BPM, volume 9253 of Lecture Notes in Computer Science, pages 144-159. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-23063-4_9.</text> <url>https://doi.org/10.1007/978-3-319-23063-4_9</url> </reference> <reference refNo="14"> <text>Claudio Di Ciccio and Massimo Mecella. On the discovery of declarative control flows for artful processes. ACM Trans. Manag. Inf. Syst., 5(4):24:1-24:37, 2015. URL: https://doi.org/10.1145/2629447.</text> <url>https://doi.org/10.1145/2629447</url> </reference> <reference refNo="15"> <text>Claudio Di Ciccio and Marco Montali. Declarative process specifications: Reasoning, discovery, monitoring. In Process Mining Handbook, volume 448 of Lecture Notes in Business Information Processing, pages 108-152. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-08848-3_4.</text> <url>https://doi.org/10.1007/978-3-031-08848-3_4</url> </reference> <reference refNo="16"> <text>Marlon Dumas and Arthur H. M. ter Hofstede. UML activity diagrams as a workflow specification language. In UML, volume 2185 of Lecture Notes in Computer Science, pages 76-90. Springer, 2001. URL: https://doi.org/10.1007/3-540-45441-1_7.</text> <url>https://doi.org/10.1007/3-540-45441-1_7</url> </reference> <reference refNo="17"> <text>Bernd Finkbeiner and Henny Sipma. Checking finite traces using alternating automata. Form.Meth.Syst.Des., 24(2):101-127, 2004. URL: https://doi.org/10.1023/B:FORM.0000017718.28096.48.</text> <url>https://doi.org/10.1023/B:FORM.0000017718.28096.48</url> </reference> <reference refNo="18"> <text>Valeria Fionda and Gianluigi Greco. The complexity of LTL on finite traces: Hard and easy fragments. In AAAI, pages 971-977. AAAI Press, 2016. URL: https://doi.org/10.1609/AAAI.V30I1.10104.</text> <url>https://doi.org/10.1609/AAAI.V30I1.10104</url> </reference> <reference refNo="19"> <text>Valeria Fionda and Gianluigi Greco. LTL on finite and process traces: Complexity results and a practical reasoner. J. Artif. Intell. Res., 63:557-623, 2018. URL: https://doi.org/10.1613/JAIR.1.11256.</text> <url>https://doi.org/10.1613/JAIR.1.11256</url> </reference> <reference refNo="20"> <text>Jean-Raphaël Gaglione, Daniel Neider, Rajarshi Roy, Ufuk Topcu, and Zhe Xu. Learning linear temporal properties from noisy data: A maxsat-based approach. In ATVA, volume 12971 of Lecture Notes in Computer Science, pages 74-90. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-88885-5_6.</text> <url>https://doi.org/10.1007/978-3-030-88885-5_6</url> </reference> <reference refNo="21"> <text>Bhaskar Kumar Ghosh and Pranab Kumar Sen. Handbook of sequential analysis. CRC Press, 1991.</text> <url/> </reference> <reference refNo="22"> <text>Ben Greenman, Sam Saarinen, Tim Nelson, and Shriram Krishnamurthi. Little tricky logic: Misconceptions in the understanding of LTL. Art Sci. Eng. Program., 7(2), 2023. URL: https://doi.org/10.22152/PROGRAMMING-JOURNAL.ORG/2023/7/7.</text> <url>https://doi.org/10.22152/PROGRAMMING-JOURNAL.ORG/2023/7/7</url> </reference> <reference refNo="23"> <text>Object Management Group. Business process model and notation (bpmn), version 2.0.2, 2014. URL: www.omg.org/spec/BPMN.</text> <url>www.omg.org/spec/BPMN</url> </reference> <reference refNo="24"> <text>Malte Helmert. The fast downward planning system. J. Artif. Intell. Res., 26:191-246, 2006. URL: https://doi.org/10.1613/JAIR.1705.</text> <url>https://doi.org/10.1613/JAIR.1705</url> </reference> <reference refNo="25"> <text>Caroline Lemieux, Dennis Park, and Ivan Beschastnikh. General LTL specification mining (T). In ASE, pages 81-92. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/ASE.2015.71.</text> <url>https://doi.org/10.1109/ASE.2015.71</url> </reference> <reference refNo="26"> <text>Fabrizio Maria Maggi, R. P. Jagadeesh Chandra Bose, and Wil M. P. van der Aalst. Efficient discovery of understandable declarative process models from event logs. In CAiSE, volume 7328 of Lecture Notes in Computer Science, pages 270-285. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31095-9_18.</text> <url>https://doi.org/10.1007/978-3-642-31095-9_18</url> </reference> <reference refNo="27"> <text>Fabrizio Maria Maggi, Claudio Di Ciccio, Chiara Di Francescomarino, and Taavi Kala. Parallel algorithms for the automated discovery of declarative process models. Inf. Syst., 74(Part):136-152, 2018. URL: https://doi.org/10.1016/J.IS.2017.12.002.</text> <url>https://doi.org/10.1016/J.IS.2017.12.002</url> </reference> <reference refNo="28"> <text>Maja Pesic, Helen Schonenberg, and Wil M. P. van der Aalst. DECLARE: full support for loosely-structured processes. In EDOC, pages 287-300. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/EDOC.2007.14.</text> <url>https://doi.org/10.1109/EDOC.2007.14</url> </reference> <reference refNo="29"> <text>Amir Pnueli. The temporal logic of programs. In FOCS, pages 46-57. IEEE Computer Society, 1977. URL: https://doi.org/10.1109/SFCS.1977.32.</text> <url>https://doi.org/10.1109/SFCS.1977.32</url> </reference> <reference refNo="30"> <text>Steve Prestwich. Robust constraint acquisition by sequential analysis. In ECAI, volume 325 of Frontiers in Artificial Intelligence and Applications, pages 355-362. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200113.</text> <url>https://doi.org/10.3233/FAIA200113</url> </reference> <reference refNo="31"> <text>Steven Prestwich and Nic Wilson. A statistical approach to learning constraints. International Journal of Approximate Reasoning, 2024.</text> <url/> </reference> <reference refNo="32"> <text>Rajarshi Roy, Jean-Raphaël Gaglione, Nasim Baharisangari, Daniel Neider, Zhe Xu, and Ufuk Topcu. Learning interpretable temporal properties from positive examples only. In AAAI, pages 6507-6515. AAAI Press, 2023. URL: https://doi.org/10.1609/AAAI.V37I5.25800.</text> <url>https://doi.org/10.1609/AAAI.V37I5.25800</url> </reference> <reference refNo="33"> <text>Tijs Slaats, Søren Debois, and Christoffer Olling Back. Weighing the pros and cons: Process discovery with negative examples. In BPM, volume 12875 of Lecture Notes in Computer Science, pages 47-64. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-85469-0_6.</text> <url>https://doi.org/10.1007/978-3-030-85469-0_6</url> </reference> <reference refNo="34"> <text>Wil M. P. van der Aalst. The application of petri nets to workflow management. J. Circuits Syst. Comput., 8(1):21-66, 1998. URL: https://doi.org/10.1142/S0218126698000043.</text> <url>https://doi.org/10.1142/S0218126698000043</url> </reference> <reference refNo="35"> <text>Wil M. P. van der Aalst. Foundations of process discovery. In Process Mining Handbook, volume 448 of Lecture Notes in Business Information Processing, pages 37-75. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-08848-3_2.</text> <url>https://doi.org/10.1007/978-3-031-08848-3_2</url> </reference> <reference refNo="36"> <text>Wil M. P. van der Aalst. Process mining: A 360 degree overview. In Process Mining Handbook, volume 448 of Lecture Notes in Business Information Processing, pages 3-34. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-08848-3_1.</text> <url>https://doi.org/10.1007/978-3-031-08848-3_1</url> </reference> <reference refNo="37"> <text>Wil M. P. van der Aalst, Maja Pesic, and Helen Schonenberg. Declarative workflows: Balancing between flexibility and support. Comput. Sci. Res. Dev., 23(2):99-113, 2009. URL: https://doi.org/10.1007/S00450-009-0057-9.</text> <url>https://doi.org/10.1007/S00450-009-0057-9</url> </reference> <reference refNo="38"> <text>Wil M. P. van der Aalst and Christian Stahl. Modeling Business Processes - A Petri Net-Oriented Approach. Cooperative Information Systems series. MIT Press, 2011.</text> <url/> </reference> <reference refNo="39"> <text>A Wald. Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2):117-186, 1945.</text> <url/> </reference> <reference refNo="40"> <text>Mathias Weske. Business Process Management - Concepts, Languages, Architectures, Third Edition. Springer, 2019. URL: https://doi.org/10.1007/978-3-662-59432-2.</text> <url>https://doi.org/10.1007/978-3-662-59432-2</url> </reference> <copyright>Francesco Chiariello</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="15"> <title>A Framework for Assessing Inconsistency in Disjunctive Temporal Problems</title> <abstract>Inconsistency measures serve to quantify the level of contradiction present within a knowledge base. They can be used for both consistency restoration and information extraction. In this article, we specifically explore inconsistency measures applicable to Disjunctive Temporal Problems (DTPs). We present a framework that extends traditional propositional logic approaches to DTPs, incorporating both new postulates and adaptations of existing ones. We identify and elaborate on various properties that establish relationships among these postulates. Furthermore, we introduce multiple inconsistency measures, adopting both a conventional approach that particularly leverages Minimal Inconsistent Subsets and a DTP-specific strategy based on constraint relaxation. Finally, we show the applicability of the inconsistency measures in DTPs through two real-world applications.</abstract> <keyword>Disjunctive Temporal Problems</keyword> <keyword>Inconsistency Measures</keyword> <keyword>Temporal Reasoning</keyword> <subjectClassification acmID="10010147.10010178.10010187.10010193">Computing methodologies~Temporal reasoning</subjectClassification> <pages>15:1-15:18</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Jean-François</firstName> <lastName>Condotta</lastName> <name>Jean-François Condotta</name> <affiliation>CRIL UMR 8188, Université d'Artois &amp; CNRS, Lens, France</affiliation> <homepageUrl>http://www.cril.univ-artois.fr/~condotta</homepageUrl> <orcid>https://orcid.org/0000-0002-7321-7855</orcid> </author> <author> <firstName>Yakoub</firstName> <lastName>Salhi</lastName> <name>Yakoub Salhi</name> <affiliation>CRIL UMR 8188, Université d'Artois &amp; CNRS, Lens, France</affiliation> <homepageUrl>http://www.cril.univ-artois.fr/~salhi</homepageUrl> <orcid>https://orcid.org/0000-0003-0100-4428</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.15</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>James F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM, 26(11):832-843, 1983. URL: https://doi.org/10.1145/182.358434.</text> <url>https://doi.org/10.1145/182.358434</url> </reference> <reference refNo="2"> <text>Meriem Ammoura, Yakoub Salhi, Brahim Oukacha, and Badran Raddaoui. On an MCS-based inconsistency measure. Int. J. Approx. Reasoning, 80:443-459, 2017. URL: https://doi.org/10.1016/J.IJAR.2016.06.004.</text> <url>https://doi.org/10.1016/J.IJAR.2016.06.004</url> </reference> <reference refNo="3"> <text>Philippe Besnard. Revisiting postulates for inconsistency measures. In Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, pages 383-396. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-11558-0_27.</text> <url>https://doi.org/10.1007/978-3-319-11558-0_27</url> </reference> <reference refNo="4"> <text>Glauber De Bona, John Grant, Anthony Hunter, and Sébastien Konieczny. Classifying inconsistency measures using graphs. J. Artif. Intell. Res., 66:937-987, 2019. URL: https://doi.org/10.1613/JAIR.1.11852.</text> <url>https://doi.org/10.1613/JAIR.1.11852</url> </reference> <reference refNo="5"> <text>Jean-François Condotta. The augmented interval and rectangle networks. In Anthony G. Cohn, Fausto Giunchiglia, and Bart Selman, editors, KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000, pages 571-579. Morgan Kaufmann, 2000.</text> <url/> </reference> <reference refNo="6"> <text>Carl Corea, John Grant, and Matthias Thimm. Measuring Inconsistency in Declarative Process Specifications. In Business Process Management - 20th International Conference, BPM 2022, Münster, Germany, September 11-16, 2022, Proceedings, volume 13420 of Lecture Notes in Computer Science, pages 289-306. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-16103-2_20.</text> <url>https://doi.org/10.1007/978-3-031-16103-2_20</url> </reference> <reference refNo="7"> <text>Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artif. Intell., 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.</text> <url>https://doi.org/10.1016/0004-3702(91)90006-6</url> </reference> <reference refNo="8"> <text>John Grant and Anthony Hunter. Measuring the good and the bad in inconsistent information. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 2632-2637. IJCAI/AAAI, 2011. URL: https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-438.</text> <url>https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-438</url> </reference> <reference refNo="9"> <text>John Grant and Francesco Parisi. On measuring inconsistency in graph databases with regular path constraints. Artif. Intell., 335:104197, 2024. URL: https://doi.org/10.1016/J.ARTINT.2024.104197.</text> <url>https://doi.org/10.1016/J.ARTINT.2024.104197</url> </reference> <reference refNo="10"> <text>Anthony Hunter and Sébastien Konieczny. On the measure of conflicts: Shapley Inconsistency Values. Artif. Intell., 174(14):1007-1026, 2010. URL: https://doi.org/10.1016/J.ARTINT.2010.06.001.</text> <url>https://doi.org/10.1016/J.ARTINT.2010.06.001</url> </reference> <reference refNo="11"> <text>Itay Meiri. Combining qualitative and quantitative constraints in temporal reasoning. Artif. Intell., 87(1-2):343-385, 1996. URL: https://doi.org/10.1016/0004-3702(95)00109-3.</text> <url>https://doi.org/10.1016/0004-3702(95)00109-3</url> </reference> <reference refNo="12"> <text>Paul H. Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In Bernhard Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, pages 494-502. Morgan Kaufmann, 2001.</text> <url/> </reference> <reference refNo="13"> <text>Francesco Parisi and John Grant. On measuring inconsistency in definite and indefinite databases with denial constraints. Artificial Intelligence, 318:103884, 2023. URL: https://doi.org/10.1016/J.ARTINT.2023.103884.</text> <url>https://doi.org/10.1016/J.ARTINT.2023.103884</url> </reference> <reference refNo="14"> <text>Yakoub Salhi. Inconsistency Measurement for Improving Logical Formula Clustering. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 1891-1897. ijcai.org, 2020. URL: https://doi.org/10.24963/IJCAI.2020/262.</text> <url>https://doi.org/10.24963/IJCAI.2020/262</url> </reference> <reference refNo="15"> <text>Yakoub Salhi. Inconsistency measurement for paraconsistent inference. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2033-2039. ijcai.org, 2021. URL: https://doi.org/10.24963/IJCAI.2021/280.</text> <url>https://doi.org/10.24963/IJCAI.2021/280</url> </reference> <reference refNo="16"> <text>Yakoub Salhi and Michael Sioutis. A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023, Rhodes, Greece, September 2-8, 2023, pages 604-613, 2023. URL: https://doi.org/10.24963/KR.2023/59.</text> <url>https://doi.org/10.24963/KR.2023/59</url> </reference> <reference refNo="17"> <text>Yakoub Salhi and Michael Sioutis. A Paraconsistency Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning. In ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023), volume 372 of Frontiers in Artificial Intelligence and Applications, pages 2049-2056. IOS Press, 2023. URL: https://doi.org/10.3233/FAIA230498.</text> <url>https://doi.org/10.3233/FAIA230498</url> </reference> <reference refNo="18"> <text>Kostas Stergiou and Manolis Koubarakis. Backtracking algorithms for disjunctions of temporal constraints. Artif. Intell., 120(1):81-117, 2000. URL: https://doi.org/10.1016/S0004-3702(00)00019-9.</text> <url>https://doi.org/10.1016/S0004-3702(00)00019-9</url> </reference> <reference refNo="19"> <text>Matthias Thimm. On the evaluation of inconsistency measures. In John Grant and Maria Vanina Martinez, editors, Measuring Inconsistency in Information, volume 73 of Studies in Logic. College Publications, February 2018.</text> <url/> </reference> <reference refNo="20"> <text>Ioannis Tsamardinos, Thierry Vidal, and Martha E. Pollack. CTP: A new constraint-based formalism for conditional, temporal planning. Constraints An Int. J., 8(4):365-388, 2003. URL: https://doi.org/10.1023/A:1025894003623.</text> <url>https://doi.org/10.1023/A:1025894003623</url> </reference> <copyright>Jean-François Condotta and Yakoub Salhi</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="16"> <title>Real-Time Higher-Order Recursion Schemes</title> <abstract>Higher-Order Recursion Schemes (HORS) have long been studied as a tool to model functional programs. Model-checking the tree generated by a HORS of order k against a parity automaton is known to be k-EXPTIME-complete. This paper introduces timed HORS, a real-time version of HORS in the sense of Alur/Dill'90, to be model-checked against a pair of a parity automaton and a timed automaton. We show that adding dense linear time to the notion of recursion schemes adds one exponential to the cost of model-checking, i.e., model-checking a timed HORS of order k can be done in (k+1)-EXPTIME. This is shown by an adaption of the region-graph construction known from the model-checking of timed CTL. We also obtain a hardness result for k = 1, but we strongly conjecture that it holds for all k. This result is obtained by encoding runs of 2-EXPTIME Turing machines into the trees generated by timed HORS.</abstract> <keyword>Timed Automata</keyword> <keyword>Higher-Order Recursion Schemes</keyword> <keyword>Tree Automata</keyword> <subjectClassification acmID="10003752.10003753.10003765">Theory of computation~Timed and hybrid models</subjectClassification> <subjectClassification acmID="10003752.10003766.10003772">Theory of computation~Tree languages</subjectClassification> <subjectClassification acmID="10003752.10003766.10003770">Theory of computation~Automata over infinite objects</subjectClassification> <pages>16:1-16:20</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Eric</firstName> <lastName>Alsmann</lastName> <name>Eric Alsmann</name> <affiliation>University of Kassel, Germany</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-2603-7827</orcid> </author> <author> <firstName>Florian</firstName> <lastName>Bruse</lastName> <name>Florian Bruse</name> <affiliation>University of Kassel, Germany</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-6800-7135</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.16</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Rajeev Alur, Costas Courcoubetis, and David L. Dill. Model-checking in dense real-time. Information and Computation, 104(1):2-34, 1993. URL: https://doi.org/10.1006/inco.1993.1024.</text> <url>https://doi.org/10.1006/inco.1993.1024</url> </reference> <reference refNo="2"> <text>Rajeev Alur and David L. Dill. Automata for modeling real-time systems. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 322-335. Springer, 1990. URL: https://doi.org/10.1007/BFB0032042.</text> <url>https://doi.org/10.1007/BFB0032042</url> </reference> <reference refNo="3"> <text>Rajeev Alur and P. Madhusudan. Decision problems for timed automata: A survey. In Marco Bernardo and Flavio Corradini, editors, Formal Methods for the Design of Real-Time Systems, International School on Formal Methods for the Design of Computer, Communication and Software Systems, SFM-RT 2004, Bertinoro, Italy, September 13-18, 2004, Revised Lectures, volume 3185 of Lecture Notes in Computer Science, pages 1-24. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30080-9_1.</text> <url>https://doi.org/10.1007/978-3-540-30080-9_1</url> </reference> <reference refNo="4"> <text>Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008.</text> <url/> </reference> <reference refNo="5"> <text>Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, and Olivier Serre. C-shore: a collapsible approach to higher-order verification. In Greg Morrisett and Tarmo Uustalu, editors, ACM SIGPLAN International Conference on Functional Programming, ICFP'13, Boston, MA, USA - September 25 - 27, 2013, pages 13-24. ACM, 2013. URL: https://doi.org/10.1145/2500365.2500589.</text> <url>https://doi.org/10.1145/2500365.2500589</url> </reference> <reference refNo="6"> <text>Christopher H. Broadbent and Naoki Kobayashi. Saturation-based model checking of higher-order recursion schemes. In Simona Ronchi Della Rocca, editor, Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, volume 23 of LIPIcs, pages 129-148. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: https://doi.org/10.4230/LIPICS.CSL.2013.129.</text> <url>https://doi.org/10.4230/LIPICS.CSL.2013.129</url> </reference> <reference refNo="7"> <text>Florian Bruse. Space-efficient model-checking of higher-order recursion schemes. manuscript submitted.</text> <url/> </reference> <reference refNo="8"> <text>Florian Bruse and Martin Lange. Temporal logic with recursion. Inf. Comput., 281:104804, 2021. URL: https://doi.org/10.1016/J.IC.2021.104804.</text> <url>https://doi.org/10.1016/J.IC.2021.104804</url> </reference> <reference refNo="9"> <text>Florian Bruse and Martin Lange. The tail-recursive fragment of timed recursive CTL. Inf. Comput., 294:105084, 2023. URL: https://doi.org/10.1016/J.IC.2023.105084.</text> <url>https://doi.org/10.1016/J.IC.2023.105084</url> </reference> <reference refNo="10"> <text>Florian Bruse and Martin Lange. Model checking timed recursive CTL. Inf. Comput., 298:105168, 2024. URL: https://doi.org/10.1016/J.IC.2024.105168.</text> <url>https://doi.org/10.1016/J.IC.2024.105168</url> </reference> <reference refNo="11"> <text>Florian Bruse, Martin Lange, and Étienne Lozes. Space-efficient fragments of higher-order fixpoint logic. In Matthew Hague and Igor Potapov, editors, Reachability Problems - 11th International Workshop, RP 2017, London, UK, September 7-9, 2017, Proceedings, volume 10506 of Lecture Notes in Computer Science, pages 26-41. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-67089-8_3.</text> <url>https://doi.org/10.1007/978-3-319-67089-8_3</url> </reference> <reference refNo="12"> <text>Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. URL: https://doi.org/10.1145/322234.322243.</text> <url>https://doi.org/10.1145/322234.322243</url> </reference> <reference refNo="13"> <text>Werner Damm. The IO- and oi-hierarchies. Theor. Comput. Sci., 20:95-207, 1982. URL: https://doi.org/10.1016/0304-3975(82)90009-3.</text> <url>https://doi.org/10.1016/0304-3975(82)90009-3</url> </reference> <reference refNo="14"> <text>Gérard Huet. Résolution d'Équations dans des Langages d'Order 1, 2., ω. PhD thesis, Universite de Paris VII, 1976.</text> <url/> </reference> <reference refNo="15"> <text>Marcin Jurdzinski. Small progress measures for solving parity games. In Horst Reichel and Sophie Tison, editors, STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings, volume 1770 of Lecture Notes in Computer Science, pages 290-301. Springer, 2000. URL: https://doi.org/10.1007/3-540-46541-3_24.</text> <url>https://doi.org/10.1007/3-540-46541-3_24</url> </reference> <reference refNo="16"> <text>Teodor Knapik, Damian Niwinski, and Pawel Urzyczyn. Higher-order pushdown trees are easy. In Mogens Nielsen and Uffe Engberg, editors, Foundations of Software Science and Computation Structures, 5th International Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002 Grenoble, France, April 8-12, 2002, Proceedings, volume 2303 of Lecture Notes in Computer Science, pages 205-222. Springer, 2002. URL: https://doi.org/10.1007/3-540-45931-6_15.</text> <url>https://doi.org/10.1007/3-540-45931-6_15</url> </reference> <reference refNo="17"> <text>Naoki Kobayashi. Model checking higher-order programs. J. ACM, 60(3):20:1-20:62, 2013. URL: https://doi.org/10.1145/2487241.2487246.</text> <url>https://doi.org/10.1145/2487241.2487246</url> </reference> <reference refNo="18"> <text>Naoki Kobayashi, Étienne Lozes, and Florian Bruse. On the relationship between higher-order recursion schemes and higher-order fixpoint logic. In Giuseppe Castagna and Andrew D. Gordon, editors, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, pages 246-259. ACM, 2017. URL: https://doi.org/10.1145/3009837.3009854.</text> <url>https://doi.org/10.1145/3009837.3009854</url> </reference> <reference refNo="19"> <text>Naoki Kobayashi and C.-H. Luke Ong. A type system equivalent to the modal mu-calculus model checking of higher-order recursion schemes. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, pages 179-188. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/LICS.2009.29.</text> <url>https://doi.org/10.1109/LICS.2009.29</url> </reference> <reference refNo="20"> <text>C.-H. Luke Ong. On model-checking trees generated by higher-order recursion schemes. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 81-90. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/LICS.2006.38.</text> <url>https://doi.org/10.1109/LICS.2006.38</url> </reference> <copyright>Eric Alsmann and Florian Bruse</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="17"> <title>Time Series Anomaly Detection Leveraging MSE Feedback with AutoEncoder and RNN</title> <abstract>Anomaly detection in time series data is a critical task in various domains, including finance, healthcare, cybersecurity and industry. Traditional methods, such as time series decomposition, clustering, and density estimation, have provided robust solutions for identifying anomalies that exhibit distinct patterns or significant deviations from normal data distributions. Recent advancements in machine learning and deep learning have further enhanced these capabilities. This paper introduces a novel method for anomaly detection that combines the strengths of autoencoders and recurrent neural networks (RNNs) with an reconstruction error feedback mechanism based on Mean Squared Error. We compare our method against classical techniques and recent approaches like OmniAnomaly, which leverages stochastic recurrent neural networks, and the Anomaly Transformer, which introduces association discrepancy to capture long-range dependencies and DCDetector using contrastive representation learning with multi-scale dual attention. Experimental results demonstrate that our method achieves superior overall performance in terms of precision, recall, and F1 score. The source code is available at http://github.com/mribrahim/AE-FAR</abstract> <keyword>Time series</keyword> <keyword>Anomaly</keyword> <keyword>Neural networks</keyword> <subjectClassification acmID="10010147.10010257.10010321">Computing methodologies~Machine learning algorithms</subjectClassification> <pages>17:1-17:12</pages> <category>Regular Paper</category> <supplements> <url category="Software">https://github.com/mribrahim/AE-FAR/</url> </supplements> <acknowledgements/> <author> <firstName>Ibrahim</firstName> <lastName>Delibasoglu</lastName> <name>Ibrahim Delibasoglu</name> <affiliation>Department of Computer and Information Science (IDA), Linköping University, Sweden</affiliation> <affiliation>Software Engineering, Sakarya University, Turkey</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-8119-2873</orcid> </author> <author> <firstName>Fredrik</firstName> <lastName>Heintz</lastName> <name>Fredrik Heintz</name> <affiliation>Department of Computer and Information Science (IDA), Linköping University, Sweden</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-9595-2471</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.17</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Archana Anandakrishnan, Senthil Kumar, Alexander Statnikov, Tanveer Faruquie, and Di Xu. Anomaly detection in finance: editors’ introduction. In KDD 2017 Workshop on Anomaly Detection in Finance, pages 1-7. PMLR, 2018.</text> <url/> </reference> <reference refNo="2"> <text>Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93-104, 2000. URL: https://doi.org/10.1145/342009.335388.</text> <url>https://doi.org/10.1145/342009.335388</url> </reference> <reference refNo="3"> <text>Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912-9924, 2020.</text> <url/> </reference> <reference refNo="4"> <text>Cristian I Challu, Peihong Jiang, Ying Nian Wu, and Laurent Callot. Deep generative model with hierarchical latent factors for time series anomaly detection. In International Conference on Artificial Intelligence and Statistics, pages 1643-1654. PMLR, 2022. URL: https://proceedings.mlr.press/v151/challu22a.html.</text> <url>https://proceedings.mlr.press/v151/challu22a.html</url> </reference> <reference refNo="5"> <text>Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020. URL: http://proceedings.mlr.press/v119/chen20j.html.</text> <url>http://proceedings.mlr.press/v119/chen20j.html</url> </reference> <reference refNo="6"> <text>Ailin Deng and Bryan Hooi. Graph neural network-based anomaly detection in multivariate time series. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 4027-4035, 2021. URL: https://doi.org/10.1609/AAAI.V35I5.16523.</text> <url>https://doi.org/10.1609/AAAI.V35I5.16523</url> </reference> <reference refNo="7"> <text>Kyle Hundman, Valentino Constantinou, Christopher Laporte, Ian Colwell, and Tom Soderstrom. Detecting spacecraft anomalies using lstms and nonparametric dynamic thresholding. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery &amp; data mining, pages 387-395, 2018.</text> <url/> </reference> <reference refNo="8"> <text>Bedeuro Kim, Mohsen Ali Alawami, Eunsoo Kim, Sanghak Oh, Jeongyong Park, and Hyoungshick Kim. A comparative study of time series anomaly detection models for industrial control systems. Sensors, 23(3):1310, 2023. URL: https://doi.org/10.3390/S23031310.</text> <url>https://doi.org/10.3390/S23031310</url> </reference> <reference refNo="9"> <text>Dan Li, Dacheng Chen, Baihong Jin, Lei Shi, Jonathan Goh, and See-Kiong Ng. Mad-gan: Multivariate anomaly detection for time series data with generative adversarial networks. In International conference on artificial neural networks, pages 703-716. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30490-4_56.</text> <url>https://doi.org/10.1007/978-3-030-30490-4_56</url> </reference> <reference refNo="10"> <text>Zhihan Li, Youjian Zhao, Jiaqi Han, Ya Su, Rui Jiao, Xidao Wen, and Dan Pei. Multivariate time series anomaly detection and interpretation using hierarchical inter-metric and temporal embedding. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery &amp; data mining, pages 3220-3230, 2021. URL: https://doi.org/10.1145/3447548.3467075.</text> <url>https://doi.org/10.1145/3447548.3467075</url> </reference> <reference refNo="11"> <text>Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 eighth ieee international conference on data mining, pages 413-422. IEEE, 2008. URL: https://doi.org/10.1109/ICDM.2008.17.</text> <url>https://doi.org/10.1109/ICDM.2008.17</url> </reference> <reference refNo="12"> <text>Aditya P Mathur and Nils Ole Tippenhauer. Swat: A water treatment testbed for research and training on ics security. In 2016 international workshop on cyber-physical systems for smart water networks (CySWater), pages 31-36. IEEE, 2016. URL: https://doi.org/10.1109/CYSWATER.2016.7469060.</text> <url>https://doi.org/10.1109/CYSWATER.2016.7469060</url> </reference> <reference refNo="13"> <text>Daehyung Park, Yuuna Hoshi, and Charles C Kemp. A multimodal anomaly detector for robot-assisted feeding using an lstm-based variational autoencoder. IEEE Robotics and Automation Letters, 3(3):1544-1551, 2018. URL: https://doi.org/10.1109/LRA.2018.2801475.</text> <url>https://doi.org/10.1109/LRA.2018.2801475</url> </reference> <reference refNo="14"> <text>Chitta Ranjan, Mahendranath Reddy, Markku Mustonen, Kamran Paynabar, and Karim Pourak. Dataset: rare event classification in multivariate time series. arXiv preprint arXiv:1809.10717, 2018.</text> <url/> </reference> <reference refNo="15"> <text>Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In International conference on machine learning, pages 4393-4402. PMLR, 2018.</text> <url/> </reference> <reference refNo="16"> <text>Youjin Shin, Sangyup Lee, Shahroz Tariq, Myeong Shin Lee, Okchul Jung, Daewon Chung, and Simon S Woo. Itad: integrative tensor-based anomaly detection system for reducing false positives of satellite systems. In Proceedings of the 29th ACM international conference on information &amp; knowledge management, pages 2733-2740, 2020. URL: https://doi.org/10.1145/3340531.3412716.</text> <url>https://doi.org/10.1145/3340531.3412716</url> </reference> <reference refNo="17"> <text>Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. Robust anomaly detection for multivariate time series through stochastic recurrent neural network. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery &amp; data mining, pages 2828-2837, 2019. URL: https://doi.org/10.1145/3292500.3330672.</text> <url>https://doi.org/10.1145/3292500.3330672</url> </reference> <reference refNo="18"> <text>Shahroz Tariq, Sangyup Lee, Youjin Shin, Myeong Shin Lee, Okchul Jung, Daewon Chung, and Simon S Woo. Detecting anomalies in space using multivariate convolutional lstm with mixtures of probabilistic pca. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery &amp; data mining, pages 2123-2133, 2019. URL: https://doi.org/10.1145/3292500.3330776.</text> <url>https://doi.org/10.1145/3292500.3330776</url> </reference> <reference refNo="19"> <text>Lawrence C Wong. Time Series Anomaly Detection using Prediction-Reconstruction Mixture Errors. PhD thesis, Massachusetts Institute of Technology, 2022.</text> <url/> </reference> <reference refNo="20"> <text>Jiehui Xu, Haixu Wu, Jianmin Wang, and Mingsheng Long. Anomaly transformer: Time series anomaly detection with association discrepancy. arXiv preprint arXiv:2110.02642, 2021. URL: https://arxiv.org/abs/2110.02642.</text> <url>https://arxiv.org/abs/2110.02642</url> </reference> <reference refNo="21"> <text>Yiyuan Yang, Chaoli Zhang, Tian Zhou, Qingsong Wen, and Liang Sun. Dcdetector: Dual attention contrastive representation learning for time series anomaly detection. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3033-3045, 2023. URL: https://doi.org/10.1145/3580305.3599295.</text> <url>https://doi.org/10.1145/3580305.3599295</url> </reference> <reference refNo="22"> <text>Hang Zhao, Yujing Wang, Juanyong Duan, Congrui Huang, Defu Cao, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Multivariate time-series anomaly detection via graph attention network. In 2020 IEEE International Conference on Data Mining (ICDM), pages 841-850. IEEE, 2020. URL: https://doi.org/10.1109/ICDM50108.2020.00093.</text> <url>https://doi.org/10.1109/ICDM50108.2020.00093</url> </reference> <reference refNo="23"> <text>Bin Zhou, Shenghua Liu, Bryan Hooi, Xueqi Cheng, and Jing Ye. Beatgan: Anomalous rhythm detection using adversarially generated time series. In IJCAI, volume 2019, pages 4433-4439, 2019. URL: https://doi.org/10.24963/IJCAI.2019/616.</text> <url>https://doi.org/10.24963/IJCAI.2019/616</url> </reference> <reference refNo="24"> <text>Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Daeki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In International conference on learning representations, 2018.</text> <url/> </reference> <copyright>Ibrahim Delibasoglu and Fredrik Heintz</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="18"> <title>Full Characterisation of Extended CTL*</title> <abstract>The precise identification of the expressive power of logic languages used in formal methods for specifying and verifying run-time properties of critical systems is a fundamental task and characterisation theorems play a crucial role as model-theoretic tools in this regard. While a clear picture of the expressive power of linear-time temporal logics in terms of word automata and predicate logics has long been established, a complete mapping of the corresponding relationships for branching-time temporal logics has proven to be a more elusive task over the past four decades with few scattered results. Only recently, an automata-theoretic characterisation of both CTL* and its full-ω-regular extension ECTL* has been provided in terms of Symmetric Hesitant Tree Automata (HTA), with and without a suitable counter-freeness restriction on their linear behaviours. These two temporal logics also correspond to the bisimulation-invariant semantic fragments of Monadic Path Logic (MPL) and Monadic Chain Logic (MCL), respectively. Additionally, it has been proven that the counting extensions of CTL* and ECTL*, namely CCTL* and CECTL*, enjoy equivalent graded versions of the HTAs for the corresponding non-counting logics. However, while Moller and Rabinovich have proved CCTL* to be equivalent to full MPL, thus filling the gap for the standard branching-time logic, no similar result has been given for CECTL*. This work completes the picture, by proving the expressive equivalence of CECTL* and full MCL, by means of a composition theorem for the latter logic. This also indirectly establishes the equivalence between HTAs and their first-order extensions HFTAs, as originally introduced by Walukiewicz.</abstract> <keyword>Branching-Time Temporal Logics</keyword> <keyword>Monadic Chain Logic</keyword> <keyword>Tree Automata</keyword> <subjectClassification acmID="10003752.10003766.10003770">Theory of computation~Automata over infinite objects</subjectClassification> <subjectClassification acmID="10003752.10003790.10003793">Theory of computation~Modal and temporal logics</subjectClassification> <subjectClassification acmID="10003752.10003766.10003772">Theory of computation~Tree languages</subjectClassification> <pages>18:1-18:18</pages> <category>Regular Paper</category> <funding>Indam GNCS 2024 project "Certificazione, Monitoraggio, ed Interpretabilità in Sistemi di Intelligenza Artificiale". M. Benerecetti, F. Mogavero, and A. Peron are members of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).</funding> <acknowledgements/> <author> <firstName>Massimo</firstName> <lastName>Benerecetti</lastName> <name>Massimo Benerecetti</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-4664-6061</orcid> </author> <author> <firstName>Laura</firstName> <lastName>Bozzelli</lastName> <name>Laura Bozzelli</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-0963-8169</orcid> </author> <author> <firstName>Fabio</firstName> <lastName>Mogavero</lastName> <name>Fabio Mogavero</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-5140-5783</orcid> </author> <author> <firstName>Adriano</firstName> <lastName>Peron</lastName> <name>Adriano Peron</name> <affiliation>Università di Trieste, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-7111-3171</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.18</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>A. Arnold and D. Niwiński. Fixed Point Characterization of Weak Monadic Logic Definable Sets of Trees. In Tree Automata and Languages, pages 159-188. North-Holland, 1992.</text> <url/> </reference> <reference refNo="2"> <text>M. Benerecetti, L. Bozzelli, F. Mogavero, and A. Peron. Quantifying over Trees in Monadic Second-Order Logic. In LICS'23, pages 1-13. IEEECS, 2023.</text> <url/> </reference> <reference refNo="3"> <text>M. Benerecetti, L. Bozzelli, F. Mogavero, and A. Peron. Automata-Theoretic Characterisations of Branching-Time Temporal Logics. In ICALP'24, LIPIcs 297, pages 128:1-20. Leibniz-Zentrum fuer Informatik, 2024.</text> <url/> </reference> <reference refNo="4"> <text>M. Benerecetti, F. Mogavero, and A. Murano. Substructure Temporal Logic. In LICS'13, pages 368-377. IEEECS, 2013.</text> <url/> </reference> <reference refNo="5"> <text>M. Benerecetti, F. Mogavero, and A. Murano. Reasoning About Substructures and Games. TOCL, 16(3):25:1-46, 2015.</text> <url/> </reference> <reference refNo="6"> <text>U. Boker, K. Lehtinen, and S. Sickert. On the Translation of Automata to Linear Temporal Logic. In FOSSACS'22, LNCS 13242, pages 140-160. Springer, 2022. URL: https://doi.org/10.1007/978-3-030-99253-8_8.</text> <url>https://doi.org/10.1007/978-3-030-99253-8_8</url> </reference> <reference refNo="7"> <text>J.R. Büchi. Weak Second-Order Arithmetic and Finite Automata. MLQ, 6(1-6):66-92, 1960.</text> <url/> </reference> <reference refNo="8"> <text>J.R. Büchi. On a Decision Method in Restricted Second-Order Arithmetic. In ICLMPS'62, pages 1-11. Stanford University Press, 1962.</text> <url/> </reference> <reference refNo="9"> <text>J.R. Büchi. On a Decision Method in Restricted Second Order Arithmetic. In Studies in Logic and the Foundations of Mathematics, volume 44, pages 1-11. Elsevier, 1966.</text> <url/> </reference> <reference refNo="10"> <text>Y. Choueka. Theories of Automata on ω-Tapes: A Simplified Approach. JCSS, 8(2):117-141, 1974.</text> <url/> </reference> <reference refNo="11"> <text>E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications: A Practical Approach. In POPL'83, pages 117-126. ACM, 1983.</text> <url/> </reference> <reference refNo="12"> <text>E.A. Emerson and E.M. Clarke. Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic. In LP'81, LNCS 131, pages 52-71. Springer, 1982.</text> <url/> </reference> <reference refNo="13"> <text>E.A. Emerson and J.Y. Halpern. "Sometimes" and "Not Never" Revisited: On Branching Versus Linear Time. In POPL'83, pages 127-140. ACM, 1983.</text> <url/> </reference> <reference refNo="14"> <text>E.A. Emerson and J.Y. Halpern. "Sometimes" and "Not Never" Revisited: On Branching Versus Linear Time. JACM, 33(1):151-178, 1986.</text> <url/> </reference> <reference refNo="15"> <text>S. Feferman and R. Vaught. The First-Order Properties of Products of Algebraic Systems. FM, 47(1):57-103, 1959.</text> <url/> </reference> <reference refNo="16"> <text>K. Fine. In So Many Possible Worlds. NDJFL, 13:516-520, 1972. URL: https://doi.org/10.1305/NDJFL/1093890715.</text> <url>https://doi.org/10.1305/NDJFL/1093890715</url> </reference> <reference refNo="17"> <text>M.J. Fischer and R.E. Ladner. Propositional Dynamic Logic of Regular Programs. JCSS, 18(2):194-211, 1979. URL: https://doi.org/10.1016/0022-0000(79)90046-1.</text> <url>https://doi.org/10.1016/0022-0000(79)90046-1</url> </reference> <reference refNo="18"> <text>G. De Giacomo and M.Y. Vardi. Linear Temporal Logic and Linear Dynamic Logic on Finite Traces. In IJCAI'13, pages 854-860. IJCAI' &amp; AAAI Press, 2013.</text> <url/> </reference> <reference refNo="19"> <text>Y. Gurevich. Modest Theory of Short Chains. I. JSL, 44(4):481-490, 1979. URL: https://doi.org/10.2307/2273287.</text> <url>https://doi.org/10.2307/2273287</url> </reference> <reference refNo="20"> <text>Y. Gurevich. Monadic Second-Order Theories. In Model-Theoretical Logics, pages 479-506. Springer, 1985.</text> <url/> </reference> <reference refNo="21"> <text>Y. Gurevich and S. Shelah. Modest Theory of Short Chains. II. JSL, 44(4):491-502, 1979. URL: https://doi.org/10.2307/2273288.</text> <url>https://doi.org/10.2307/2273288</url> </reference> <reference refNo="22"> <text>Y. Gurevich and S. Shelah. Rabin’s Uniformization Problem. JSL, 48(4):1105-1119, 1979.</text> <url/> </reference> <reference refNo="23"> <text>Y. Gurevich and S. Shelah. The Decision Problem for Branching Time Logic. JSL, 50(3):668-681, 1985. URL: https://doi.org/10.2307/2274321.</text> <url>https://doi.org/10.2307/2274321</url> </reference> <reference refNo="24"> <text>T. Hafer and W. Thomas. Computation Tree Logic CTL* and Path Quantifiers in the Monadic Theory of the Binary Tree. In ICALP'87, LNCS 267, pages 269-279. Springer, 1987. URL: https://doi.org/10.1007/3-540-18088-5_22.</text> <url>https://doi.org/10.1007/3-540-18088-5_22</url> </reference> <reference refNo="25"> <text>D. Janin. A Contribution to Formal Methods: Games, Logic and Automata. Habilitation thesis, Université Bordeaux I, Bordeaux, France, 2005.</text> <url/> </reference> <reference refNo="26"> <text>D. Janin and G. Lenzi. On the Relationship Between Monadic and Weak Monadic Second Order Logic on Arbitrary Trees, with Applications to the mu-Calculus. FI, 61(3-4):247-265, 2004. URL: http://content.iospress.com/articles/fundamenta-informaticae/fi61-3-4-04.</text> <url>http://content.iospress.com/articles/fundamenta-informaticae/fi61-3-4-04</url> </reference> <reference refNo="27"> <text>D. Janin and I. Walukiewicz. On the Expressive Completeness of the Propositional mu-Calculus with Respect to Monadic Second Order Logic. In CONCUR'96, LNCS 1119, pages 263-277. Springer, 1996. URL: https://doi.org/10.1007/3-540-61604-7_60.</text> <url>https://doi.org/10.1007/3-540-61604-7_60</url> </reference> <reference refNo="28"> <text>H.W. Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, University of California, Los Angeles, CA, USA, 1968.</text> <url/> </reference> <reference refNo="29"> <text>D. Kozen. Results on the Propositional muCalculus. TCS, 27(3):333-354, 1983. URL: https://doi.org/10.1016/0304-3975(82)90125-6.</text> <url>https://doi.org/10.1016/0304-3975(82)90125-6</url> </reference> <reference refNo="30"> <text>R.E. Ladner. Application of Model Theoretic Games to Discrete Linear Orders and Finite Automata. IC, 33(4):281-303, 1977. URL: https://doi.org/10.1016/S0019-9958(77)90443-0.</text> <url>https://doi.org/10.1016/S0019-9958(77)90443-0</url> </reference> <reference refNo="31"> <text>H. Läuchli. A Decision Procedure for the Weak Second-Order Theory of Linear Order. In LC'66, volume 50, pages 189-197. North-Holland, 1968.</text> <url/> </reference> <reference refNo="32"> <text>O. Maler and A. Pnueli. On the Cascaded Decomposition of Automata, its Complexity, and its Application to Logic. Unpublished, 1995.</text> <url/> </reference> <reference refNo="33"> <text>Z. Manna and A. Pnueli. The Temporal Logic of Reactive and Concurrent Systems - Specification. Springer, 1992.</text> <url/> </reference> <reference refNo="34"> <text>Z. Manna and A. Pnueli. Temporal Verification of Reactive Systems - Safety. Springer, 1995.</text> <url/> </reference> <reference refNo="35"> <text>R. McNaughton. Testing and Generating Infinite Sequences by a Finite Automaton. IC, 9(5):521-530, 1966. URL: https://doi.org/10.1016/S0019-9958(66)80013-X.</text> <url>https://doi.org/10.1016/S0019-9958(66)80013-X</url> </reference> <reference refNo="36"> <text>R. McNaughton and S. Papert. Counter-Free Automata. MIT Press, 1971.</text> <url/> </reference> <reference refNo="37"> <text>F. Moller and A.M. Rabinovich. On the Expressive Power of CTL*. In LICS'99, pages 360-368. IEEECS, 1999.</text> <url/> </reference> <reference refNo="38"> <text>F. Moller and A.M. Rabinovich. Counting on CTL*: On the Expressive Power of Monadic Path Logic. IC, 184(1):147-159, 2003. URL: https://doi.org/10.1016/S0890-5401(03)00104-4.</text> <url>https://doi.org/10.1016/S0890-5401(03)00104-4</url> </reference> <reference refNo="39"> <text>D. Perrin and J. Pin. First-Order Logic and Star-Free Sets. JCSS, 32(3):393-406, 1986. URL: https://doi.org/10.1016/0022-0000(86)90037-1.</text> <url>https://doi.org/10.1016/0022-0000(86)90037-1</url> </reference> <reference refNo="40"> <text>A. Pnueli. The Temporal Logic of Programs. In FOCS'77, pages 46-57. IEEECS, 1977.</text> <url/> </reference> <reference refNo="41"> <text>A. Pnueli. The Temporal Semantics of Concurrent Programs. TCS, 13:45-60, 1981. URL: https://doi.org/10.1016/0304-3975(81)90110-9.</text> <url>https://doi.org/10.1016/0304-3975(81)90110-9</url> </reference> <reference refNo="42"> <text>S. Safra. On the Complexity of ω-Automata. In FOCS'88, pages 319-327. IEEECS, 1988.</text> <url/> </reference> <reference refNo="43"> <text>S. Shelah. The Monadic Theory of Order. AM, 102(3):379-419, 1975.</text> <url/> </reference> <reference refNo="44"> <text>W. Thomas. Star-Free Regular Sets of ω-Sequences. IC, 42(2):148-156, 1979.</text> <url/> </reference> <reference refNo="45"> <text>W. Thomas. A Combinatorial Approach to the Theory of ω-Automata. IC, 48(3):261-283, 1981.</text> <url/> </reference> <reference refNo="46"> <text>W. Thomas. Logical Aspects in the Study of Tree Languages. In CAAP'84, pages 31-50. CUP, 1984.</text> <url/> </reference> <reference refNo="47"> <text>W. Thomas. On Chain Logic, Path Logic, and First-Order Logic over Infinite Trees. In LICS'87, pages 245-256. IEEECS, 1987.</text> <url/> </reference> <reference refNo="48"> <text>W. Thomas. Automata on Infinite Objects. In Handbook of Theoretical Computer Science (vol. B), pages 133-191. MIT Press, 1990.</text> <url/> </reference> <reference refNo="49"> <text>J. van Benthem. Modal Correspondence Theory. PhD thesis, University of Amsterdam, Amsterdam, Netherlands, 1977.</text> <url/> </reference> <reference refNo="50"> <text>M.Y. Vardi and P. Wolper. Yet Another Process Logic. In LP'83, LNCS 164, pages 501-512. Springer, 1984.</text> <url/> </reference> <reference refNo="51"> <text>I. Walukiewicz. Monadic Second Order Logic on Tree-Like Structures. TCS, 275(1-2):311-346, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00185-2.</text> <url>https://doi.org/10.1016/S0304-3975(01)00185-2</url> </reference> <reference refNo="52"> <text>P. Wolper. Temporal Logic Can Be More Expressive. IC, 56(1-2):72-99, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80051-5.</text> <url>https://doi.org/10.1016/S0019-9958(83)80051-5</url> </reference> <copyright>Massimo Benerecetti, Laura Bozzelli, Fabio Mogavero, and Adriano Peron</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="19"> <title>Model Checking Linear Temporal Properties on Polyhedral Systems</title> <abstract>We study the problem of model checking linear temporal logic formulae on finite trajectories generated by polyhedral differential inclusions, thus enriching the landscape of models where such specifications can be effectively verified. Each model in the class comprises a static and a dynamic component. The static component features a finite set of observables represented by (non-necessarily convex) polyhedra. The dynamic one is given by a convex polyhedron constraining the dynamics of the system, by specifying the possible slopes of the trajectories in each time instant. We devise an exact algorithm that computes a symbolic representation of the region of points that existentially satisfy a given formula φ, i.e., the points from which there exists a trajectory satisfying φ.</abstract> <keyword>Model Checking</keyword> <keyword>Real-Time Systems</keyword> <keyword>LTLf</keyword> <keyword>RTLf</keyword> <subjectClassification acmID="10003752.10003790.10003793">Theory of computation~Modal and temporal logics</subjectClassification> <pages>19:1-19:23</pages> <category>Regular Paper</category> <funding>PNRR MUR project PE0000013-FAIR and Indam GNCS 2024 project "Certificazione, Monitoraggio, ed Interpretabilità in Sistemi di Intelligenza Artificiale". The authors are members of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).</funding> <acknowledgements/> <author> <firstName>Massimo</firstName> <lastName>Benerecetti</lastName> <name>Massimo Benerecetti</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-4664-6061</orcid> </author> <author> <firstName>Marco</firstName> <lastName>Faella</lastName> <name>Marco Faella</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-7617-5489</orcid> </author> <author> <firstName>Fabio</firstName> <lastName>Mogavero</lastName> <name>Fabio Mogavero</name> <affiliation>Università di Napoli Federico II, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-5140-5783</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.19</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>R. Alur and D.L. Dill. A theory of timed automata. Theoretical Computer Science, 126:183-235, 1994. URL: https://doi.org/10.1016/0304-3975(94)90010-8.</text> <url>https://doi.org/10.1016/0304-3975(94)90010-8</url> </reference> <reference refNo="2"> <text>R. Alur, T. Feder, and T.A. Henzinger. The benefits of relaxing punctuality. Journal of the ACM (JACM), 43(1):116-146, 1996. URL: https://doi.org/10.1145/227595.227602.</text> <url>https://doi.org/10.1145/227595.227602</url> </reference> <reference refNo="3"> <text>R. Alur, T.A. Henzinger, and P.-H. Ho. Automatic symbolic verification of embedded systems. IEEE Trans. Softw. Eng., 22:181-201, March 1996. URL: https://doi.org/10.1109/32.489079.</text> <url>https://doi.org/10.1109/32.489079</url> </reference> <reference refNo="4"> <text>R. Alur, A. Trivedi, and D. Wojtczak. Optimal scheduling for constant-rate multi-mode systems. In Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control, pages 75-84, 2012.</text> <url/> </reference> <reference refNo="5"> <text>R. Bagnara, P. M. Hill, and E. Zaffanella. The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Science of Computer Programming, 72(1-2):3-21, 2008. URL: https://doi.org/10.1016/j.scico.2007.08.001.</text> <url>https://doi.org/10.1016/j.scico.2007.08.001</url> </reference> <reference refNo="6"> <text>M. Benerecetti and M. Faella. Automatic synthesis of switching controllers for linear hybrid systems: Reachability control. ACM Trans. on Embedded Computing Systems, 16(4), 2017. URL: https://doi.org/10.1145/3047500.</text> <url>https://doi.org/10.1145/3047500</url> </reference> <reference refNo="7"> <text>M. Benerecetti, M. Faella, and S. Minopoli. Automatic synthesis of switching controllers for linear hybrid systems: Safety control. Theoretical Computer Science, 493:116-138, 2013. URL: https://doi.org/10.1016/J.TCS.2012.10.042.</text> <url>https://doi.org/10.1016/J.TCS.2012.10.042</url> </reference> <reference refNo="8"> <text>M. Blondin, P. Offtermatt, and A. Sansfaçon-Buchanan. Verifying linear temporal specifications of constant-rate multi-mode systems. In LICS, pages 1-13, 2023. URL: https://doi.org/10.1109/LICS56636.2023.10175721.</text> <url>https://doi.org/10.1109/LICS56636.2023.10175721</url> </reference> <reference refNo="9"> <text>E. Davis. Infinite loops in finite time: Some observations. In Proc. of the 3rd Int. Conf. on Principles of Knowledge Representation and Reasoning (KR'92). Cambridge, MA, USA, October 25-29, 1992, pages 47-58. Morgan Kaufmann, 1992.</text> <url/> </reference> <reference refNo="10"> <text>G. De Giacomo and M.Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 854-860. IJCAI/AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6997.</text> <url>http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6997</url> </reference> <reference refNo="11"> <text>A. Duret-Lutz, A. Lewkowicz, A. Fauchille, T. Michaud, E. Renault, and L. Xu. Spot 2.0—a framework for ltl and-automata manipulation. In International Symposium on Automated Technology for Verification and Analysis, pages 122-129. Springer, 2016.</text> <url/> </reference> <reference refNo="12"> <text>G. Frehse, C. Le Guernic, A. Donzé, S. Cotton, R. Ray, O. Lebeltel, R. Ripado, A. Girard, T. Dang, and O. Maler. Spaceex: Scalable verification of hybrid systems. In CAV 11: Proc. of 23rd Conf. on Computer Aided Verification, pages 379-395, 2011. URL: https://doi.org/10.1007/978-3-642-22110-1_30.</text> <url>https://doi.org/10.1007/978-3-642-22110-1_30</url> </reference> <reference refNo="13"> <text>T.A. Henzinger. The theory of hybrid automata. In 11th IEEE Symp. Logic in Comp. Sci., pages 278-292, 1996. URL: https://doi.org/0.1109/LICS.1996.561342.</text> <url>https://doi.org/0.1109/LICS.1996.561342</url> </reference> <reference refNo="14"> <text>T.A. Henzinger, P.W. Kopke, A. Puri, and P. Varaiya. What’s decidable about hybrid automata? J. of Computer and System Sciences, 57(1):94-124, 1998. URL: https://doi.org/10.1006/jcss.1998.1581.</text> <url>https://doi.org/10.1006/jcss.1998.1581</url> </reference> <reference refNo="15"> <text>M. Kloetzer and C. Belta. A fully automated framework for control of linear systems from temporal logic specifications. IEEE Transactions on Automatic Control, 53(1):287-297, 2008. URL: https://doi.org/10.1109/TAC.2007.914952.</text> <url>https://doi.org/10.1109/TAC.2007.914952</url> </reference> <reference refNo="16"> <text>R. Koymans. Specifying real-time properties with metric temporal logic. Real-time systems, 2(4):255-299, 1990. URL: https://doi.org/10.1007/BF01995674.</text> <url>https://doi.org/10.1007/BF01995674</url> </reference> <reference refNo="17"> <text>O. Maler and D. Nickovic. Monitoring temporal properties of continuous signals. In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, pages 152-166. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30206-3_12.</text> <url>https://doi.org/10.1007/978-3-540-30206-3_12</url> </reference> <reference refNo="18"> <text>O. Maler, D. Nickovic, and A. Pnueli. Checking temporal properties of discrete, timed and continuous behaviors. Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, pages 475-505, 2008. URL: https://doi.org/10.1007/978-3-540-78127-1_26.</text> <url>https://doi.org/10.1007/978-3-540-78127-1_26</url> </reference> <reference refNo="19"> <text>A. Pnueli. The temporal logic of programs. In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 46-57. IEEE Computer Society, 1977. URL: https://doi.org/10.1109/SFCS.1977.32.</text> <url>https://doi.org/10.1109/SFCS.1977.32</url> </reference> <reference refNo="20"> <text>R. Poovendran. Cyber-physical systems: Close encounters between two parallel worlds. Proceedings of the IEEE, 98(8):1363-1366, 2010.</text> <url/> </reference> <reference refNo="21"> <text>M. Reynolds. The complexity of the temporal logic with “until” over general linear time. Journal of Computer and System Sciences, 66(2):393-426, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00005-9.</text> <url>https://doi.org/10.1016/S0022-0000(03)00005-9</url> </reference> <reference refNo="22"> <text>M. Reynolds. The complexity of temporal logic over the reals. Annals of Pure and Applied Logic, 161(8):1063-1096, 2010. URL: https://doi.org/10.1016/J.APAL.2010.01.002.</text> <url>https://doi.org/10.1016/J.APAL.2010.01.002</url> </reference> <copyright>Massimo Benerecetti, Marco Faella, and Fabio Mogavero</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> <article articleNo="20"> <title>FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks</title> <abstract>The analysis and summarization of temporal networks are crucial for understanding complex interactions over time, yet pose significant computational challenges. This paper introduces FastMinTC+, an innovative heuristic approach designed to efficiently solve the Minimum Timeline Cover (MinTCover) problem in temporal networks. Our approach focuses on the optimization of activity timelines within temporal networks, aiming to provide both effective and computationally feasible solutions. By employing a low-complexity approach, FastMinTC+ adeptly handles massive temporal graphs, improving upon existing methods. Indeed, comparative evaluations on both synthetic and real-world datasets demonstrate that our algorithm outperforms established benchmarks with remarkable efficiency and accuracy. The results highlight the potential of heuristic approaches in the domain of temporal network analysis and open up new avenues for further research incorporating other computational techniques, for example deep learning, to enhance the adaptability and precision of such heuristics.</abstract> <keyword>Temporal Networks</keyword> <keyword>Activity Timeline</keyword> <keyword>Timeline Cover</keyword> <keyword>Vertex Cover</keyword> <keyword>Optimization</keyword> <keyword>Heuristic</keyword> <subjectClassification acmID="10002950.10003624.10003633.10010917">Mathematics of computing~Graph algorithms</subjectClassification> <subjectClassification acmID="10003752.10003809">Theory of computation~Design and analysis of algorithms</subjectClassification> <subjectClassification acmID="10003752.10003809.10003716">Theory of computation~Mathematical optimization</subjectClassification> <subjectClassification acmID="10003752.10003809.10003716.10011136">Theory of computation~Discrete optimization</subjectClassification> <pages>20:1-20:18</pages> <category>Regular Paper</category> <acknowledgements/> <author> <firstName>Giorgio</firstName> <lastName>Lazzarinetti</lastName> <name>Giorgio Lazzarinetti</name> <affiliation>Università degli Studi Milano-Bicocca, Milano, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0003-0326-8742</orcid> </author> <author> <firstName>Sara</firstName> <lastName>Manzoni</lastName> <name>Sara Manzoni</name> <affiliation>Università degli Studi Milano-Bicocca, Milano, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-6406-536X</orcid> </author> <author> <firstName>Italo</firstName> <lastName>Zoppis</lastName> <name>Italo Zoppis</name> <affiliation>Università degli Studi Milano-Bicocca, Milano, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0001-7312-7123</orcid> </author> <author> <firstName>Riccardo</firstName> <lastName>Dondi</lastName> <name>Riccardo Dondi</name> <affiliation>Università degli Studi di Bergamo, Bergamo, Italy</affiliation> <homepageUrl/> <orcid>https://orcid.org/0000-0002-6124-2965</orcid> </author> <doi>10.4230/LIPIcs.TIME.2024.20</doi> <contentUrl/> <archivedUrl/> <reference refNo="1"> <text>Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017. URL: https://openreview.net/forum?id=Bk9mxlSFx.</text> <url>https://openreview.net/forum?id=Bk9mxlSFx</url> </reference> <reference refNo="2"> <text>Shaowei Cai. Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 747-753. AAAI Press, 2015. URL: http://ijcai.org/Abstract/15/111.</text> <url>http://ijcai.org/Abstract/15/111</url> </reference> <reference refNo="3"> <text>Shaowei Cai, Kaile Su, Chuan Luo, and Abdul Sattar. Numvc: An efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res., 46:687-716, 2013. URL: https://doi.org/10.1613/JAIR.3907.</text> <url>https://doi.org/10.1613/JAIR.3907</url> </reference> <reference refNo="4"> <text>Riccardo Dondi. Untangling temporal graphs of bounded degree. Theor. Comput. Sci., 969:114040, 2023. URL: https://doi.org/10.1016/J.TCS.2023.114040.</text> <url>https://doi.org/10.1016/J.TCS.2023.114040</url> </reference> <reference refNo="5"> <text>Riccardo Dondi and Manuel Lafond. An FPT algorithm for temporal graph untangling. In Neeldhara Misra and Magnus Wahlström, editors, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 of LIPIcs, pages 12:1-12:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPICS.IPEC.2023.12.</text> <url>https://doi.org/10.4230/LIPICS.IPEC.2023.12</url> </reference> <reference refNo="6"> <text>Riccardo Dondi and Alexandru Popa. Timeline cover in temporal graphs: Exact and approximation algorithms. In Sun-Yuan Hsieh, Ling-Ju Hung, and Chia-Wei Lee, editors, Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Tainan, Taiwan, June 7-10, 2023, Proceedings, volume 13889 of Lecture Notes in Computer Science, pages 173-184. Springer, 2023. URL: https://doi.org/10.1007/978-3-031-34347-6_15.</text> <url>https://doi.org/10.1007/978-3-031-34347-6_15</url> </reference> <reference refNo="7"> <text>Riccardo Dondi and Alexandru Popa. Exact and approximation algorithms for covering timeline in temporal graphs. Annals of Operations Research, April 2024. URL: https://doi.org/10.1007/s10479-024-05993-8.</text> <url>https://doi.org/10.1007/s10479-024-05993-8</url> </reference> <reference refNo="8"> <text>Vincent Froese, Pascal Kunz, and Philipp Zschoche. Disentangling the computational complexity of network untangling. CoRR, abs/2204.02668, 2022. URL: https://doi.org/10.48550/arXiv.2204.02668.</text> <url>https://doi.org/10.48550/arXiv.2204.02668</url> </reference> <reference refNo="9"> <text>Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput., 11(3):555-556, 1982. URL: https://doi.org/10.1137/0211045.</text> <url>https://doi.org/10.1137/0211045</url> </reference> <reference refNo="10"> <text>Petter Holme and Jari Saramäki. Temporal networks. CoRR, abs/1108.1780, 2011. URL: https://arxiv.org/abs/1108.1780.</text> <url>https://arxiv.org/abs/1108.1780</url> </reference> <reference refNo="11"> <text>Yuriy Hulovatyy, Huili Chen, and Tijana Milenkovic. Exploring the structure and function of temporal networks with dynamic graphlets. Bioinform., 32(15):2402, 2016. URL: https://doi.org/10.1093/BIOINFORMATICS/BTW310.</text> <url>https://doi.org/10.1093/BIOINFORMATICS/BTW310</url> </reference> <reference refNo="12"> <text>George Karakostas. A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms, 5(4):41:1-41:8, 2009. URL: https://doi.org/10.1145/1597036.1597045.</text> <url>https://doi.org/10.1145/1597036.1597045</url> </reference> <reference refNo="13"> <text>Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6348-6358, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/d9896106ca98d3d05b8cbdf4fd8b13a1-Abstract.html.</text> <url>https://proceedings.neurips.cc/paper/2017/hash/d9896106ca98d3d05b8cbdf4fd8b13a1-Abstract.html</url> </reference> <reference refNo="14"> <text>Kenneth Langedal, Johannes Langguth, Fredrik Manne, and Daniel Thilo Schroeder. Efficient minimum weight vertex cover heuristics using graph neural networks. In Christian Schulz and Bora Uçar, editors, 20th International Symposium on Experimental Algorithms, SEA 2022, July 25-27, 2022, Heidelberg, Germany, volume 233 of LIPIcs, pages 12:1-12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.SEA.2022.12.</text> <url>https://doi.org/10.4230/LIPICS.SEA.2022.12</url> </reference> <reference refNo="15"> <text>Giorgio Lazzarinetti, Riccardo Dondi, Sara Manzoni, and Italo Zoppis. An attention-based method for the minimum vertex cover problem on complex networks. Algorithms, 17(2):72, 2024. URL: https://doi.org/10.3390/A17020072.</text> <url>https://doi.org/10.3390/A17020072</url> </reference> <reference refNo="16"> <text>Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 537-546, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/8d3bba7425e7c98c50f52ca1b52d3735-Abstract.html.</text> <url>https://proceedings.neurips.cc/paper/2018/hash/8d3bba7425e7c98c50f52ca1b52d3735-Abstract.html</url> </reference> <reference refNo="17"> <text>Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey. ACM Comput. Surv., 51(3):62:1-62:34, 2018. URL: https://doi.org/10.1145/3186727.</text> <url>https://doi.org/10.1145/3186727</url> </reference> <reference refNo="18"> <text>Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math., 12(4):239-280, 2016. URL: https://doi.org/10.1080/15427951.2016.1177801.</text> <url>https://doi.org/10.1080/15427951.2016.1177801</url> </reference> <reference refNo="19"> <text>Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. Motifs in temporal networks. Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 2016. URL: https://api.semanticscholar.org/CorpusID:13332080.</text> <url>https://api.semanticscholar.org/CorpusID:13332080</url> </reference> <reference refNo="20"> <text>Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Sci. Eng., 6(2):119-141, 2021. URL: https://doi.org/10.1007/S41019-021-00155-3.</text> <url>https://doi.org/10.1007/S41019-021-00155-3</url> </reference> <reference refNo="21"> <text>Anna-Kaisa Pietilänen and Christophe Diot. Dissemination in opportunistic social networks: the role of temporal communities. In Proceedings of the Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '12, pages 165-174, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2248371.2248396.</text> <url>https://doi.org/10.1145/2248371.2248396</url> </reference> <reference refNo="22"> <text>Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: https://networkrepository.com.</text> <url>https://networkrepository.com</url> </reference> <reference refNo="23"> <text>P. Rozenshtein. the-network-untangling-problem. https://github.com/polinapolina/the-network-untangling-problem/tree/master, 2020. [Online; accessed 13-June-2024].</text> <url>https://github.com/polinapolina/the-network-untangling-problem/tree/master</url> </reference> <reference refNo="24"> <text>Polina Rozenshtein, Francesco Bonchi, Aristides Gionis, Mauro Sozio, and Nikolaj Tatti. Finding events in temporal networks: segmentation meets densest subgraph discovery. Knowl. Inf. Syst., 62(4):1611-1639, 2020. URL: https://doi.org/10.1007/S10115-019-01403-9.</text> <url>https://doi.org/10.1007/S10115-019-01403-9</url> </reference> <reference refNo="25"> <text>Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. The network-untangling problem: from interactions to activity timelines. Data Min. Knowl. Discov., 35(1):213-247, 2021. URL: https://doi.org/10.1007/S10618-020-00717-5.</text> <url>https://doi.org/10.1007/S10618-020-00717-5</url> </reference> <reference refNo="26"> <text>Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, and Christos Faloutsos. Timecrunch: Interpretable dynamic graph summarization. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 1055-1064. ACM, 2015. URL: https://doi.org/10.1145/2783258.2783321.</text> <url>https://doi.org/10.1145/2783258.2783321</url> </reference> <reference refNo="27"> <text>Bianca Wackersreuther, Peter Wackersreuther, Annahita Oswald, Christian Böhm, and Karsten M. Borgwardt. Frequent subgraph discovery in dynamic networks. In Ulf Brefeld, Lise Getoor, and Sofus A. Macskassy, editors, Proceedings of the Eighth Workshop on Mining and Learning with Graphs, MLG '10, Washington, D.C., USA, July 24-25, 2010, pages 155-162. ACM, 2010. URL: https://doi.org/10.1145/1830252.1830272.</text> <url>https://doi.org/10.1145/1830252.1830272</url> </reference> <copyright>Giorgio Lazzarinetti, Sara Manzoni, Italo Zoppis, and Riccardo Dondi</copyright> <license>Creative Commons Attribution 4.0 International license</license> <licenseUrl>https://creativecommons.org/licenses/by/4.0/legalcode</licenseUrl> </article> </metadata>