<p>The terminology <em>rigid</em> seems to be relatively new compared to the term <em>disjunctive</em> used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is <em>disjunctive</em> if and only if the <a href="https://en.wikipedia.org/wiki/Syntactic_monoid">syntactic congruence</a> of $P$ in $M$ is the equality relation. Thus a monoid is the syntactic monoid of a language if and only if it contains a disjunctive subset.</p>

<p>With this characterisation in hand, it is easy to find finite monoids that are not syntactic monoid of any language: take the monoid $\{1, a, b, c\}$ in which $1$ is the identity and the rest of the multiplication is defined by $xy = y$ for all $x, y \in \{a,b,c\}$. This result is folklore (&lt; 1980).</p>

CC BY-SA 3.0
2016-06-10T10:46:53.597Z
2016-06-10T10:46:53.597Z
J.-E. Pin
<p>In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check.</p>

<p><strong>Definition:</strong> Let $M$ be a monoid, and $Y \subseteq M$.  Define the congruence relation $\equiv_Y$ over $M$ by $x \equiv_Y y$ iff $\big[\forall w, z \in M$, $wxz \in Y \Leftrightarrow wyz \in Y\big]$.</p>

<p><strong>Definition:</strong> Let $M$ be a monoid.  A subset $Y \subseteq M$ is <em>rigid</em> if $x \equiv_Y y \Rightarrow x = y$ for all $x, y \in M$.  (Equivalently, $M \approx M/\equiv_Y$.)</p>

<p><strong>Theorem:</strong> A finite monoid $M$ is the syntactic monoid of some regular language iff it has a rigid subset.</p>

<p>Of course, $M$ being finite, this property is decidable.</p>

CC BY-SA 3.0
2016-06-10T09:13:08.340Z
2016-06-10T09:13:08.340Z
Michaël Cadilhac
<p>It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without paywall it would be great. I requested the full-text on ResearchGate.</p>

<p><strong>Title</strong>: <a href="http://www.sciencedirect.com/science/article/pii/002001909290135I">Which Finite Monoids are Syntactic Monoids of Rational omega-Languages</a>.</p>

<p><strong>Authors</strong>: Phan Trung Huy, Igor Litovsky, Do Long Van</p>

<p><strong>Abstract</strong>: A notion of ω-rigid sets for a finite monoid is introduced. We prove that a finite monoid M is the Arnold's syntactic monoid of some rational ω-language (ω-syntactic for short) if and only if there exists an ω-rigid set for M. This property is shown to be decidable for the finite monoids. Relationship between the family of ω-syntactic monoids and that of ∗-syntactic monoids (i.e. the syntactic monoids of rational languages of finite words) is established.</p>

<hr>

<p>Additionally, the wikipedia page on syntactic monoids states:</p>

<ul>
<li>Every finite monoid is homomorphic to the syntactic monoid of some non-trivial language,[1] but not every finite monoid is isomorphic to a syntactic monoid.[2]</li>
<li>Every finite group is isomorphic to the syntactic monoid of some non-trivial language.[1]</li>
</ul>

<p>[1] McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.</p>

<p>[2] Lawson (2004) p.233</p>

CC BY-SA 3.0
2016-06-09T22:06:13.987Z
What does "homomorphic to" mean? That is, which direction does the homomorphism go, and is it required to be surjective?
Emil Jeřábek
CC BY-SA 3.0
2016-06-09T23:40:35.453Z
It means that any finite monoid is a submonoid of a syntactic monoid.
This is confirmed in http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf
Denis
CC BY-SA 3.0
2016-06-10T07:33:56.910Z
Just a note: the RIMS publications of the automata group meetings are usually not refereed. So be careful regarding the contents, if you cannot verify them yourself.
Peter Leupold
CC BY-SA 3.0
2016-06-09T19:46:55.050Z
2016-06-09T21:03:02.850Z
2016-06-09T21:03:02.850Z
Denis
<p>Let $L \subseteq X^{\ast}$ be some language, then we define the <em>syntactic congruence</em> as
$$
 u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L
$$
and the quotient monoid $X^{\ast} / \sim_L$ is called the <em>syntactic monoid</em> of $L$.</p>

<blockquote>
  <p>Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?</p>
</blockquote>

<p>For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.</p>

<p>Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).</p>

CC BY-SA 3.0
2016-06-13T12:35:57.687Z
What does the term "language" mean in this context? A submonoid, perhaps? **Edit.** Well, I guess not that, since this would mean that $\sim$ was always the equality relation. Perhaps they're arbitrary subsets?
goblin GONE
CC BY-SA 3.0
2016-06-13T12:45:20.190Z
@goblin A language is just some arbitrary subset of $X^{\ast}$ (i.e. set of finite sequences, or the free monoid); they encode words.
StefanH
CC BY-SA 3.0
2016-06-13T15:09:41.747Z
Thanks. I was beginning to surmise as much. Is there any connection between what you're doing here and the quotient group $G/N$ where $N$ is a normal subgroup of a group $G$? Either way, this seems very cool.
goblin GONE
CC BY-SA 3.0
2016-06-13T15:25:18.063Z
@goblin If you are looking for an analogy $X^{\ast}$ and $\sim$ to $G$ and $N$, then I do not see any direct relationship merely then the abstract one of forming factor structures (and hence inducing canonical morphisms); but there are other ways that groups could enter the picture here, for example the syntactic monoid could be a group, or $L$ could also be a group (which generalises to the notion of automatic groups I guess, but I am no expert here). I would suggest you open a new post if you are interested how groups could enter the stage here!
StefanH
CC BY-SA 3.0
2016-06-13T15:44:11.517Z
@goblin Maybe another analogy which in some ways might be familiar to group theorist: Given a language $L$ we can form an automaton (not necessariliy finite!) to accept $L$ (for example with the nerode right classes). Now if $Q$ denotes the states, then we have an action $Q \times X^{\ast} \to Q$, which gives a mapping $X^{\ast} \to Q^Q$. Now the kernel of this action as a congruence relation refines $\sim$ from above as $q_0\cdot xuy = q_0\cdot xvy$ then (but merely $u\sim v$ may send them to different final states, hence it may properly refine $\sim$).
StefanH
<fl.formal-languages><automata-theory><regular-language><algebra><monoid>
On the realisation of monoids as syntactic monoids of languages
StefanH
# On the realisation of monoids as syntactic monoids of languages

(Asked by: username_0 on 2016-06-09)

Let $L \subseteq X^{\ast}$ be some language, then we define the *syntactic congruence* as
$$
u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L
$$
and the quotient monoid $X^{\ast} / \sim\_L$ is called the *syntactic monoid* of $L$.

> Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?

For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.

Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).

**Tags:** fl.formal-languages, automata-theory, regular-language, algebra, monoid

> **Comments:**
> **username_1**: What does the term "language" mean in this context? A submonoid, perhaps? **Edit.** Well, I guess not that, since this would mean that $\sim$ was always the equality relation. Perhaps they're arbitrary subsets?  
> **username_0**: @goblin A language is just some arbitrary subset of $X^{\ast}$ (i.e. set of finite sequences, or the free monoid); they encode words.  
> **username_1**: Thanks. I was beginning to surmise as much. Is there any connection between what you're doing here and the quotient group $G/N$ where $N$ is a normal subgroup of a group $G$? Either way, this seems very cool.  
> **username_0**: @goblin If you are looking for an analogy $X^{\ast}$ and $\sim$ to $G$ and $N$, then I do not see any direct relationship merely then the abstract one of forming factor structures (and hence inducing canonical morphisms); but there are other ways that groups could enter the picture here, for example the syntactic monoid could be a group, or $L$ could also be a group (which generalises to the notion of automatic groups I guess, but I am no expert here). I would suggest you open a new post if you are interested how groups could enter the stage here!  
> **username_0**: @goblin Maybe another analogy which in some ways might be familiar to group theorist: Given a language $L$ we can form an automaton (not necessariliy finite!) to accept $L$ (for example with the nerode right classes). Now if $Q$ denotes the states, then we have an action $Q \times X^{\ast} \to Q$, which gives a mapping $X^{\ast} \to Q^Q$. Now the kernel of this action as a congruence relation refines $\sim$ from above as $q_0\cdot xuy = q_0\cdot xvy$ then (but merely $u\sim v$ may send them to different final states, hence it may properly refine $\sim$).  

---

## 3 answers

### Answer by username_4 on 2016-06-09. Score: 12 | Accepted answer

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without paywall it would be great. I requested the full-text on ResearchGate.

**Title**: [Which Finite Monoids are Syntactic Monoids of Rational omega-Languages](http://www.sciencedirect.com/science/article/pii/002001909290135I).

**Authors**: Phan Trung Huy, Igor Litovsky, Do Long Van

**Abstract**: A notion of ω-rigid sets for a finite monoid is introduced. We prove that a finite monoid M is the Arnold's syntactic monoid of some rational ω-language (ω-syntactic for short) if and only if there exists an ω-rigid set for M. This property is shown to be decidable for the finite monoids. Relationship between the family of ω-syntactic monoids and that of ∗-syntactic monoids (i.e. the syntactic monoids of rational languages of finite words) is established.

---

Additionally, the wikipedia page on syntactic monoids states:

* Every finite monoid is homomorphic to the syntactic monoid of some non-trivial language,[1] but not every finite monoid is isomorphic to a syntactic monoid.[2]
* Every finite group is isomorphic to the syntactic monoid of some non-trivial language.[1]

[1] McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) p.233

> **Comments:**
> **username_5**: What does "homomorphic to" mean? That is, which direction does the homomorphism go, and is it required to be surjective?  
> **username_4**: It means that any finite monoid is a submonoid of a syntactic monoid. This is confirmed in http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf  
> **username_6**: Just a note: the RIMS publications of the automata group meetings are usually not refereed. So be careful regarding the contents, if you cannot verify them yourself.  

---

### Answer by username_2 on 2016-06-10. Score: 13

The terminology *rigid* seems to be relatively new compared to the term *disjunctive* used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is *disjunctive* if and only if the [syntactic congruence](https://en.wikipedia.org/wiki/Syntactic_monoid) of $P$ in $M$ is the equality relation. Thus a monoid is the syntactic monoid of a language if and only if it contains a disjunctive subset.

With this characterisation in hand, it is easy to find finite monoids that are not syntactic monoid of any language: take the monoid $\{1, a, b, c\}$ in which $1$ is the identity and the rest of the multiplication is defined by $xy = y$ for all $x, y \in \{a,b,c\}$. This result is folklore (< 1980).


---

### Answer by username_3 on 2016-06-10. Score: 11

In a more elementary way than username_4's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check.

**Definition:** Let $M$ be a monoid, and $Y \subseteq M$. Define the congruence relation $\equiv\_Y$ over $M$ by $x \equiv\_Y y$ iff $\big[\forall w, z \in M$, $wxz \in Y \Leftrightarrow wyz \in Y\big]$.

**Definition:** Let $M$ be a monoid. A subset $Y \subseteq M$ is *rigid* if $x \equiv\_Y y \Rightarrow x = y$ for all $x, y \in M$. (Equivalently, $M \approx M/\equiv\_Y$.)

**Theorem:** A finite monoid $M$ is the syntactic monoid of some regular language iff it has a rigid subset.

Of course, $M$ being finite, this property is decidable.


---

