$\omega$-string menghindari satu set substring

Question

Diberikan satu set string $S$ lebih $\{a,b\}$. Bagaimana menentukan apakah ada deret tak hingga yang terdiri dari${a, b}$ (yaitu, a $\omega$-string), yang tidak memiliki string apa pun $S$ sebagai substring?

Panjang total semua substring $S$ paling banyak $20000$.

Answer 1

Jika setiap $\omega$-string berisi substring dalam $S$, lalu kami katakan itu $S$tidak dapat dihindari atau set pukulan universal (UHS) . Ada algoritma klasik untuk mendeteksi apakah sekumpulan substring tidak dapat dihindari, dijelaskan misalnya dalam kombinatorik Aljabar Lothaire pada kata-kata , Bagian 1.6.

Buat grafik $G$sebagai berikut. Semua simpul adalah awalan dari string dalam$S$. Untuk setiap awalan$p$ dan simbol $\sigma$, kami terhubung $p$ ke akhiran terpanjang dari $p\sigma$muncul di grafik. Set$S$ tidak dapat dihindari jika setiap siklus masuk $G$ melewati simpul yang sesuai dengan kata di $S$.

Untuk melihat hal ini, misalkan terlebih dahulu setiap siklus masuk $G$ melewati simpul yang sesuai dengan kata di $S$. Pertimbangkan beberapa$\omega$-kata $w$. Mulai dari puncak$\epsilon$, "membaca" simbol dari $w$satu per satu. Akhirnya Anda akan mencapai siklus (sejak$G$terbatas). Dengan asumsi, siklus ini mengandung sebuah simpul$v$ di $S$, dan sebagainya $w$ mengandung $v$. Di arah lain, menelusuri file$S$-less cycle (mengganti setiap sisi dengan simbol $\sigma$ digunakan untuk membuatnya) menghasilkan secara berkala $\omega$-kata yang menghindari $S$.