paint-brush
What Are Ordered Monoids? Ordered Monoids Explainedby@hierarchy

What Are Ordered Monoids? Ordered Monoids Explained

by Hierarchy
Hierarchy HackerNoon profile picture

Hierarchy

@hierarchy

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

January 31st, 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

An ordered monoid is a pair (M <) where M is a monoid and < is a partial order on M.
featured image - What Are Ordered Monoids? Ordered Monoids Explained
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

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.

image

image

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.


image


image


We now prove Proposition 6. The proof is based on Theorem 3 and Proposition 50 above. Let us first recall the statement.


image


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.


image


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)).


image


We turn to the proof of Proposition 10.


image


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).


image

image


We now prove strictness. First, we have the following lemma whose proof is based on the properties of the operator BPol.


image


Clearly, this is a language in Pol(DD). Moreover, one can verify that,


image


Since it is clear that x1, x2, x3, x4 ∈ Pol(DD), we get U ∈ Pol(DD) by closure under concatenation. Similarly, observe that,


image


image


Second, we have the following lemma whose proof is based on Lemma 5.


image


image


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.


image


image


image


image


image


Theorem 18 gives additional information regarding the concatenation and temporal hierarchies of basis ST. We first recall its statement.


image


We have the following lemma.


image


The second ingredient in the proof of Theorem 18 is given by the following lemma.


image


image


image


image


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.


image


The last result to prove in this Appendix is Theorem 20. Let us first recall its statement.


image


image


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.


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
X
Bsky
X REMOVE AD