<p>Perhaps the Menagerie of Monoids diagram will be helpful?</p>

<p><a href="https://i.sstatic.net/tKSam.png" rel="nofollow noreferrer">https://i.sstatic.net/tKSam.png</a></p>

<p>from page 5, "On the Representation Theory of Finite J-trivial Monoids", by Denton, et. al. (2010).</p>

<p>A detailed description is also given in Section 2.1,</p>

<blockquote>
  <p>The smaller class of R-trivial monoids coincides with the class of so-called <em>weakly
  ordered monoids</em> as defined by Schocker [Sch08]. Also, via the right regular representation, any R-trivial monoid can be represented as a monoid of regressive functions on some finite poset P (a function f : P → P is called <em>regressive</em> if f(x) ≤ x for every x ∈ P); reciprocally any such monoid is R-trivial. We now present an example of a monoid which is R-trivial, but not J-trivial.</p>
  
  <p>Example 2.3. Take the free left regular band B generated by two idempotents a,b. Multiplication is given by concatenation taking into account the idempotent relations, and then selecting only the two left factors (see for example [Sal07]). So B = {1,a,b,ab,ba} and 1B = B, aB = {a,ab}, bB = {b,ba}, abB = {ab}, and baB = {ba}. This shows that all R-classes consist of only one element and hence B is R-trivial.
  On the other hand, B is not L-trivial since {ab, ba} forms an L-class since b · ab = baanda·ba=ab. HenceBisalsonotJ-trivial.</p>
</blockquote>

CC BY-SA 2.5
2010-12-03T22:17:30.230Z
'menagerie of monoids' is just neat.
Suresh Venkat
CC BY-SA 2.5
2010-12-04T02:23:10.287Z
I find 'menagerie of monoids' mollitiously mirific!
Daniel Apon
CC BY-SA 2.5
2010-12-03T16:32:30.690Z
2010-12-03T16:32:30.690Z
s8soj3o289
<p>A semigroup $S$ is $R\text{-trivial}$ iff $a \: R \: b \Rightarrow a = b$ for all $a, b \in S$ where $R$ is <a href="http://en.wikipedia.org/wiki/Green%27s_relations#The_L.2C_R.2C_and_J_relations" rel="noreferrer">Green's relation</a> $a \: R \: b \Leftrightarrow aS^1 = bS^1$. The set of $R\text{-trivial}$ monoids forms a variety which can be ultimately defined by the equations $(xy)^n x = (xy)^n$.</p>

<p>A language is $R\text{-trivial}$ if its <a href="http://en.wikipedia.org/wiki/Syntactic_monoid" rel="noreferrer">syntactic monoid</a> is $R\text{-trivial}$. This variety of languages is alternatively defined as the set of all languages that can be written as a disjoint union  of languages of the form $A_0^* a_1 A_1^* a_2 \ldots a_n A_n^*$ where $n \geq 0$, $a_1, \ldots, a_n \in A$, $A_i \subseteq A \setminus \{a_{i+1}\}$ for $0 \leq i \leq n-1$. Another definition given in <a href="http://www.liafa.jussieu.fr/~jep/Resumes/Varietes.html" rel="noreferrer">[Pin]</a>, which I'm not familiar with, uses the so-called <em>automates extensifs</em> ("extensive automata"). You can find more results about those languages in <a href="http://www.liafa.jussieu.fr/~jep/Resumes/Varietes.html" rel="noreferrer">[Pin]</a>. There is an English version of this book, I've never read it but I'm pretty sure that you can find the same content.</p>

<p>For the sake of completeness, here is an example of an (artificial) $R\text{-trivial}$ language: $\{b\}^* a \{a,c\}^* b \{a\}^* b \{a,b,c\}^* \cup \{d\}^* \cup abcd$. You can build other examples with the previous definitions. Note that all of the properties of varieties of languages hold for $R\text{-trivial}$ languages, therefore they are closed under union, intersection and complementation. It should help to build more complicated languages.</p>

CC BY-SA 2.5
2010-12-04T17:19:03.580Z
Thanks for the nice and detailed answer. That was exactly what I was searching for.
Albert
CC BY-SA 2.5
2010-12-03T22:13:51.747Z
2010-12-04T17:18:02.460Z
2010-12-04T17:18:02.460Z
Michael Blondin
<p>What is an R-trivial language? What is an R-trivial monoid?</p>

<p>Context: Formal languages. Afaik, R-trivial languages is a subset of the starfree languages.</p>

<p>I mostly have background in formal languages and automata theory but not so much with the syntactic monoid characterization. So it would be nice to give a basic definition with maybe a small example of such a language.</p>

<hr>

<p>(In order to support multiple QA-sites because I don't want to have any QA-site stay behind and to have that question also represented there, I have also posted this question on these other sites: <a href="https://stackoverflow.com/questions/4346608/formal-languages-what-does-r-trivial-mean">stackoverflow.com</a>, <a href="https://math.stackexchange.com/questions/12921/formal-languages-what-does-r-trivial-mean">math.stackexchange.com</a>, <a href="https://mathoverflow.net/questions/48181/formal-languages-what-does-r-trivial-mean">mathoverflow.net</a>. In general I am against cross-posting but in this case, as they all have the same goal to be a complete reference of questions in the specific area, having the question cross posted is the best thing you can do.)</p>

CC BY-SA 2.5
2010-12-03T16:09:03.977Z
duplicate:

http://math.stackexchange.com/questions/12921/formal-languages-what-does-r-trivial-mean

and 

http://mathoverflow.net/questions/48181/formal-languages-what-does-r-trivial-mean
Artem Kaznatcheev
CC BY-SA 2.5
2010-12-03T16:10:30.420Z
a google search reveals that slides 7 of http://www.labri.fr/perso/zeitoun/research/lectures/R-1103.pdf seems to have the answer.
Artem Kaznatcheev
CC BY-SA 2.5
2010-12-03T16:12:32.603Z
@Artem: I don't quite understand/know where to post the question. Also, there are different people on all those sites so it might help everyone if I post it everywhere. Once I get an answer, I will repost it on the other sites.
Albert
CC BY-SA 2.5
2010-12-03T16:14:15.893Z
@Artem: Those slides seems to be about infinite words. Or is that Omega the Kleene star?
Albert
CC BY-SA 2.5
2010-12-03T16:23:10.860Z
Albert: there may be different people on both sites, but the least you could do is tell people you posted on the other site as well and link in both directions. See http://meta.cstheory.stackexchange.com/questions/25/material-to-supplement-the-faq/36#36
Anthony Labarre
CC BY-SA 2.5
2010-12-03T16:27:02.887Z
@Anthony: Ah ok, thanks for the clarification. Will do that.
Albert
CC BY-SA 2.5
2010-12-03T17:11:43.200Z
@Albert, please update the question as per Anthony's suggestion.
Suresh Venkat
CC BY-SA 2.5
2010-12-03T22:30:02.800Z
@Albert: the goal of this site is **NOT** " *becoming a complete reference of questions* ", please read our [faq](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question). Our current policy is also against cross-posting at the same time.
Kaveh
<fl.formal-languages>
formal languages: what does R-trivial mean?
Albert
# formal languages: what does R-trivial mean?

(Asked by: username_0 on 2010-12-03)

What is an R-trivial language? What is an R-trivial monoid?

Context: Formal languages. Afaik, R-trivial languages is a subset of the starfree languages.

I mostly have background in formal languages and automata theory but not so much with the syntactic monoid characterization. So it would be nice to give a basic definition with maybe a small example of such a language.

---

(In order to support multiple QA-sites because I don't want to have any QA-site stay behind and to have that question also represented there, I have also posted this question on these other sites: [stackoverflow.com](https://stackoverflow.com/questions/4346608/formal-languages-what-does-r-trivial-mean), [math.stackexchange.com](https://math.stackexchange.com/questions/12921/formal-languages-what-does-r-trivial-mean), [mathoverflow.net](https://mathoverflow.net/questions/48181/formal-languages-what-does-r-trivial-mean). In general I am against cross-posting but in this case, as they all have the same goal to be a complete reference of questions in the specific area, having the question cross posted is the best thing you can do.)

**Tags:** fl.formal-languages

> **Comments:**
> **username_1**: duplicate:  http://math.stackexchange.com/questions/12921/formal-languages-what-does-r-trivial-mean  and   http://mathoverflow.net/questions/48181/formal-languages-what-does-r-trivial-mean  
> **username_1**: a google search reveals that slides 7 of http://www.labri.fr/perso/zeitoun/research/lectures/R-1103.pdf seems to have the answer.  
> **username_0**: @Artem: I don't quite understand/know where to post the question. Also, there are different people on all those sites so it might help everyone if I post it everywhere. Once I get an answer, I will repost it on the other sites.  
> **username_0**: @Artem: Those slides seems to be about infinite words. Or is that Omega the Kleene star?  
> **username_2**: username_0: there may be different people on both sites, but the least you could do is tell people you posted on the other site as well and link in both directions. See http://meta.cstheory.stackexchange.com/questions/25/material-to-supplement-the-faq/36#36  
> **username_0**: @Anthony: Ah ok, thanks for the clarification. Will do that.  
> **username_3**: @username_0, please update the question as per Anthony's suggestion.  
> **username_4**: @username_0: the goal of this site is **NOT** " *becoming a complete reference of questions* ", please read our [faq](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question). Our current policy is also against cross-posting at the same time.  

---

## 2 answers

### Answer by username_7 on 2010-12-03. Score: 7 | Accepted answer

A semigroup $S$ is $R\text{-trivial}$ iff $a \: R \: b \Rightarrow a = b$ for all $a, b \in S$ where $R$ is [Green's relation](http://en.wikipedia.org/wiki/Green%27s_relations#The_L.2C_R.2C_and_J_relations) $a \: R \: b \Leftrightarrow aS^1 = bS^1$. The set of $R\text{-trivial}$ monoids forms a variety which can be ultimately defined by the equations $(xy)^n x = (xy)^n$.

A language is $R\text{-trivial}$ if its [syntactic monoid](http://en.wikipedia.org/wiki/Syntactic_monoid) is $R\text{-trivial}$. This variety of languages is alternatively defined as the set of all languages that can be written as a disjoint union of languages of the form $A\_0^\* a\_1 A\_1^\* a\_2 \ldots a\_n A\_n^\*$ where $n \geq 0$, $a\_1, \ldots, a\_n \in A$, $A\_i \subseteq A \setminus \{a\_{i+1}\}$ for $0 \leq i \leq n-1$. Another definition given in [[Pin]](http://www.liafa.jussieu.fr/~jep/Resumes/Varietes.html), which I'm not familiar with, uses the so-called *automates extensifs* ("extensive automata"). You can find more results about those languages in [[Pin]](http://www.liafa.jussieu.fr/~jep/Resumes/Varietes.html). There is an English version of this book, I've never read it but I'm pretty sure that you can find the same content.

For the sake of completeness, here is an example of an (artificial) $R\text{-trivial}$ language: $\{b\}^\* a \{a,c\}^\* b \{a\}^\* b \{a,b,c\}^\* \cup \{d\}^\* \cup abcd$. You can build other examples with the previous definitions. Note that all of the properties of varieties of languages hold for $R\text{-trivial}$ languages, therefore they are closed under union, intersection and complementation. It should help to build more complicated languages.

> **Comments:**
> **username_0**: Thanks for the nice and detailed answer. That was exactly what I was searching for.  

---

### Answer by username_5 on 2010-12-03. Score: 3

Perhaps the Menagerie of Monoids diagram will be helpful?

<https://i.sstatic.net/tKSam.png>

from page 5, "On the Representation Theory of Finite J-trivial Monoids", by Denton, et. al. (2010).

A detailed description is also given in Section 2.1,

> The smaller class of R-trivial monoids coincides with the class of so-called *weakly
> ordered monoids* as defined by Schocker [Sch08]. Also, via the right regular representation, any R-trivial monoid can be represented as a monoid of regressive functions on some finite poset P (a function f : P → P is called *regressive* if f(x) ≤ x for every x ∈ P); reciprocally any such monoid is R-trivial. We now present an example of a monoid which is R-trivial, but not J-trivial.
>
> Example 2.3. Take the free left regular band B generated by two idempotents a,b. Multiplication is given by concatenation taking into account the idempotent relations, and then selecting only the two left factors (see for example [Sal07]). So B = {1,a,b,ab,ba} and 1B = B, aB = {a,ab}, bB = {b,ba}, abB = {ab}, and baB = {ba}. This shows that all R-classes consist of only one element and hence B is R-trivial.
> On the other hand, B is not L-trivial since {ab, ba} forms an L-class since b · ab = baanda·ba=ab. HenceBisalsonotJ-trivial.

> **Comments:**
> **username_3**: 'menagerie of monoids' is just neat.  
> **username_6**: I find 'menagerie of monoids' mollitiously mirific!  

---

