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. 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 D. Appendix to Section 5 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. 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. Decision problems. 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.

What Are Temporal Hierarchies?

Temporal Hierarchies of Regular Languages: How We Classified Languages

Read My Stories

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

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

Shannon: a Hero of the Digital Age

Light Bulb Control Circuit Design Using Boolean Algebra

Rating Maps: The Framework That We Used

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

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

Shannon: a Hero of the Digital Age

Light Bulb Control Circuit Design Using Boolean Algebra

Rating Maps: The Framework That We Used

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps