Temporal query languages expressive power: μTL vs. T-WHILE

We investigate the expressive power of implicit temporal query languages. The initial motivation was refining the results of (S. Abiteboul et al., 1999) and enrich them with comparison to μTL (M.Y. Vardi, 1988). Thus, we address two classes of temporal query languages: μTL-like languages based on TL and T-WHILE-like languages based on WHILE. We provide a two-level hierarchy (w.r t. expressive power) for these temporal query languages. One of the contributions solves an open problem: the relative expressivity of μTL and T-FIXPOINT.