Jumlah kelas ekivalensi dalam bahasa reguler sebagai fungsi dari ukuran DFA

Pertanyaan ini terkait dengan pertanyaan terbaru oleh Janoma .

Latar Belakang

Dalam pemrograman kendala, sebuah rutin global yang kendala $c$ selama domain $D$ adalah sepasang $(s, M)$ dengan $s$ tupel variabel (lingkup) dan $M$ DFA atas domain $D$ . Tugas $\theta$ to $s$ memuaskan $c$ jika $M$ menerima string $\theta(s_1)\theta(s_2)\ldots\theta(s_n)$ .

Di bawah, asumsikan bahwa domain $D$ sudah diperbaiki. Tentukan relasi ekivalensi $\sim$ pada set string $T = D^{|s|}$sehingga $a \sim b$ jika untuk setiap DFA $M$ baik $a, b \in L(M)$ atau $a, b \not\in L(M)$ . Secara intuitif, dua string setara jika jika tidak ada DFA dapat membedakannya. Jika itu benar, maka mereka juga memenuhi batasan reguler yang sama .

Jika kita tidak membatasi DFA dengan cara apa pun, maka himpunan kelas ekivalensi $T/{\sim}$ hanyalah $T$ itu sendiri. Saya tertarik pada jumlah kelas ekivalensi wrt. $\sim$ sebagai fungsi dari jumlah status $n$ yang kami izinkan untuk DFA. Jelas, jika $n = |D|^{|s|}$(abaikan konstanta) lalu $|T/{\sim}| = |T|$. (Tentu saja, $n$ sini sendiri akan menjadi fungsi $|s|$ .)

Pertanyaan

1. Apa $n$ terkecil untuk yang $|T/{\sim}| = |T|$?
2. Apa yang terjadi di bawah itu? Khususnya,
   • apakah ada $n$ sehingga $|T/{\sim}| = O(|s|^{|D|})$ ?
   • apakah ada $n$ sehingga $|T/{\sim}| = O(|s| \times |D|)$ ?

$|s|^{|D|}$

$k$$\geq k$

Jawaban untuk Pertanyaan 1,

Apa n terkecil untuk yang | 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})$ .

yang diperoleh di

Robson, JM , Memisahkan string dengan automata kecil , Inf. Proses. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051 .