i v with v ? w. The duplicator is then going to answer as follows. First, he/she considers the set of states of I corresponding to the choice of the spoiler. Let us assume that this set is E={I i 1 , . . ., I iv }. Next, he/she builds the equivalence classes of E induced by the equivalence relation ? defined by I t ? I t ? iff I t ? {a 1, The spoiler chooses to play a t-move in I and starts by providing v distinct instants i 1 ,
Temporal Connectives Versus Explicit Timestamps in Temporal Query Languages, Recent Advances in Temporal Databases, pp.43-60, 1995. ,
Temporal Connectives Versus Explicit Timestamps to Query Temporal Databases, JCSS, vol.58, issue.1, pp.54-68, 1999. ,
Foundations of Databases, 1995. ,
Interpolation, Preservation, and Pebble games, J. Symbolic Logic, vol.64, issue.2, pp.881-903, 1999. ,
Implicit temporal query languages : towards completeness, LNCS, vol.1738, pp.245-257, 1999. ,
, Model Theory, 1990.
Temporal Query Languages: a survey, Temporal Logic, First Int. conf., LNAI, vol.827, pp.506-534, 1994. ,
, Temporal Logic in Information Systems, Logics for Databases and Information Systems, pp.31-70, 1998.
, Finite Model Theory, 1995.
Temporal and Modal Logic, Formal Models and Semantics, Jan van Leeuwen, vol.B, pp.995-1072, 1990. ,
, On the Temporal Basis of Fairness, Symposium on Principles of Programming Languages, pp.163-173, 1980.
Decidable fragments of first-order temporal logics, Annals of Pure and Applied Logic, vol.106, pp.85-134, 2000. ,
Descriptive Complexity. Springer Graduate Texts in Computer Science, 1999. ,
Tense Logic and the Theory of Linear Order, 1968. ,
, , 1996.
A hierarchy of temporal logics with past, TCS, vol.148, issue.2, pp.303-324, 1995. ,
Weak monadic second order theory of successor is not elementary recursive, Proceedings Logic Colloquium, vol.453, pp.132-154, 1975. ,
First Order Queries over Temporal Databases Inexpressible in Temporal Logic, EDBT, pp.307-324, 1996. ,
The complexity of proposicional linear temporal logic, Journal of the ACM, vol.32, issue.3, pp.733-749, 1985. ,
First-order expressivity for S5-models: modals vs. twosorted languages, Journal of Philosophical Logic, vol.30, pp.571-591, 2001. ,
Temporal Logic can be more expressive. Information and Control, vol.56, pp.72-99, 1983. ,