Сравнивался рост числа синтаксических классов и классов Nerode.

Для языка L ⊆ Σ ^ * определите синтаксическую конгруэнцию ≡ в L как наименьшую конгруэнцию на Σ ^ *, которая насыщает L , т.е.

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

Теперь определим эквивалентность Nerode как следующее правильное сравнение:

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

Пусть [u] - класс эквивалентности u по ≡ и 〈u respect по ∼ . Теперь определите i (n) как число различных [u] для u размера n , и определите j (n) аналогичным образом для ∼ .

Теперь вопрос в том, как эти две функции связаны?

Например, стандартная теорема (я полагаю, Kleene-Schützenberger) говорит, что i (n) ограничена константой, когда j (n) есть, и наоборот.

Вопрос: Есть ли другой результат в этом направлении? Что, если один из них, например, является полиномом?

Кажется, что этот документ http://arxiv.org/abs/1010.3263 может иметь отношение к вашему вопросу.

Аннотация гласит:

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

Таким образом, насколько я понимаю, это отвечает на ваш вопрос о размерах синтаксической и полугруппы Майилла-Нерода: в общем, синтаксическая конгруэнция может иметь экспоненциально много классов, чем отношение Майхилла-Нерода.

$n^n$$n$