What Are Temporal Hierarchies?

Table of Links

Abstract and 1 Introduction

2 Preliminaries

3 Temporal Hierarchies

4 Rating Maps

5 Optimal Imprints for TL(AT)

6 Conclusion and References

Appendix A. Appendix to Section 2 & Appendix B. Appendix to Section 3

Appendix C. Appendix to Section 4 & Appendix D. Appendix to Section 5

3. Temporal hierarchies

We introduce the operator C 7→ TL(C) and use it to define temporal hierarchies. We compare them to the classic concatenation hierarchies. We focus on the standard bases which are made of group languages. We prove that for such a basis, the corresponding temporal hierarchy is always strict and that membership for the level two boils down to separation for the basis.

Proposition 21 can now be combined with Corollary 4. We obtain that for every group prevariety G, if C ∈ {G, G +}, then TL2(C)-membership reduces to BPol(C)-separation. The latter problem has been extensively studied for group classes. If C ∈ {G, G +}, it is shown in [28, 30] that BPol(C)- separation reduces to C-separation. This yields the following result.