Porównywany wzrost liczby klas składniowych i klas Nerode.

Dla języka L ⊆ Σ ^ * zdefiniować składniowej identyczność ≡ z L co najmniej zbieżność na Ď ^ * że nasycone L , tj

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

Teraz zdefiniuj równoważność Nerode jako następującą prawą zgodność:

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

Niech [u] będzie klasą równoważności u w odniesieniu do ≡ i 〈u〉 w odniesieniu do ∼ . Teraz zdefiniuj i (n) jako liczbę różnych [u] dla u rozmiaru n , i zdefiniuj j (n) w podobny sposób dla ∼ .

Teraz pytanie brzmi: jak te dwie funkcje się odnoszą?

Na przykład standardowe twierdzenie (sądzę, Kleene-Schützenberger) mówi, że i (n) jest ograniczone stałą, ilekroć j (n) jest, i wzajemnie.

Pytanie: Czy w tym trendzie jest jakikolwiek inny wynik? Co jeśli jeden z nich jest na przykład wielomianowy?

Wygląda na to, że ten artykuł http://arxiv.org/abs/1010.3263 może mieć znaczenie dla twojego pytania.

Abstrakt stwierdza:

Złożoność stanu zwykłego języka to liczba stanów w minimalnym deterministycznym automacie akceptującym ten język. Złożoność składniowa języka regularnego jest licznością jego półgrupy składniowej. Złożoność składniowa podklasy języków zwykłych jest najgorszym złożonością składniową, przyjmowaną jako funkcja złożoności stanu języków w tej klasie. Badamy złożoność składniową klasy zwykłych języków idealnych i ich uzupełnień, języków zamkniętych. Udowadniamy, że n n - 1 jest wąską górną granicą złożoności prawych ideałów i języków zamkniętych przedrostkiem oraz że istnieją lewe ideały i zamknięte języki przedrostkowe o złożoności złożonej n n $n$$n^{n-1}$, oraz dwustronne ideały i języki zamknięte czynnikowo o złożoności syntaktycznej n n - 2 +(n-2) 2 n - 2 +1.$n^{n-1}+n-1$$n^{n-2}+(n-2)2^{n-2}+1$

Tak więc, o ile rozumiem, odpowiada to na twoje pytanie dotyczące wielkości półgrupy syntaktycznej i Myhill-Nerode: na ogół zgodność syntaktyczna może mieć wykładniczo wiele klas niż relacja Myhill-Nerode.

Ostatni komentarz. Zwykle skończoność obu półgrup dla języków zwykłych przypisuje się M. Rabinowi i D. Scottowi (Automaty skończone i ich problemy decyzyjne. IBM Jourmal. Kwiecień 1959). W szczególności z tekstu Rabina i Scotta wynika, że ​​liczba klas syntaktycznych nie przekracza , gdzie n jest liczbą klas Myhill-Nerode.$n^n$$n$