The Preliminaries We Used to Classify Languages: Fixing a Finite Alphabet

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

2. Preliminaries

Remark 1. The only infinite monoids that we consider are of the form A∗ . From now on, we implicitly assume that every other monoid M, N, . . . appearing in the paper is finite.

We shall also consider the class LT of locally testable languages [6, 44]. It consists of all finite Boolean combinations of languages A∗wA∗ , wA∗ and A∗w where w ∈ A∗ is a word.

Decision problems. These problems depend on a parameter class C. We use them as tools for analyzing C: intuitively, proving their decidability requires a solid understanding of C. The simplest one is C-membership. Its input is a regular language L. It asks whether L ∈ C.