Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals 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, 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.)

share|improve this question
1  
2  
The question was answered on SO. –  Qiaochu Yuan Dec 3 '10 at 20:37
    
Curious: Why the downvotes? –  Albert Dec 4 '10 at 16:58
    
Why the cross-posting? –  Robin Chapman Dec 4 '10 at 18:05
    
@Robin: To help people find the question & answer. Is that bad? And still, even if that is bad, why is the question bad then? –  Albert Dec 4 '10 at 18:09

1 Answer 1

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.

share|improve this answer
    
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. –  Robin Chapman Dec 4 '10 at 19:14
    
@Robin: Haven't you read my first sentence? Again, I quite fail to understand why it is bad to have that copied here. –  Albert Dec 5 '10 at 0:38

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.