MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. : $$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \in S \leftrightarrow xvy \in S].$$

Now define the Nerode equivalence as the following right congruence : $$u \sim_S v \Leftrightarrow (\forall x)[ux \in S \leftrightarrow vx \in S].$$

Let $[u]_\equiv$ be the equivalence class of $u$ with respect to $\equiv_S$ and $[u]_\sim$ with respect to $\sim_S$.

Now define $i_\equiv (n)$ to be the number of different $[u]_\equiv$ for $u$ of size $n$.

Define $i_\sim(n)$ in a similar fashion.

Now the question is, how do the two $i$ functions relate ?

For instance, a standard theorem says that $i_\sim(n)$ is bounded by a constant whenever $i_\equiv(n)$ is, and reciprocally. Is there any other result in this trend?

share|cite|improve this question
up vote 2 down vote accepted

Let $L$ be a regular language. Then the index of the Nerode equivalence of $L$ is the number of states $n$ of its minimal automaton and the index its syntactic congruence is the size $N$ of its syntactic monoid.

It is well known that $N \leqslant n^n$ and that this bound can be reached on a three-letter alphabet. I will now slightly modify this construction to show that, for each $n$, there is a language $L_n$ on a four-letter alphabet $\{a, b, c, d\}$ such that, for $k$ large enough, $i_\sim(k) = n$ and $i_\equiv(k) = n^n$.

Consider $a, b, c, d$ as transformations on $\{1, ..., n\}$: $a$ is the cyclic permutation, $b$ is a transposition, say $(2, 1)$, $c$ maps every state $\not= n$ to itself, but maps $n$ to $1$. Finally $d$ is the identity. This defines a deterministic automaton $\mathcal{A}$, with $1$ as the initial and unique final state. Let $L_n$ be the language recognized by this automaton. Now, for $k \geqslant n$, the words $d^{k-j}a^j$ have the same length $k$ and define $n$ distinct $\sim$-classes, since $1 \cdot d^{k-j}a^j = j$ in $\mathcal{A}$. Thus $i_\sim(k) = n$ for $k \geqslant n$.

Now, it is known that the transformation monoid generated by $\{a, b, c\}$ is the full transformation monoid $\mathcal{T}_n$, which has $n^n$ elements. For each $s \in \mathcal{T}_n$, let $u_s$ be a shortest word representing $s$ and let $R = \max \{ |u_s| \mid s \in \mathcal{T}_n\}$ (an obvious upper-bound for $R$ is $n^n$). Now, for $k \geqslant R$, the $n^n$ words $d^{k-|u_s|}u_s$ (for $s \in \mathcal{T}_n$) have the same length $k$ and define distinct elements of $\mathcal{T}_n$. Therefore $i_\equiv(k) = n^n$ for $k \geqslant R$.

share|cite|improve this answer
Thanks J.-É.! I remembered this question when seeing this related new paper by Brzozowski and Szykuła: – Michaël Jan 3 '14 at 12:16

Since you are talking about size of monoid elements, I assume you want a finitely geerated monoid and wish to use word length for size.

Since ${\equiv}\subseteq {\sim}$ trivially one has $i_{\sim}(n)\leq i_{\equiv}(n)$. I believe that in the other direction no good bounds hold. For instance let $G$ be the Grigorchuk group and let $P$ be a parabolic subgroup with respect to a generic boundary point of the 2-ary tree. Then the minimal automaton for $P$ is the Schreier graph for $G/P$, which is known to be infinte with polynomial growth. On the other hand $G$ is just infinite so $G$ is the syntactic monoid of $P$. $G$ is known to have intermediate growth. Thus the syntactic congruence for $P$ has many more classes in a strong sense than the Nerode congruence.

share|cite|improve this answer

Your Answer


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.