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

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?

• Certainly i(n) is always an upper bound on j(n), so presumably you are only asking about implication in the other direction, for example: if j(n) is bounded above by a polynomial, must i(n) be as well? Aug 18, 2010 at 2:07
• Well, the other way around still makes sense, no? For instance I may ask: if i(n) is exponential, is there a simple criterion from which I can conclude that j(n) is also exponential? Aug 18, 2010 at 13:14
• Indeed. I was just thinking in terms of upper bounds, but of course you are correct. Aug 18, 2010 at 15:12

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.