15
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – goblin GONE
    Commented Jun 13, 2016 at 12:35
  • 1
    $\begingroup$ @goblin A language is just some arbitrary subset of $X^{\ast}$ (i.e. set of finite sequences, or the free monoid); they encode words. $\endgroup$
    – StefanH
    Commented Jun 13, 2016 at 12:45
  • $\begingroup$ 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. $\endgroup$
    – goblin GONE
    Commented Jun 13, 2016 at 15:09
  • $\begingroup$ @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! $\endgroup$
    – StefanH
    Commented Jun 13, 2016 at 15:25
  • $\begingroup$ @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$). $\endgroup$
    – StefanH
    Commented Jun 13, 2016 at 15:44

3 Answers 3

Reset to default
12
$\begingroup$

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.

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ What does "homomorphic to" mean? That is, which direction does the homomorphism go, and is it required to be surjective? $\endgroup$
    – Emil Jeřábek
    Commented Jun 9, 2016 at 22:06
  • 2
    $\begingroup$ It means that any finite monoid is a submonoid of a syntactic monoid. This is confirmed in kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf $\endgroup$
    – Denis
    Commented Jun 9, 2016 at 23:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Leupold
    Commented Jun 10, 2016 at 7:33
13
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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