Liczba klas równoważności w zwykłych językach jako funkcja wielkości DFA

To pytanie jest związane z ostatnim pytaniem przez Janoma .

tło

Programowania więzów, A regularne globalny ograniczenie $c$ przez domeny $D$ jest parą $(s, M)$ z $s$ krotki zmiennych (zakres, w) oraz $M$ DFA na obszarze $D$ . Przypisanie $\theta$ do $s$ spełnia warunek $c$ jeśli $M$ przyjmuje ciąg $\theta(s_1)\theta(s_2)\ldots\theta(s_n)$ .

Poniżej załóżmy, że domena $D$ jest stała. Zdefiniuj relację równoważności $\sim$ na zbiorze ciągów $T = D^{|s|}$tak, że $a \sim b$ jeśli dla każdego DFA $M$ albo $a, b \in L(M)$ lub $a, b \not\in L(M)$ . Intuicyjnie dwa ciągi znaków są równoważne, jeśli DFA ich nie rozróżnia. Jeśli to prawda, spełniają one również te same regularne ograniczenia.

Jeśli nie ograniczymy DFA w żaden sposób, to zestaw klas równoważności $T/{\sim}$ jest po prostu sam $T$Interesuje mnie liczba klas równoważności wrt. $\sim$ jako funkcję liczby stanów $n$ , które dopuszczamy dla DFA. Oczywiście, jeśli $n = |D|^{|s|}$(zignoruj ​​stałe), a następnie $|T/{\sim}| = |T|$. (Oczywiście $n$ tutaj samo będzie funkcją $|s|$ .)

pytania

1. Jaka jest najmniejsza liczba $n$ dla której $|T/{\sim}| = |T|$?
2. Co dzieje się poniżej? W szczególności,
   • czy jest taki $n$ , że $|T/{\sim}| = O(|s|^{|D|})$ ?
   • czy jest taki $n$ , że $|T/{\sim}| = O(|s| \times |D|)$ ?

$|s|^{|D|}$

$k$$\geq k$

Odpowiedź na pytanie 1,

Jaka jest najmniejsza liczba n, dla której | T / ∼ | = | T | $n$$|T/{\sim}|=|T|$

$$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$ $\mathrm{sep}(w,x)$$w$$x$$n$

$n=O(s^{2/5}(\log s)^{3/5})$

który został uzyskany w

Robson, JM , Rozdzielanie ciągów za pomocą małych automatów , Inf. Proces. Łotysz. 30, nr 4, 209-214 (1989). ZBL0666.68051 .