formal languages: what does R-trivial mean?

Question

What is an R-trivial language? I.e. what is the definition?

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: cstheory.stackexchange.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.)

Answer 1

Monoid is R-trivial if the Green's relation R on it coincides with the equality.

Answer 2

A very good answer has also 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.

Answer 3

Another characterization, perhaps clearer for CS people, is that a regular language is R-trivial iff its minimal deterministic finite automaton is partially ordered, that is, it has no cycles (self-loops are not considered as cycles).