Document Open Access Logo

Logical Forms of Chronicles

Authors Thomas Guyet , Nicolas Markey

PDF
Thumbnail PDF

File

LIPIcs.TIME.2022.7.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Guyet
  • Inria, Lyon, France
Nicolas Markey
  • CNRS, IRISA, Rennes, France

Cite As Get BibTex

Thomas Guyet and Nicolas Markey. Logical Forms of Chronicles. In 29th International Symposium on Temporal Representation and Reasoning (TIME 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 247, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.TIME.2022.7

Abstract

A chronicle is a temporal model introduced by Dousson et al. for situation recognition. In short, a chronicle consists of a set of events and a set of real-valued temporal constraints on the delays between pairs of events. This work investigates the relationship between chronicles and classical temporal-model formalisms, namely TPTL and MTL. More specifically, we answer the following question: is it possible to find an equivalent formula in such formalisms for any chronicle? This question arises from the observation that a single chronicle captures complex temporal behaviours, without imposing a particular order of the events in time.
For our purpose, we introduce the subclass of linear chronicles, which set the order of occurrence of the events to be recognized in a temporal sequence. Our first result is that any chronicle can be expressed as a disjunction of linear chronicles. Our second result is that any linear chronicle has an equivalent TPTL formula. Using existing expressiveness results between TPTL and MTL, we show that some chronicles have no equivalent in MTL. This confirms that the model of chronicle has interesting properties for situation recognition.

Subject Classification

ACM Subject Classification
  • Theory of computation → Modal and temporal logics
  • Theory of computation → Timed and hybrid models
Keywords
  • temporal logics
  • temporal models

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur and Thomas A. Henzinger. A really temporal logic. Journal of the ACM, 41(1):181-203, 1994. Google Scholar
  2. Darko Anicic, Sebastian Rudolph, Paul Fodor, and Nenad Stojanovic. Stream reasoning and complex event processing in ETALIS. Semantic web, 3(4):397-407, 2012. Google Scholar
  3. Philippe Besnard and Thomas Guyet. Chronicles. under submission, 2022. Google Scholar
  4. Michael H Böhlen, Jan Chomicki, Richard T Snodgrass, and David Toman. Querying TSQL2 databases with temporal logic. In Proceedings of the International Conference on Extending Database Technology, pages 325-341, 1996. Google Scholar
  5. Alessio Bottrighi, Laura Giordano, Gianpaolo Molino, Stefania Montani, Paolo Terenziani, and Mauro Torchio. Adopting model checking techniques for clinical guidelines verification. Artificial Intelligence in Medicine, 48(1):1-19, 2010. Google Scholar
  6. Patricia Bouyer, Fabrice Chevalier, and Nicolas Markey. On the expressiveness of TPTL and MTL. Information and Computation, 208(2):97-116, 2010. Google Scholar
  7. Sebastian Brandt, Elem Güzel Kalaycı, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. Querying log data with metric temporal logic. Journal of Artificial Intelligence Research, 62:829-877, 2018. Google Scholar
  8. Martin Chapman, Luke V Rasmussen, Jennifer A Pacheco, and Vasa Curcin. Phenoflow: A microservice architecture for portable workflow-based phenotype definitions. Procedings of the Summits on Translational Science, 2021:142, 2021. Google Scholar
  9. Edmund M Clarke and E Allen Emerson. Design and synthesis of synchronization skeletons using branching time temporal logic. In Workshop on Logic of Programs, pages 52-71, 1981. Google Scholar
  10. Damien Cram, Benoît Mathern, and Alain Mille. A complete chronicle discovery approach: application to activity analysis. Expert Systems, 29(4):321-346, 2012. Google Scholar
  11. Yann Dauxais, Thomas Guyet, David Gross-Amblard, and André Happe. Discriminant chronicles mining. In Proceedings of the Conference on Artificial Intelligence in Medicine in Europe (AIME), pages 234-244, 2017. Google Scholar
  12. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 49(1-3):61-95, 1991. Google Scholar
  13. Christophe Dousson, Paul Gaborit, and Malik Ghallab. Situation recognition: representation and algorithms. In Proceedings of the international joint conference on Artifical intelligence (IJCAI), pages 166-172, 1993. Google Scholar
  14. Christophe Dousson and Thang Vu Duong. Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems. In Proceedings of the international joint conference on Artifical intelligence (IJCAI), pages 620-629, 1999. Google Scholar
  15. Malik Ghallab. On chronicles: Representation, on-line recognition and learning. In Luigia Carlucci Aiello, Jon Doyle, and Stuart C. Shapiro, editors, Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 597-606, 1996. Google Scholar
  16. Thomas Guyet, Philippe Besnard, Ahmed Samet, Nasreddine Ben Salha, and Nicolas Lachiche. Énumération des occurrences d'une chronique. In Extraction et Gestion des Connaissances, pages 253-260, 2020. Google Scholar
  17. Romain Kervac and Ariane Piel. A survey on chronicles and other behavior detection techniques. Journal of Aerospace Lab, 15, 2020. Google Scholar
  18. Ron Koymans. Specifying real-time properties with metric temporal logic. Real-time systems, 2(4):255-299, 1990. Google Scholar
  19. Leslie Lamport. The temporal logic of actions. Transactions on Programming Languages and Systems (TOPLAS), 16(3):872-923, 1994. Google Scholar
  20. Hector Levesque, Fiora Pirri, and Ray Reiter. Foundations for the situation calculus. Linköping Electronic Articles in Computed and Information Science, 3(18), 1998. Google Scholar
  21. Erik T Mueller. Event calculus. Foundations of Artificial Intelligence, 3:671-708, 2008. Google Scholar
  22. Joël Ouaknine and James Worrell. On metric temporal logic and faulty turing machines. In Proceedings of the International Conference on Foundations of Software Science and Computation Structures, pages 217-230, 2006. Google Scholar
  23. Amir Pnueli. The temporal logic of programs. In Proceedings of the Annual Symposium on Foundations of Computer Science (SFCS), pages 46-57, 1977. Google Scholar
  24. Pavithra Prabhakar and Deepak D'Souza. On the expressiveness of MTL with past operators. In Proceedings of Formal Modeling and Analysis of Timed Systems, pages 322-336, 2006. Google Scholar
  25. Paolo Terenziani, Gianpaolo Molino, and Mauro Torchio. A modular approach for representing and executing clinical guidelines. Artificial intelligence in medicine, 23(3):249-276, 2001. Google Scholar
  26. Dogan Ulus. Pattern Matching with Time: Theory and Applications. PhD thesis, Université Grenoble Alpes, 2018. Google Scholar
  27. Przemyslaw A. Walęga, Bernardo Cuenca Grau, Mark Kaminski, and Egor V. Kostylev. DatalogMTL: Computational complexity and expressive power. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1886-1892, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact