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

  • 1
    $\begingroup$ Also asked elsewhere: cstheory.stackexchange.com/questions/3503/… and mathoverflow.net/questions/48181/… $\endgroup$
    – rgrig
    Dec 3 '10 at 17:29
  • 2
    $\begingroup$ The question was answered on SO. $\endgroup$ Dec 3 '10 at 20:37
  • $\begingroup$ Curious: Why the downvotes? $\endgroup$
    – Albert
    Dec 4 '10 at 16:58
  • $\begingroup$ Why the cross-posting? $\endgroup$ Dec 4 '10 at 18:05
  • $\begingroup$ @Robin: To help people find the question & answer. Is that bad? And still, even if that is bad, why is the question bad then? $\endgroup$
    – Albert
    Dec 4 '10 at 18:09

The best answer has been given here by Michael Blondin:

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 a $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.

  • $\begingroup$ This is a copy of Blondin's answer from cstheory. How good of you to post it here for the benefit of users who are unable to follow web links. $\endgroup$ Dec 4 '10 at 19:14
  • $\begingroup$ @Robin: Haven't you read my first sentence? Again, I quite fail to understand why it is bad to have that copied here. $\endgroup$
    – Albert
    Dec 5 '10 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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