Temporal query languages expressive power: /spl mu/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 /spl mu/TL (M.Y. Vardi, 1988). Thus, we address two classes of temporal query languages: /spl mu/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 /spl mu/TL and T-FIXPOINT.