Loading...
Please wait, while we are loading the content...
Similar Documents
Ordered monoids and J-trivial monoids
| Content Provider | Semantic Scholar |
|---|---|
| Author | Henckell, Karsten |
| Copyright Year | 1999 |
| Abstract | In this paper we give a new proof of the following result of Straubing and Thérien: every J -trivial monoid is a quotient of an ordered monoid satisfying the identity x ≤ 1. We will assume in this paper that the reader has a basic background in finite semigroup theory (in particular, Green’s relations and identities defining varieties) and in computer science (languages, trees, heaps). All semigroups except free monoids and free semigroups are assumed finite. As a consequence, the term variety always means variety of finite semigroups (or pseudo-variety) and the term identity refers to pseudo-identity, in the terminology of Almeida [2]. A relation ≤ on a semigroup S is stable if, for every x, y, z ∈ S, x ≤ y implies xz ≤ yz and zx ≤ zy. An ordered semigroup is a semigroup S equipped with a stable partial order ≤ on S. Ordered monoids are defined analogously. Let A∗ be a free monoid. Given a subset P of A∗, the relation 1P defined on A∗ by setting u 1P v if and only if, for every x, y ∈ A ∗, xvy ∈ P ⇒ xuy ∈ P, is a stable partial preorder. The equivalence relation ∼P associated with 1P is defined, for every x, y ∈ A ∗, by xuy ∈ P ⇐⇒ xvy ∈ P The monoid M(P ) = A/∼P , ordered with the order relation induced by 1P , is called the ordered syntactic monoid of P . New College of the University of South Florida, Sarasota, FL 34243, USA, henckell@virtu.sar.usf.edu LIAFA, Université Paris VII et CNRS, Tour 55-56, 2 Place Jussieu, 75251 Paris Cedex 05, FRANCE, Jean-Eric.Pin@liafa.jussieu.fr |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://hal.archives-ouvertes.fr/hal-00112620/document |
| Alternate Webpage(s) | http://www.liafa.jussieu.fr/~jep/PDF/OrderedJtrivial.pdf |
| Alternate Webpage(s) | https://www.irif.fr/~jep/PDF/OrderedJtrivial.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Assumed Free monoid Heap (data structure) Krohn–Rhodes theory Nomenclature Order (action) Ordered pair Programming Languages Pseudo brand of pseudoephedrine Quotient Sense of identity (observable entity) Subgroup Surround sound Syntactic monoid Trees (plant) Turing completeness Vii computer science |
| Content Type | Text |
| Resource Type | Article |
