3
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks J.-É.! I remembered this question when seeing this related new paper by Brzozowski and Szykuła: arxiv.org/abs/1401.0157 $\endgroup$
    – Michaël
    Jan 3, 2014 at 12:16
1
$\begingroup$

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.

$\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.