Memisahkan daftar kata

Ada masalah terbuka dalam bahasa formal yang dikenal sebagai Masalah Pemisahan; yang secara singkat dinyatakan memiliki dua string panjang , seberapa besar DFA diperlukan untuk "memisahkan" mereka, artinya menerima satu string tetapi menolak yang lain.$n$

Berikut adalah beberapa makalah yang relevan 1 , 2 . (Saya punya beberapa lagi tetapi saya tidak memiliki reputasi yang cukup untuk mempostingnya).

Ini semua membahas masalah memisahkan dua string yang berbeda. Saya bertanya-tanya apakah ada apapun pekerjaan yang dilakukan di wilayah yang memisahkan daftar string, artinya diberikan dua daftar string, dan B , apa ukuran diperlukan DFA untuk menerima setiap string dalam A dan menolak setiap string dalam B . Masalah ini setara dengan golf regex.$A$$B$$A$$B$

Ada beberapa pertanyaan dasar yang telah saya kerjakan seperti apakah salah satu daftar berukuran atau jika semua string memiliki panjang yang berbeda.$1$

Saya telah mencari-cari tetapi belum menemukan makalah yang berhubungan dengan jenis masalah ini. Apakah ada penelitian yang dilakukan di bidang ini?

Terima kasih sebelumnya.

$K$$L$$M$$K \subseteq M$$M \cap L = \emptyset$

$K$$L$$M$

Dalam makalah 2013 , penulis menunjukkan:

Meskipun masalah pemisahan sering terjadi, namun belum dipelajari secara sistematis, bahkan dalam kasus bahasa reguler yang terbatas namun menantang.

Namun mereka menyebutkan beberapa kasus khusus yang telah diselesaikan, dan yang paling pasti mencakup kasus yang terbatas.

Anda mungkin juga ingin melihat Craig interpolant , masalah serupa pada rumus logis. Interpolasi digunakan misalnya dalam pengecekan model berbasis SAT, dalam pengaturan yang saya pikir lebih dekat dengan apa yang Anda cari (terutama mengenai keterbatasan input). Makalah ini harus menjadi titik awal yang baik.

$A$$B$

Ini disebut "The Separating Words Problem". Slide oleh Shallit cukup banyak mencakup semua yang diketahui tentang masalah (lihat slide1 dan slide2 ).