Compared growth of the number of syntactic classes and Nerode classes.

Question

For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :

u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].

Now define the Nerode equivalence as the following right congruence :

u ∼ v ⇔ (∀ x)[ux ∈ L ↔ vx ∈ L].

Let [u] be the equivalence class of u with respect to ≡ and 〈u〉 with respect to ∼. Now define i(n) to be the number of different [u] for u of size n, and define j(n) in a similar fashion for ∼.

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

For instance, a standard theorem (Kleene-Schützenberger, I believe) says that i(n) is bounded by a constant whenever j(n) is, and reciprocally.

Question: Is there any other result in this trend? What if one of them is polynomial, for instance?

Answer 1

It seems that this paper http://arxiv.org/abs/1010.3263 may be relevant to your question.

The abstract states:

The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n-1}$ is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity $n^{n-1}+n-1$, and two-sided ideals and factor-closed languages of syntactic complexity $n^{n-2}+(n-2)2^{n-2}+1$.

Thus, as far as I understand, this answers your question about the sizes of syntactic and Myhill-Nerode semigroup: in general, syntactic congruence may have exponentially many classes than Myhill-Nerode relation.

The last comment. Usually the finitness of both semigroups for regular languages is attributed to M.Rabin and D.Scott (Finite automata and their decision problems. IBM Jourmal. April 1959). In particular, it follows from the text of Rabin and Scott that the number of syntactic classes does not exceed $n^n$, where $n$ is the number of Myhill-Nerode classes.