paint-brush
The Preliminaries We Used to Classify Languages: Fixing a Finite Alphabetby@hierarchy

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

by Hierarchy
Hierarchy HackerNoon profile picture

Hierarchy

@hierarchy

Hierarchy's nested framework organizes and allocates, channeling power and responsibility...

January 30th, 2025
Read on Terminal Reader
Read this story in a terminal
Print this story
Read this story w/o Javascript
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

We fix a finite alphabet A. As usual, A* is the set of all infinite words over A, including the empty one.
featured image - The Preliminaries We Used to Classify Languages: Fixing a Finite Alphabet
1x
Read by Dr. One voice-avatar

Listen to this story

Hierarchy HackerNoon profile picture
Hierarchy

Hierarchy

@hierarchy

Hierarchy's nested framework organizes and allocates, channeling power and responsibility with clarity and purpose.

About @hierarchy
LEARN MORE ABOUT @HIERARCHY'S
EXPERTISE AND PLACE ON THE INTERNET.
0-item

STORY’S CREDIBILITY

Academic Research Paper

Academic Research Paper

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

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

image


image


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.


image


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.


image


This paper is available on arxiv under CC BY 4.0 DEED license.

Authors:

(1) Thomas Place;

(2) Marc Zaitoun.


L O A D I N G
. . . comments & more!

About Author

Hierarchy HackerNoon profile picture
Hierarchy@hierarchy
Hierarchy's nested framework organizes and allocates, channeling power and responsibility with clarity and purpose.

TOPICS

THIS ARTICLE WAS FEATURED IN...

Permanent on Arweave
Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite
Hackernoon
Bsky
X REMOVE AD