Dibandingkan pertumbuhan jumlah kelas sintaksis dan kelas Nerode.

Untuk bahasa L ⊆ Σ ^ * , tentukan kongruensi sintaksis ≡ dari L sebagai kongruensi terkecil pada on ^ * yang menjenuhkan L , yaitu:

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

Sekarang tentukan kesetaraan Nerode sebagai kongruensi kanan berikut:

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

Biarkan [u] menjadi kelas kesetaraan u sehubungan dengan ≡ dan <u> sehubungan dengan ~ . Sekarang mendefinisikan i (n) menjadi jumlah yang berbeda [u] untuk u ukuran n , dan menentukan j (n) dengan cara yang sama untuk ~ .

Sekarang pertanyaannya adalah, bagaimana hubungan kedua fungsi tersebut?

Sebagai contoh, teorema standar (Kleene-Schützenberger, saya percaya) mengatakan bahwa i (n) dibatasi oleh konstanta setiap kali j (n) adalah, dan secara timbal balik.

Pertanyaan: Apakah ada hasil lain dalam tren ini? Bagaimana jika salah satunya adalah polinomial, misalnya?

Tampaknya makalah ini http://arxiv.org/abs/1010.3263 mungkin relevan dengan pertanyaan Anda.

Status abstrak:

$n$$n^{n-1}$$n^{n-1}+n-1$$n^{n-2}+(n-2)2^{n-2}+1$

Jadi, sejauh yang saya mengerti, ini menjawab pertanyaan Anda tentang ukuran sintaksis dan semigroup Myhill-Nerode: secara umum, kongruensi sintaksis mungkin memiliki banyak kelas secara eksponensial daripada hubungan Myhill-Nerode.

$n^n$$n$