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

https://hal.inria.fr/hal-02887779
Contributor : Luc Segoufin <>
Submitted on : Thursday, July 2, 2020 - 3:02:49 PM
Last modification on : Saturday, May 1, 2021 - 3:41:42 AM
Long-term archiving on: : Thursday, September 24, 2020 - 4:57:43 AM

File

journal.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

27

Files downloads

86