16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joshua Grochow Aug 18 '10 at 2:07
  • $\begingroup$ 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? $\endgroup$ – Michaël Cadilhac Aug 18 '10 at 13:14
  • $\begingroup$ Indeed. I was just thinking in terms of upper bounds, but of course you are correct. $\endgroup$ – Joshua Grochow Aug 18 '10 at 15:12
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please expand your answer to explain the relevance? $\endgroup$ – Dave Clarke Feb 9 '11 at 10:18
  • $\begingroup$ Just look through the paper! $\endgroup$ – Sergey Feb 9 '11 at 10:27
  • $\begingroup$ 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 $\endgroup$ – Sergey Feb 9 '11 at 10:31
  • 1
    $\begingroup$ By the way, as it follows from the paper listed above there could be exponentially more syntactic classes than Myhill-Nerode classes. $\endgroup$ – Sergey Feb 9 '11 at 11:05
  • $\begingroup$ 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! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 9 '11 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.