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. This paper is available on arxiv under CC BY 4.0 DEED license. Authors:
(1) Thomas Place;
(2) Marc Zaitoun. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Preliminaries 2 Preliminaries 3 Temporal Hierarchies 3 Temporal Hierarchies 4 Rating Maps 4 Rating Maps 5 Optimal Imprints for TL(AT) 5 Optimal Imprints for TL(AT) 6 Conclusion and References 6 Conclusion and References Appendix A. Appendix to Section 2 & Appendix B. Appendix to Section 3 Appendix A. Appendix to Section 2 & Appendix B. Appendix to Section 3 Appendix C. Appendix to Section 4 Appendix C. Appendix to Section 4 Appendix D. Appendix to Section 5 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. Definition 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. 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. Connection with concatenation hierarchies. Proposition 8. For every class C , we have TL( C ) = TL(Pol( C )). Proposition 8. For every class C we have C 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)). 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, 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 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. • 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. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv Authors: (1) Thomas Place; (2) Marc Zaitoun. Authors: Authors: (1) Thomas Place; (2) Marc Zaitoun.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Temporal Hierarchies of Regular Languages: Missing Arguments for the Intermediary Statements

Defining Temporal Hierarchies and How We Proved That Corresponding Hierarchies Are Always Strict

Read My Stories

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

What Are Ordered Monoids? Ordered Monoids Explained

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Defining Temporal Hierarchies and How We Proved That Corresponding Hierarchies Are Always Strict

Temporal Hierarchies of Regular Languages: Missing Arguments for the Intermediary Statements

Temporal Hierarchies of Regular Languages: How We Classified Languages

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

What Are Temporal Hierarchies?

Rating Maps: The Framework That We Used

Defining Temporal Hierarchies and How We Proved That Corresponding Hierarchies Are Always Strict

Temporal Hierarchies of Regular Languages: Missing Arguments for the Intermediary Statements

Temporal Hierarchies of Regular Languages: How We Classified Languages

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

What Are Temporal Hierarchies?

Rating Maps: The Framework That We Used

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps