Logical forms of chronicles
International audience 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 chroni...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , , , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2022
|
Subjects: | |
Online Access: | https://hal.archives-ouvertes.fr/hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471/document https://hal.archives-ouvertes.fr/hal-03777471/file/time2022-GM.pdf |
id |
ftecolecentrlyon:oai:HAL:hal-03777471v1 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Portail HAL - Ecole Centrale de Lyon |
op_collection_id |
ftecolecentrlyon |
language |
English |
topic |
temporal logics temporal models [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
spellingShingle |
temporal logics temporal models [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Guyet, Thomas Markey, Nicolas Logical forms of chronicles |
topic_facet |
temporal logics temporal models [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
description |
International audience 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. 2012 ACM Subject Classification Theory of computation → Modal and temporal logics; Theory of computation → Timed and hybrid models Keywords and phrases temporal logics, temporal models Digital Object Identifier 10.4230/LIPIcs.TIME.2022.1 |
author2 |
Artificial Evolution and Computational Biology (BEAGLE) Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS) Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL) Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon) Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL) Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) SUpervision of large MOdular and distributed systems (SUMO) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4) Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Université de Rennes 1 (UR1) Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Université de Rennes 1 (UR1) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT) |
format |
Conference Object |
author |
Guyet, Thomas Markey, Nicolas |
author_facet |
Guyet, Thomas Markey, Nicolas |
author_sort |
Guyet, Thomas |
title |
Logical forms of chronicles |
title_short |
Logical forms of chronicles |
title_full |
Logical forms of chronicles |
title_fullStr |
Logical forms of chronicles |
title_full_unstemmed |
Logical forms of chronicles |
title_sort |
logical forms of chronicles |
publisher |
HAL CCSD |
publishDate |
2022 |
url |
https://hal.archives-ouvertes.fr/hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471/document https://hal.archives-ouvertes.fr/hal-03777471/file/time2022-GM.pdf |
op_coverage |
online, Heard & McDonald Islands |
long_lat |
ENVELOPE(73.510,73.510,-53.117,-53.117) ENVELOPE(72.600,72.600,-53.033,-53.033) |
geographic |
Heard McDonald Islands |
geographic_facet |
Heard McDonald Islands |
genre |
McDonald Islands |
genre_facet |
McDonald Islands |
op_source |
TIME 2022 - 29th International Symposium on Temporal Representation and Reasoning https://hal.archives-ouvertes.fr/hal-03777471 TIME 2022 - 29th International Symposium on Temporal Representation and Reasoning, Nov 2022, online, Heard & McDonald Islands. pp.1-15 |
op_relation |
hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471/document https://hal.archives-ouvertes.fr/hal-03777471/file/time2022-GM.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766067104958644224 |
spelling |
ftecolecentrlyon:oai:HAL:hal-03777471v1 2023-05-15T17:10:31+02:00 Logical forms of chronicles Guyet, Thomas Markey, Nicolas Artificial Evolution and Computational Biology (BEAGLE) Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS) Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL) Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon) Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL) Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) SUpervision of large MOdular and distributed systems (SUMO) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4) Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Université de Rennes 1 (UR1) Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Université de Rennes 1 (UR1) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique) Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT) online, Heard & McDonald Islands 2022-11-07 https://hal.archives-ouvertes.fr/hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471/document https://hal.archives-ouvertes.fr/hal-03777471/file/time2022-GM.pdf en eng HAL CCSD hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471 https://hal.archives-ouvertes.fr/hal-03777471/document https://hal.archives-ouvertes.fr/hal-03777471/file/time2022-GM.pdf info:eu-repo/semantics/OpenAccess TIME 2022 - 29th International Symposium on Temporal Representation and Reasoning https://hal.archives-ouvertes.fr/hal-03777471 TIME 2022 - 29th International Symposium on Temporal Representation and Reasoning, Nov 2022, online, Heard & McDonald Islands. pp.1-15 temporal logics temporal models [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] info:eu-repo/semantics/conferenceObject Conference papers 2022 ftecolecentrlyon 2022-10-13T06:00:57Z International audience 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. 2012 ACM Subject Classification Theory of computation → Modal and temporal logics; Theory of computation → Timed and hybrid models Keywords and phrases temporal logics, temporal models Digital Object Identifier 10.4230/LIPIcs.TIME.2022.1 Conference Object McDonald Islands Portail HAL - Ecole Centrale de Lyon Heard ENVELOPE(73.510,73.510,-53.117,-53.117) McDonald Islands ENVELOPE(72.600,72.600,-53.033,-53.033) |