Skip to main content
edited tags
Link
Michaël
  • 786
  • 3
  • 12
Source Link
Michaël
  • 786
  • 3
  • 12

What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?

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?