<p>It seems that this paper     <a href="http://arxiv.org/abs/1010.3263">http://arxiv.org/abs/1010.3263</a>  may be relevant to your question. </p>

<p>The abstract states:</p>

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

<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-09T10:18:47.767Z
Could you please expand your answer to explain the relevance?
Dave Clarke
CC BY-SA 2.5
2011-02-09T10:27:37.270Z
Just look through the paper!
Sergey
CC BY-SA 2.5
2011-02-09T10:31:06.113Z
I'm sorry, I inserted invalid link. Actually I was intended to give not the answer (in some sense the answer is contained in the paper I'd mentioned) but a comment, but unfortunately I don't know how to do it technically
Sergey
CC BY-SA 2.5
2011-02-09T11:05:48.100Z
By the way, as it follows from the paper listed above there could be exponentially more syntactic classes than Myhill-Nerode classes.
Sergey
CC BY-SA 2.5
2011-02-09T14:01:45.703Z
It would be nice if you summarized the result of the paper which is relevant to this question, and it will turn into a perfect answer here. Please :) Some of us (me) are pretty interested to see answers to a long-standing unanswered question here!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-09T10:15:23.693Z
2011-02-09T15:01:34.700Z
2011-02-09T15:01:34.700Z
Sergey
<p>For a language <i>L ⊆ Σ^*</i>, define the <i>syntactic congruence</i> <i>≡</i> of <i>L</i> as the least congruence on <i>Σ^*</i> that saturates <i>L</i>, i.e. :</p>

<p><i>u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].</i></p>

<p>Now define the <i>Nerode equivalence</i> as the following right congruence :</p>

<p><i>u ∼ v ⇔ (∀ x)[ux ∈ L ↔ vx ∈ L].</i></p>

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

<p>Now the question is, how do the two functions relate ?</p>

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

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

CC BY-SA 2.5
2010-08-18T02:07:40.027Z
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?
Joshua Grochow
CC BY-SA 2.5
2010-08-18T13:14:18.700Z
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?
Michaël Cadilhac
CC BY-SA 2.5
2010-08-18T15:12:19.463Z
Indeed.  I was just thinking in terms of upper bounds, but of course you are correct.
Joshua Grochow
<automata-theory><fl.formal-languages>
Compared growth of the number of syntactic classes and Nerode classes.
Michaël Cadilhac
# Compared growth of the number of syntactic classes and Nerode classes.

(Asked by: username_0 on 2010-08-17)

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?

**Tags:** automata-theory, fl.formal-languages
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_1**: Indeed.  I was just thinking in terms of upper bounds, but of course you are correct.  

---

## 1 answers

### Answer by username_2 on 2011-02-09. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_3**: Could you please expand your answer to explain the relevance?  
> **username_2**: Just look through the paper!  
> **username_2**: I'm sorry, I inserted invalid link. Actually I was intended to give not the answer (in some sense the answer is contained in the paper I'd mentioned) but a comment, but unfortunately I don't know how to do it technically  
> **username_2**: By the way, as it follows from the paper listed above there could be exponentially more syntactic classes than Myhill-Nerode classes.  
> **username_4**: It would be nice if you summarized the result of the paper which is relevant to this question, and it will turn into a perfect answer here. Please :) Some of us (me) are pretty interested to see answers to a long-standing unanswered question here!  

---

