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
Appendix A. Appendix to Section 2
In this section, we present additional terminology used in proof arguments throughout the appendix. First, we introduce ordered monoids, which are used to handle classes that may not be closed under complement (we need them to deal with the classes Pol(C)). Then, we introduce the notion of C-morphism for a positive prevariety C, which is a key mathematical tool.
Appendix B. Appendix to Section 3
In this appendix, we provide the missing proofs for the statements presented in Section 3.
B.1. Definition. We use Theorem 3 to prove a characterization of the TL(C)-morphisms when C is a prevariety. This will be useful in proof arguments.
We now prove Proposition 6. The proof is based on Theorem 3 and Proposition 50 above. Let us first recall the statement.
Finally, we prove Lemma 5.
Lemma 5. Let C be a prevariety and L, U, V ⊆ A∗ such that L is not C-separable from either U or V. If P = L∗ (UL∗V L∗ )∗, then P is not TL(C)-separable from either PUP or PVP.
B.2. Connection with concatenation hierarchies. We turn to concatenation hierarchies. First, we prove the statements presented in the main paper. Let us start with Proposition 8.
Proposition 8. For every class C, we have TL(C) = TL(Pol(C)).
We turn to the proof of Proposition 10.
Lemma 51. Let C be a positive prevariety. Then Pol(BPol(C)) = Pol(co-Pol(C)).
The next lemma is the counterpart of Lemma 5 for this operator. We prove it as a corollary of [26, Theorem 54] which states a generic algebraic characterization of Pol(C).
We now prove strictness. First, we have the following lemma whose proof is based on the properties of the operator BPol.
Clearly, this is a language in Pol(DD). Moreover, one can verify that,
Since it is clear that x1, x2, x3, x4 ∈ Pol(DD), we get U ∈ Pol(DD) by closure under concatenation. Similarly, observe that,
Second, we have the following lemma whose proof is based on Lemma 5.
Consequently, we obtain the following theorem as an immediate corollary.
Theorem 15. Let G a be group prevariety. If |A| ≥ 2, then,
• The temporal hierarchies of bases G and G + are both strict and strictly intertwined.
• The concatenation hierarchies of bases G and G + are both strict and strictly intertwined.
Theorem 18 gives additional information regarding the concatenation and temporal hierarchies of basis ST. We first recall its statement.
We have the following lemma.
The second ingredient in the proof of Theorem 18 is given by the following lemma.
One can verify that this construction φ 7→ ⟨φ⟩ does satisfy (5), which completes the proof.
With Proposition 56 in hand, we are ready to conclude the proof of Theorem 19. The last ingredient is given by the following lemma.
The last result to prove in this Appendix is Theorem 20. Let us first recall its statement.
One can verify that this construction φ 7→ ⟨φ⟩ does satisfy (6), which completes the proof.
The second ingredient in the proof of Theorem 20 is given by the following lemma.
Authors:
(1) Thomas Place;
(2) Marc Zaitoun.
