Kompleksitas memeriksa apakah dua kata memiliki interleaving dalam bahasa

Untuk bahasa tetap pada beberapa alfabet , mari kita pertimbangkan masalah berikut, yang saya sebut -INTERLEAVING :A L$L$$A$$L$

• Input: dua kata$u, v \in A^*$
• Output: apakah ada suatu interleaving dari dan yang di .v $u$$v$$L$

Di sini, interleaving dua kata dan adalah kata yang dapat diperoleh secara intuitif dengan mengambil huruf dan sambil menjaga urutan relatifnya. Secara formal, adalah interleaving dari dan jika kita dapat mempartisi menjadi dua disjoint, yang sama dengan dan yang lainnya sama dengan . Misalnya, "bheleloll" adalah interleaving dari "halo" dan "bel".v w u v w u v u $u$$v$$w$$u$$v$$w$$u$$v$$u$$v$

Apa kompleksitas masalah -INTERLEAVING, tergantung pada bahasa ? $L$$L$Khususnya:

• Jika teratur, maka kita dapat menyelesaikan masalah dengan algoritma dinamis pada dua string yang menunjukkannya berada di kelas NL. Apakah ini sulit untuk beberapa bahasa biasa? Namun, untuk beberapa bahasa reguler, masalahnya jelas dalam L (deterministic logspace). Apakah ada beberapa karakterisasi bahasa yang masalahnya ada di L?$L$
• Jika tidak teratur, masalahnya masih di NL ketika memiliki kompleksitas ruang deterministik polinomial online (lihat di sini untuk gagasan ini, atau pertanyaan saya sebelumnya ). Namun, ini tidak mencakup, misalnya, semua bahasa bebas konteks; namun, beberapa yang lain (misalnya, palindrom) dapat juga ditunjukkan sebagai NL (misalnya, dengan melakukan algoritma dinamis secara bersamaan dari awal dan dari akhir). Apakah ada bahasa bebas konteks yang masalah interleaving NP-hard?$L$$L$$L$

Untuk kata dan untuk dua bilangan bulat dengan kita dilambangkan dengan kata kunci dari . Selanjutnya kita membiarkan menunjukkan kata kosong. i , j 1 ≤ i ≤ j ≤ ℓ w ( i , j ) w i w i + 1 ... w j w w ( 0 , 0 $w=w_1\ldots w_{\ell}$$i,j$$1\le i\le j\le \ell$$w(i,j)$$w_iw_{i+1}\ldots w_j$$w$$w(0,0)$

• Biarkan dan menjadi dua kata yang dipertimbangkan. v = v 1 ... v $u=u_1\ldots u_m$$v=v_1\ldots v_n$
• Asumsikan bahwa bahasa bebas konteks ditentukan oleh tata bahasa bebas konteks dalam bentuk normal Chomsky.$L$

Bangun program dinamis, di mana keadaan ditentukan oleh$[i,j,r,s,A]$

• dua bilangan bulat dengan atau1 ≤ i ≤ j ≤ m i = j = $i,j$$1\le i\le j\le m$$i=j=0$
• dua bilangan bulat dengan atau1 ≤ r ≤ s ≤ n r = s = $r,s$$1\le r\le s\le n$$r=s=0$
• simbol non-terminal dalam tata bahasa bebas konteks$A$

Untuk setiap negara, putuskan apakah dalam tata bahasa bebas konteks ada beberapa derivasi yang dimulai dengan non-terminal dan yang berakhir dengan beberapa interleaving dari dua kata dan . Keputusan ini dapat dengan mudah dibuat, jika negara bagian ditangani dengan urutan yang benar (subword pendek sebelum subword panjang).u ( i , j ) w ( r , s $A$$u(i,j)$$w(r,s)$

Semua dalam semua, ini menghasilkan algoritma waktu polinomial untuk masalah -interleaving dari setiap bebas konteks bahasa .$L$$L$