Anzahl der Äquivalenzklassen in regulären Sprachen als Funktion der DFA-Größe

Diese Frage bezieht sich auf eine aktuelle Frage von Janoma .

Hintergrund

In Constraint - Programmierung, ein regelmäßiger globaler constraint $c$ über einen Domain - $D$ ist ein Paar $(s, M)$ mit $s$ einem Tupel von Variablen (der Umfang) , und $M$ ein DFA über die Domäne $D$ . Eine Zuordnung $\theta$ zu $s$ erfüllt $c$ wenn $M$ die Zeichenkette $\theta(s_1)\theta(s_2)\ldots\theta(s_n)$ akzeptiert .

Nehmen Sie unten an, dass die Domäne $D$ festgelegt ist. Definieren Sie eine Äquivalenzbeziehung $\sim$ über die Menge der Zeichenfolgen $T = D^{|s|}$so dass $a \sim b$ wenn für jeden DFA $M$ entweder $a, b \in L(M)$ oder $a, b \not\in L(M)$ . Intuitiv sind zwei Zeichenfolgen gleichwertig, wenn kein DFA sie unterscheiden kann. Wenn dies zutrifft, erfüllen sie auch die gleichen regulären Einschränkungen.

Wenn wir die DFAs in keiner Weise einschränken, ist die Menge der Äquivalenzklassen $T/{\sim}$ nur $T$ selbst. Ich interessiere mich für die Anzahl der Äquivalenzklassen. $\sim$ als Funktion der Anzahl der Zustände $n$ , die wir für den DFA zulassen. Klar, wenn $n = |D|^{|s|}$(Konstanten ignorieren) dann $|T/{\sim}| = |T|$. (Natürlich wird $n$ hier selbst eine Funktion von $|s|$ .)

Fragen

1. Was ist das kleinste $n$ für welches $|T/{\sim}| = |T|$?
2. Was passiert darunter? Im Speziellen,
   • gibt es ein $n$ so dass $|T/{\sim}| = O(|s|^{|D|})$ ?
   • gibt es ein $n$ so dass $|T/{\sim}| = O(|s| \times |D|)$ ?

$|s|^{|D|}$

$k$$\geq k$

Antwort auf Frage 1,

Was ist das kleinste n für welches | 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})$ .

welches in erhalten wurde

Robson, JM , Trennen von Strings mit kleinen Automaten , Inf. Prozess. Lette. 30, Nr. 4, 209-214 (1989). ZBL0666.68051 .