Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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, math.stackexchange.com, mathoverflow.net. 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.)

share|improve this question
4  
3  
a google search reveals that slides 7 of labri.fr/perso/zeitoun/research/lectures/R-1103.pdf seems to have the answer. –  Artem Kaznatcheev Dec 3 '10 at 16:10
    
@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 Dec 3 '10 at 16:12
    
@Artem: Those slides seems to be about infinite words. Or is that Omega the Kleene star? –  Albert Dec 3 '10 at 16:14
2  
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 meta.cstheory.stackexchange.com/questions/25/… –  Anthony Labarre Dec 3 '10 at 16:23

2 Answers 2

up vote 6 down vote accepted

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 $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 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], which I'm not familiar with, uses the so-called automates extensifs ("extensive automata"). You can find more results about those languages in [Pin]. 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.

share|improve this answer
    
Thanks for the nice and detailed answer. That was exactly what I was searching for. –  Albert Dec 4 '10 at 17:19
    
You're welcome! –  Michael Blondin Dec 4 '10 at 17:29

Perhaps the Menagerie of Monoids diagram will be helpful?

http://i.stack.imgur.com/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.

share|improve this answer
    
'menagerie of monoids' is just neat. –  Suresh Venkat Dec 3 '10 at 22:17
    
I find 'menagerie of monoids' mollitiously mirific! –  Daniel Apon Dec 4 '10 at 2:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.