Skip to Main content Skip to Navigation
Journal articles

Order Independent Temporal Properties

Nicole Bidoit 1 Sandra de Amo 2, 3 Luc Segoufin 4 
4 GEMO - Integration of data and knowledge distributed over the web
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The paper investigates temporal properties that are invariant with respect to the temporal ordering and that are expressible by temporal query languages either explicit like FO(≤) or implicit like TL. In the case of an explicit time representation, these "order invariant" temporal properties are simply those expressible in the language FO(=). In the case of an implicit time representation, we introduce a new language, TL(E i) that captures exactly these properties. The expressive power of the language TL(E i) is characterized via a gameà la Ehrenfeucht-Fraïssé. This provides another proof, using a more classical technique, that the implicit temporal language TL is strictly less expressive than the explicit temporal language FO(≤). This alternative proof is interesting by itself and opens new perspectives in the investigation of results of the same kind for more expressive implicit temporal languages than TL.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Thursday, July 2, 2020 - 3:02:49 PM
Last modification on : Sunday, June 26, 2022 - 12:16:39 PM
Long-term archiving on: : Thursday, September 24, 2020 - 4:57:43 AM


Files produced by the author(s)




Nicole Bidoit, Sandra de Amo, Luc Segoufin. Order Independent Temporal Properties. Journal of Logic and Computation, Oxford University Press (OUP), 2004, 14 (2), pp.277-298. ⟨10.1093/logcom/14.2.277⟩. ⟨hal-02887779⟩



Record views


Files downloads