.. ;. and ,. .. , 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

S. Abiteboul, L. Herr, and J. Van-den-bussche, Temporal Connectives Versus Explicit Timestamps in Temporal Query Languages, Recent Advances in Temporal Databases, pp.43-60, 1995.

S. Abiteboul, L. Herr, and J. Van-den-bussche, Temporal Connectives Versus Explicit Timestamps to Query Temporal Databases, JCSS, vol.58, issue.1, pp.54-68, 1999.

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

J. Barwise and J. Benthem, Interpolation, Preservation, and Pebble games, J. Symbolic Logic, vol.64, issue.2, pp.881-903, 1999.

N. Bidoit and S. De-amo, Implicit temporal query languages : towards completeness, LNCS, vol.1738, pp.245-257, 1999.

C. Chang and H. Keisler, Model Theory, 1990.

J. Chomicki, Temporal Query Languages: a survey, Temporal Logic, First Int. conf., LNAI, vol.827, pp.506-534, 1994.

J. Chomicki and D. Toman, Temporal Logic in Information Systems, Logics for Databases and Information Systems, pp.31-70, 1998.

H. Ebbinghaus and J. Flum, Finite Model Theory, 1995.

E. A. Emerson, Temporal and Modal Logic, Formal Models and Semantics, Jan van Leeuwen, vol.B, pp.995-1072, 1990.

D. Gabbay, M. Pnueli, A. Shelah, S. Stavi, and J. , On the Temporal Basis of Fairness, Symposium on Principles of Programming Languages, pp.163-173, 1980.

I. Hodkinson, F. Wolter, and M. Zakharyaschev, Decidable fragments of first-order temporal logics, Annals of Pure and Applied Logic, vol.106, pp.85-134, 2000.

N. Immerman, Descriptive Complexity. Springer Graduate Texts in Computer Science, 1999.

H. W. Kamp, Tense Logic and the Theory of Linear Order, 1968.

E. Kushilevitz and N. Nisan, , 1996.

L. Laroussinie and P. Schnoebelen, A hierarchy of temporal logics with past, TCS, vol.148, issue.2, pp.303-324, 1995.

A. R. Meyer, Weak monadic second order theory of successor is not elementary recursive, Proceedings Logic Colloquium, vol.453, pp.132-154, 1975.

D. Niwinski and D. Toman, First Order Queries over Temporal Databases Inexpressible in Temporal Logic, EDBT, pp.307-324, 1996.

A. P. Sistla, C. , and E. M. , The complexity of proposicional linear temporal logic, Journal of the ACM, vol.32, issue.3, pp.733-749, 1985.

H. Sturm and F. Wolter, First-order expressivity for S5-models: modals vs. twosorted languages, Journal of Philosophical Logic, vol.30, pp.571-591, 2001.

P. Wolper, Temporal Logic can be more expressive. Information and Control, vol.56, pp.72-99, 1983.