Seberapa keras unshuffling string?

117

Acak dua string dibentuk dengan memotong karakter ke string baru, menjaga karakter masing-masing string dalam urutan. Misalnya, MISSISSIPPIadalah shuffle dari MISIPPdan SSISI. Biarkan saya memanggil string kuadrat jika itu adalah shuffle dari dua string yang identik. Sebagai contoh, ABCABDCDadalah kuadrat, karena itu adalah shuffle dari ABCDdan ABCD, tetapi string ABCDDCBAtidak kuadrat.

Apakah ada algoritma cepat untuk menentukan apakah suatu string adalah kuadrat, atau apakah itu NP-hard? Pendekatan pemrograman dinamis yang jelas tampaknya tidak berhasil.

Bahkan case khusus berikut nampaknya sulit: (1) string di mana setiap karakter muncul paling banyak empat enam kali, dan (2) string dengan hanya dua karakter berbeda. Seperti yang ditunjukkan Per Austrin di bawah ini, kasus khusus di mana setiap karakter muncul paling banyak empat kali dapat dikurangi menjadi 2SAT.


Pembaruan: Masalah ini memiliki formulasi lain yang dapat membuat bukti kekerasan lebih mudah.

Pertimbangkan grafik G yang simpulnya adalah bilangan bulat 1 sampai n; identifikasi setiap sisi dengan interval nyata di antara titik akhir. Kami mengatakan bahwa dua tepi G bersarang jika satu interval dengan benar berisi yang lainnya. Misalnya, tepi (1,5) dan (2,3) bersarang, tetapi (1,3) dan (5,6) tidak, dan (1,5) dan (2,8) tidak. Pencocokan dalam G tidak bersarang jika tidak ada tepi yang bersarang. Apakah ada algoritma cepat untuk menentukan apakah G memiliki pencocokan sempurna non-bersarang, atau apakah itu masalah NP-keras?

  • Memisahkan string adalah sama dengan menemukan pencocokan sempurna yang tidak bersarang di dalam gabungan kelompok klik (dengan tepi antara karakter yang sama). Secara khusus, unshuffling string biner setara dengan menemukan pencocokan sempurna non-bersarang dalam penyatuan terpisah dari dua klik. Tetapi saya bahkan tidak tahu apakah masalah ini sulit untuk grafik umum, atau mudah untuk setiap kelas grafik yang menarik.

  • Ada algoritma polinomial-waktu yang mudah untuk menemukan kecocokan non- persimpangan yang sempurna .


Pembaruan (24 Jun 2013): Masalahnya terpecahkan! Sekarang ada dua bukti independen yang mengidentifikasi string persegi adalah NP-complete.

Ada juga bukti yang lebih sederhana bahwa menemukan pasangan sempurna yang tidak bersarang adalah NP-hard, karena Shuai Cheng Li dan Ming Li pada tahun 2009. Lihat " Pada dua masalah terbuka pola 2-interval ", Theoretical Computer Science 410 (24-25) ): 2410–2423, 2009.

Jeffε
sumber
2
Bukankah urutannya hanya A000984, "jumlah nilai yang mungkin dari angka biner 2 * n bit yang setengah bit aktif dan setengah mati"?
Travis Brown
5
@ Travis, kecuali saya salah paham: Untuk n = 4, 10000111 adalah bilangan biner 2 * n bit yang setengah bit aktif dan setengah mati, tapi yang bukan persegi, seperti yang didefinisikan. Mengikuti logika itu, karena kuadrat adalah subset ketat dari himpunan yang menghasilkan A000984, nilai untuk kuadrat atas alfabet biner harus lebih rendah pada indeks yang sama melalui urutan - tidak?
Daniel Apon
1
Pengamatan: Menggunakan formalisme grafik, misalkan 2n menjadi jumlah simpul dalam G. Misalkan G ′ adalah grafik yang diperoleh dari grafik garis G dengan menambahkan tepi antara simpul yang bersesuaian dengan tepi bersarang dari G. Masalah menanyakan apakah G ′ memiliki set ukuran independen n. Ada berbagai kelas grafik di mana set independen maksimum dapat dihitung waktu polinomialnya. Jika kita mengikuti rute ini, pertanyaannya adalah: Properti bagus apa yang dimiliki G ′? (selengkapnya)
Tsuyoshi Ito
2
@ Radu: Saya tidak berpikir fraksi kuadrat ke non-kuadrat (lebih dari huruf biner) konvergen ke 1/3. Saya melakukan beberapa simulasi Monte-Carlo yang menunjukkan konvergensi yang lambat ke 1/2. Karenanya dalam batas dasarnya semua string biner dengan angka genap 0 dan 1 adalah kuadrat. Ini mengejutkan bagi saya, dan dapat dieksploitasi dalam suatu algoritma. Untuk huruf besar fraksi kuadrat tampaknya konvergen ke 0 dengan cepat.
Martin Berger
8
Karena pertanyaan ini disebutkan dalam posting blog hari ini, mari kita lihat apakah kita bisa mendapatkan minat baru dalam menyelesaikan masalah ini. Sudah setahun sejak pertanyaan ini diajukan, dan kami telah mendapatkan banyak pengguna baru sejak saat itu. Saya telah memberikan hadiah 100 rep untuk pertanyaan itu.
Alex ten Brink

Jawaban:

66

Michael Soltys dan saya telah berhasil membuktikan bahwa masalah menentukan apakah sebuah string dapat ditulis sebagai pengocokan persegi adalah NP lengkap. Ini berlaku bahkan pada alfabet terbatas dengan hanya simbol yang berbeda, meskipun bukti kami ditulis untuk alfabet dengan simbol. Pertanyaan ini masih terbuka untuk huruf yang lebih kecil, katakanlah hanya dengan simbol. Kami belum melihat masalah di bawah pembatasan bahwa setiap simbol hanya muncul kali (atau, lebih umum, jumlah yang konstan kali); jadi pertanyaan itu masih terbuka.9 2 67926

Buktinya menggunakan pengurangan dari -Partisi. Terlalu panjang untuk memposting di sini, tetapi pracetak, "Membatalkan pengacakan string adalah -hard", tersedia dari halaman web kami di:NP3NP

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

dan

http://www.cas.mcmaster.ca/~soltys/#Papers .

Makalah ini telah diterbitkan dalam Jurnal Ilmu Sistem Komputer:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Sam Buss
sumber
11
Hebat !! (Dan sangat melegakan saya, sangat tidak serius .)
Jeffε
15
Terima kasih. StackExchange adalah sumber kami untuk pertanyaan ini. Ini sumber yang bagus!
Sam Buss
9
@ SamBuss permintaan kecil: saat Anda mengutip pertanyaan Jeff, Anda hanya menyebutkan solusi Per Austrin dalam teks. Jika Anda melihat jawabannya, ada cara untuk membuat kutipan formal untuk jawaban juga (klik tombol bagikan dan tekan tautan 'cite'). Dengan cara itu, Anda dapat menghasilkan kutipan yang tepat untuk jawaban Per juga. Saya hanya menyebutkan ini sehingga orang yang memberikan kontribusi formal di situs ini juga bisa mendapatkan pengakuan formal. Terima kasih! dan selamat atas pemecahan masalah ini
Suresh Venkat
2
@ SureshVenkat. Terima kasih atas tipnya: ini berguna. Saya telah menambahkan ini ke versi online makalah ini.
Sam Buss
Masalah mengenali shuffle persegi kini telah terbukti sulit bahkan pada alfabet biner: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

Untuk kasus khusus yang Anda sebutkan ketika setiap karakter muncul paling banyak empat kali, ada pengurangan sederhana menjadi 2-SAT (kecuali saya kehilangan sesuatu ...), sebagai berikut:

Poin penting adalah bahwa untuk setiap karakter, ada (paling banyak) dua cara yang valid untuk mencocokkan kejadian karakter (kemungkinan ketiga akan bersarang). Gunakan variabel boolean untuk mewakili yang mana dari dua pencocokan yang dipilih. Sekarang tugas untuk variabel-variabel ini memberikan unfuffle yang valid dari iff string untuk setiap pasangan tepi yang bersarang, tidak keduanya dipilih. Kondisi ini dapat secara tepat dijelaskan oleh disjungsi dari variabel (mungkin dinegasikan) sesuai dengan dua karakter yang terlibat.

Per Austrin
sumber
Bagus. Ide yang sama digeneralisasikan ke string di mana setiap karakter muncul paling banyak enam kali, tetapi hasilnya adalah turunan dari 5-SAT. :-(
Jeffε
2
Jawaban ini adalah favorit untuk memenangkan hadiah.
Jeffε
jadi ini sepertinya membuktikan masalahnya adalah NPC dan mengapa kita membutuhkan bukti konferensi dan jurnal yang panjang?
T ....
@ Turbo Banyak yang terlambat, tetapi ini tidak membuktikan masalah menjadi NPC karena 2-SAT bukan NPC; itu di P.
Steven Stadnicki
Apakah pengurangan menjadi 2-SAT ini berfungsi jika ukuran Alfabet tidak terikat?
Mohammad Al-Turkistany
11

Berikut ini adalah algoritma yang mungkin memiliki peluang untuk menjadi benar meskipun tampaknya sulit untuk dibuktikan dan saya tidak akan bertaruh rumah di atasnya ...

GeGee

GGGG

>1

Setelah pilihan serakah kita membersihkan grafik lagi, dan seterusnya, dan proses berakhir ketika grafik (mudah-mudahan) pencocokan sempurna non-bersarang.

Pada awalnya saya pikir ini kira-kira seperti melihat-lihat kecil di depan dalam algoritma serakah dan tidak benar-benar bekerja, tetapi saya merasa sangat sulit untuk membuat contoh tandingan.

Per Austrin
sumber
Saya skeptis tentang fase rakus kedua, tetapi membersihkan grafik tampaknya berguna. Dalam konteks string asli, di mana grafik adalah gabungan klik-klik, dapatkah Anda mengatakan apa pun tentang struktur grafik yang dibersihkan? Apakah ini masih merupakan persatuan klik yang terpisah? (Dengan kata lain, dapatkah Anda mempartisi kemunculan setiap karakter dalam string input sehingga karakter di bagian yang berbeda tidak dapat dicocokkan?)
Jeffε
2
Untuk pertanyaan kedua, perhatikan string 'aaaa'. Membersihkannya menghilangkan tepi 1-4 dan 2-3, memberikan 4 siklus. Dua variasi langkah serakah kedua yang juga akan cukup dan bahwa saya tidak dapat menemukan contoh tandingan adalah: 1) Grafik yang dibersihkan memiliki pencocokan sempurna non-bersarang jika memiliki pencocokan sempurna (ini sepertinya tidak sebanding dengan langkah serakah) . 2) Dalam grafik pembersihan dengan pencocokan sempurna non-bersarang, setiap tepi digunakan dalam beberapa pencocokan sempurna non-bersarang (ini lebih kuat daripada langkah serakah dan item pertama sehingga seharusnya lebih mudah untuk dibantah).
Per Austrin
11

Solusi yang Sam Buss dan saya usulkan pada bulan November 2012 (menunjukkan bahwa unshuffling persegi di NP-hard dengan pengurangan dari 3-Partition) sekarang menjadi artikel yang diterbitkan dalam Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Michael Soltys
sumber
2
Ini benar-benar harus menjadi edit untuk jawaban Sam Buss sebelumnya, bukan jawaban yang terpisah. Anda dapat mengklik "sunting" untuk menyarankan sunting ke jawaban orang lain, dan sunting Anda akan ditinjau oleh pengguna situs lainnya.
DW
11

Romeo Rizzi dan Stéphane Vialette membuktikan bahwa mengenali string kuadrat adalah NP-lengkap dalam makalah 2013 mereka " Pada Mengenali Kata-kata Yang Kuadrat untuk Produk Shuffle ", dengan mengurangi dari masalah urutan biner terpanjang. Mereka menyatakan bahwa kompleksitas unshuffling string biner masih terbuka.

Bukti yang bahkan lebih sederhana bahwa menemukan pencocokan sempurna non-bersarang adalah NP-lengkap diberikan oleh Shuai Cheng Li dan Ming Li dalam makalah 2009 mereka " Pada dua masalah terbuka pola 2-interval ". Namun, mereka menggunakan terminologi yang diwarisi dari bioinformatika. Alih-alih "pencocokan non-bersarang sempurna", mereka menyebutnya "DIS-2-IP- masalah". Kesetaraan antara dua masalah dijelaskan oleh Blin, Fertin, dan Vialette :{<,}

Masalah 2-IP-DIS- memiliki formulasi langsung dalam hal pencocokan terbatas dalam grafik umum: Diberikan grafik bersama-sama dengan urutan linear dari simpul , 2-IP -DIS- masalah setara dengan menemukan kardinalitas maksimum yang cocok dengan dalam dengan properti yang untuk setiap dua sisi berbeda dan dari bukan dan juga{<,}GπG{<,}MG{u,v}{u,v}Mmin{π(u),π(v)}<min{π(u),π(v)}max{π(u),π(v)<max{π(u),π(v)}min{π(u),π(v)}<min{π(u),π(v)} dan terjadi.max{π(u),π(v)}<max{π(u),π(v)}

Pembaruan (25 Februari 2019): Bulteau dan Vialette menunjukkan bahwa masalah keputusan unhuffling string biner adalah NP-lengkap dalam makalah mereka, Mengenali kotak shuffle biner adalah NP-hard .

Mohammad Al-Turkistany
sumber
Saya tidak melihat hubungannya, dan saya tidak melihat di mana penulis mengklaim bahwa melepaskan string adalah setara dengan masalah mereka.
Suresh Venkat
2
Mereka tidak mengatakan itu setara dengan unshuffling; itu masalah yang lebih umum.
Jeffε
@ SureshVenkat Saya mengedit jawaban saya, saya harap ini lebih jelas. Pada dasarnya, apa yang mereka katakan di catatan kaki adalah bahwa setiap dua sisi dalam pencocokan ( ) tidak bersarang. M
Mohammad Al-Turkistany
Dalam versi yang sebenarnya diterbitkan, kesetaraannya dinyatakan di halaman 320. books.google.com/...
Mohammad Al-Turkistany
Diedit untuk mengubur lede .
Jeffε
9

Apakah ini membantu?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Aaron Sterling
sumber
7
Referensi yang bagus. Sulit untuk melihat bagaimana hasilnya akan berlaku untuk masalah saya, tetapi mungkin tekniknya akan membantu. Mudah untuk mengetahui apakah string X yang diberikan adalah pengocokan dua salinan dari string Y yang diberikan. Kertas terlampir membuktikan bahwa NP-sulit untuk memutuskan apakah string X yang diberikan adalah pengocokan dari sejumlah salinan dari string Y yang diberikan lainnya. Saya ingin tahu apakah string yang diberikan X adalah shuffle dari dua salinan string BEBERAPA UNKNOWN Y.
Jeffε
5

PERNAH PIKIRAN, JAWABAN INI SALAH. Gagal pada input "AABAAB": rakus mencocokkan dua A pertama satu sama lain membuat mustahil untuk mencocokkan simbol yang tersisa. Saya meninggalkannya daripada menghapusnya untuk membantu orang lain menghindari membuat kesalahan yang sama.

Tampak bagi saya bahwa selalu aman untuk mencocokkan setiap karakter berturut-turut dari kotak yang seharusnya dengan rakus dengan karakter lain yang sederajat yang berada di posisi sedini mungkin. Artinya, saya pikir algoritma waktu linier berikut ini harus bekerja:

Loop melalui setiap posisi i dalam string input, i = 0, 1, 2, ... n. Untuk setiap posisi i, periksa apakah posisi itu sudah cocok dengan beberapa posisi sebelumnya dalam string. Jika tidak, cocokkan dengan karakter yang sama yang muncul setelah posisi terakhir yang cocok dan sebaliknya sedini mungkin dalam string. Jika kecocokan tidak ditemukan untuk beberapa karakter, nyatakan bahwa inputnya bukan kotak; jika tidak, itu adalah himpunan karakter pada pasangan pertama dari setiap pertandingan.

Ini dia dengan Python:

def sqrt (S):
    cocok = []
    i, j = 0, 0
    sementara saya <len (S):
        jika j <len (cocok) dan cocok dengan [j] [1] == i:
            i + = 1
            j + = 1
            terus
        jika cocok:
            k = cocok [-1] [1] + 1
        lain:
            k = 1
        sementara k <len (S) dan S [k]! = S [i]:
            k + = 1
        jika k> = len (S):
            meningkatkan Exception ("Not a square")
        match.append ((i, k))
        i + = 1
    return "" .join (S [a] untuk a, b dalam pertandingan)

cetak sqrt ("ABCABDCD")

Di sini i adalah variabel loop utama (posisi yang kami coba cocokkan), j adalah pointer ke array pasangan yang cocok yang mempercepat pemeriksaan apakah posisi saya sudah cocok, dan k adalah indeks yang digunakan untuk mencari karakter yang cocok dengan yang ada di posisi i. Ini waktu linier karena i, j, dan k secara monoton meningkat melalui string dan setiap iterasi loop dalam meningkatkan salah satunya.

David Eppstein
sumber
4
Pernah ke sana. Selesai itu. :-)
Jeffε
5

Pembaruan: Tidak masuk akal untuk berbicara tentang kesulitan menemukan pencocokan sempurna yang non-bersarang dan non-persimpangan, ketika label dari 1 ke n, karena hanya ada satu. (Ya, saya menendang diri saya sendiri.) Namun, akan masuk akal mengingat rentang yang lebih besar pada label ... jadi saya masih melihat beberapa harapan, tetapi mungkin tidak ada gunanya. Saya pasti harus menindaklanjuti ini lagi.


Saya bisa memikirkan mengapa mungkin sulit menemukan pasangan yang tidak bersarang dan tidak bersilang. Izinkan saya menyebut pencocokan demikian sebagai pencocokan terpisah . Tidak yakin sejauh mana hal ini membantu, tetapi biar saya tetap menyajikan alasannya. (Saya harus menunjukkan bahwa argumen saya, seperti yang ada di sini, tidak lengkap, dan detail yang saya tinggalkan mungkin sangat penting. Namun, saya membayangkan bahwa itu mungkin merupakan permulaan.)

Saya akan mulai dengan masalah yang sedikit berbeda. Diberi grafik yang ujung-ujungnya diwarnai dengan warna , dan simpul diberi label dari ke , apakah ada pencocokan terpisah yang berisi tepat satu sisi dari setiap warna? Masalah ini tampaknya NP-hard (argumen untuk ini lengkap dan langsung - kecuali saya kehilangan sesuatu). Pengurangan memuntahkan grafik yang merupakan gabungan klik-klik.Gk1n

Pengurangan ini dari Disjoint Factors , masalah NP-lengkap yang diperkenalkan pada [1]. Sebuah contoh faktor disjoint diberikan oleh string di atas alfabet ukuran , dan pertanyaannya adalah apakah ada faktor disjoint , di mana faktor adalah substring yang dimulai dan diakhiri dengan huruf yang sama; dan dua faktor terpisah jika tidak tumpang tindih dalam string (perhatikan bahwa 'bersarang', khususnya, tidak diizinkan juga).kk

Biarkan saya dilambangkan dengan , elemen-elemen alfabet berukuran terkait dengan instance Disjoint Factors.a1,,akk

Diberikan contoh faktor disjoint, yaitu, katakanlah string dengan panjang , buat grafik yang memiliki simpul dengan label titik dari ke . Tambahkan tepi antara simpul dan jika posisi yang sesuai memiliki huruf yang sama (katakanlah ), dan juga warna tepi dengan warna .nn1nuvai(u,v)i

Bukti pengurangan pada dasarnya mengikuti dari definisi. Dengan faktor disjoint, kami jelas memiliki pencocokan -disjoint colorful, hanya memilih tepi seperti yang diberikan oleh faktor disjoint, dan mudah untuk melihat bahwa pencocokan yang dihasilkan berwarna-warni dan disjoint. Sebaliknya, jika ada pencocokan -disjoint colourful, maka kita memiliki faktor k disjoint, satu untuk setiap huruf, karena pencocokannya berwarna-warni (dan karenanya mengambil satu faktor per huruf), dan disjoint (sehingga faktor yang sesuai tidak akan tumpang tindih) ).kkk

Untuk menghilangkan warna dan menyempurnakannya, meskipun pada kisaran yang lebih besar , buat modifikasi berikut pada grafik yang dibuat:

Biarkan menunjukkan subset dari simpul yang memiliki label yang merupakan posisi yang terkait dengan huruf . Jika memiliki simpul , maka tambahkan simpul baru dan grafik bipartit lengkap antara dan simpul yang baru ditambahkan. Ulangi, tentu saja, untuk setiap huruf.UaaUaA(A2)Ua

Secara kasar, jika grafik ingin menghasilkan pencocokan sempurna, simpul yang baru diperkenalkan harus cocok dengan simpul , dan mereka akan menjenuhkan semua kecuali sepasang simpul, dan tepi antara simpul yang tersisa akan sesuai dengan faktor disjoint . Saya belum menghitung angka yang harus dikaitkan dengan simpul yang baru ditambahkan ... perhatikan bahwa angka tersebut harus sedemikian sehingga pencocokan yang dihasilkan terpisah. Saya hanya punya perasaan (baca: harapan) bahwa 'bisa dilakukan'!Ua

[1] Pada masalah tanpa kernel polinomial , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows dan Danny Hermelin, J. Comput. Syst. Sci.

Neeldhara
sumber
3
Saya bingung. Bukankah (1,2), (3,4), (5,6), ..., (n-1, n) SATU-SATUNYA pencocokan terpisah sempurna?
Jeffε
Setelah saya beralih ke skenario 'pencocokan sempurna', saya memodifikasi konstruksi dan menambahkan banyak simpul baru (perhatikan bahwa saya menambahkan | U_a | -2 simpul baru untuk setiap a dalam alfabet). Dengan demikian, n akan meledak sesuai - kira-kira ke 2n-2k, untuk alfabet berukuran k. Saya harap saya menjelaskan bahwa pengurangan tidak lengkap karena saya belum menentukan angka apa yang dialokasikan untuk simpul baru, tetapi saya berharap hal itu dapat diperpanjang tanpa terlalu banyak kesulitan. Namun, saya tentu harus memikirkannya sebelum saya bisa mengatakan apa-apa lagi.
Neeldhara
1
Saya berpikir bahwa inti dari komentar JeffE adalah mudah untuk menemukan pasangan yang cocok yang tidak bersarang dan tidak bersilang (atau melaporkan ketiadaannya) karena hanya ada satu kemungkinan.
Tsuyoshi Ito
2
Saya tidak berbicara tentang isi ide pembuktian Anda, tetapi saya berbicara tentang kalimat pertama dari jawaban Anda: "Saya bisa memikirkan mengapa mungkin sulit untuk menemukan pasangan yang sempurna yang tidak bersarang dan tidak bersilang." Tugas ini mudah karena JeffE menulis.
Tsuyoshi Ito
2
Tanpa kendala pewarnaan yang dipaksakan oleh masalah faktor disjoint (paling banyak satu sisi dari masing-masing warna), menemukan kecocokan disjoint maksimal juga mudah.
Jeffε
1

Pendekatan ini tidak berhasil: menguraikan kotak yang dikocok dengan mengeluarkan dua huruf yang cocok tidak menghasilkan kotak yang dikocok ... Lihat komentar Radu di bawah ini.


Sebuah proposal menggunakan Rentang Penggabungan Tata bahasa (RCGs, lihat http://hal.inria.fr/inria-00073347/en/ ): Saya 'm berada di bawah kesan bahwa RCG sederhana berikut mengakui Anda 'dikocok kotak' bahasa lebih terbatas alfabet , DIedit setelah komentar pertama Radu: di mana rentang lebih dan menunjukkan kosong tali.Σ

S(XY)A(X,Y)(1)A(aX1,aX2Y1Y2)A(X1,Y1)A(X2,Y2)(2)A(ε,ε)ε(3)
aΣε

Tata bahasa memeriksa dengan predikat kedua yang cocok dengan huruf dari kemunculan kata pertama dengan huruf yang sama dalam kemunculan kata kedua. Kemudian menebak bagaimana mencocokkan sisa dari huruf kata pertama yang tersisa, yaitu dengan substring dari sisanya, yaitu . itu semuanya sebelum milik instance kata pertama; kami menyebutnya dan kami rasa itu cocok dengan beberapa suffix mulai dari . Perhatikan bahwa dan mungkin berisi huruf-huruf dari kedua contoh kata, tetapi dan hanya berisi huruf-huruf dari instance pertama.X1Y1Y1X2Y2Y1Y2X1X2

Sebagai contoh, berikut adalah kemungkinan turunan dari string Anda : abcabdcd

S(abcabdcd)A(abc,abdcd)(by 1,X=abc,Y=abdcd)A(bc,bdcd)A(ε,ε)(by 2,X1=bc,Y1=bdcd,X2=Y2=ε)A(c,c)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(ε,ε)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(d,d)A(ε,ε)(by 3)A(d,d)A(ε,ε)(by 3)A(ε,ε)A(ε,ε)A(ε,ε)(by 2)3εi.e. success

Untuk , 0011

S(0011)A(0,011)A(ε,ε)A(1,1)A(1,1)ε

Sekarang, Boullier menunjukkan di koran terkait sebelumnya bahwa ada pemrograman polinomial waktu algoritma dinamis untuk RCGs, yang menjawab pertanyaan Anda jika tata bahasa di atas adalah benar. Idenya adalah bahwa, meskipun saya disajikan di atas instanciations variabel , , dll sebagai string, mereka benar-benar interval di dalam string input, yang dapat ditabulasi dengan benar.XY

Sylvain
sumber
Apakah ada derivasi yang membawa S (0011) ke ? (Seharusnya ada satu.)ϵ
Radu GRIGore
Saya kira tidak.
Serge Gaspers
Juga, A (10,011010) -> A (0,101) A (0,0) -> , tapi saya percaya 10011010 bukan kotak. ϵ
Radu GRIGore
Terima kasih atas pengembaliannya; Saya telah sedikit mengubah tata bahasa, dan bahkan memiliki intuisi kecil yang mungkin bisa berfungsi.
Sylvain
3
Sama-sama. Berikut ini lebih lanjut, untuk tata bahasa yang diperbarui :) A (00,000110) -> A (0,011) A (0,0) -> , tetapi 00000110 bukan persegi. Juga, tampaknya tidak ada derivasi untuk 100110101010, yang merupakan kuadrat. ϵ
Radu GRIGore
1

Pembaruan: Seperti yang ditunjukkan Tsuyoshi Ito dalam komentar, algoritma ini memiliki waktu berjalan yang eksponensial.

Pos asli:

Inilah cara saya memprogram ini di Dunia Nyata.

Kita diberi string S = (S [1], ..., S [n]). Untuk setiap awalan S_r = (S [1], ..., S [r]), ada satu set {(T_i, U_i)} dari pasangan string, sehingga S_r adalah pengocokan (T_i, U_i), dan T_i adalah awalan dari U_i (yaitu U_i 'dimulai dengan' T_i). S_r itu sendiri adalah kotak jika dan hanya jika set ini berisi pasangan (T_i, U_i) dengan T_i = U_i.

Sekarang, kita tidak perlu membuat semua pasangan ini; kita hanya perlu membuat akhiran V_i dari setiap string yang U_i peroleh dengan menghapus salinan T_i-nya. Ini akan menghilangkan jumlah duplikat yang tidak relevan (mungkin eksponensial). Sekarang S_r adalah kotak jika dan hanya jika rangkaian sufiks ini berisi string kosong. Jadi algoritme menjadi:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Misalnya, jika S adalah AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Kami dapat membuang semua sufiks yang lebih dari setengah sepanjang string input, jadi ini menyederhanakan untuk:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

Saya telah memprogram ini dalam C ++, dan berfungsi pada semua contoh yang diberikan di sini. Saya dapat memposting kode, jika ada yang tertarik. Pertanyaannya adalah: dapatkah ukuran SuffixSet tumbuh lebih cepat daripada secara polinomi?

TonyK
sumber
3
Saya mencoba ini juga, tetapi percobaan menunjukkan bahwa ukuran SuffixSet tampaknya tumbuh secara eksponensial dalam n jika string asli adalah (AB) ^ n.
Tsuyoshi Ito
1

EDIT: Ini adalah jawaban yang salah.


Sylvain menyarankan RCG yang sayangnya tidak sesuai untuk "kotak acak" ini. Namun, saya pikir ada satu (EDIT: bukan RCG, lihat komentar Kurt di bawah!) , Yang terlihat sebagai berikut:

S(Y)A(ϵ,Y)(1)A(X,ZY)A(XZ,Y)(2)A(aX,aY)A(X,Y) for every aΣ(3)A(ϵ,ϵ)ϵ(4)

Penjelasan: ingat bahwa kita harus mencocokkan simbol yang dapat muncul di mana saja di string, tetapi begitu kita telah mencocokkan dan , kita hanya bisa mencocokkan dan jika menyiratkan ( artinya diutamakan linear). Idenya adalah bahwa kita membagi string untuk membandingkan prefix dari setengahnya. Jika permulaan dari dua substring cocok, kita dapat mengurangi masalah ke string yang tersisa . Jika tidak, kita dapat memindahkan beberapa bagian sisi kanan ke sisi kiriaabbabab(1,2)(3)(2)dan lihat apakah ada kecocokan di posisi selanjutnya. Yang penting adalah ini hanya diperbolehkan dalam satu arah!

Berikut ini derivasi untuk (contoh tandingan terhadap RCG Sylvain):100110101010

S(100110101010)A(ϵ,100110101010)(1)A(1001,10101010)(2)A(01,101010)(3)A(011,01010)(2)A(1,010)(3)A(10,10)(2)A(ϵ,ϵ)(3)ϵ(4)

Saya belum menemukan bukti formal bahwa tata bahasa ini benar-benar menangkap "kotak acak" tetapi seharusnya tidak terlalu sulit. Sylvain telah menyebutkan bahwa masalah keputusan untuk RCG adalah polinomial.

DaniCL
sumber
Saya tidak melihat bagaimana ini dapat diterapkan dalam waktu polinomial: Jika Anda mulai dari 000102030 maka Anda dapat mencapai untuk x sama dengan salah satu dari string 123, 01230, 01203, 0012030, 01023, 0010230, 0010203, 000102030. (Ya, saya melihat dokumen yang ditautkan oleh Sylvain, tapi kelihatannya semua orang Prancis bagi saya.)2 3A(x,ϵ)23
Radu GRIGore
5
@DaniCL, Setelah dipikir-pikir ... Apakah parameter dalam RHS dari aturan produksi harus rentang input yang berdekatan? Saya tidak melihat bahwa secara eksplisit dinyatakan dalam definisi di makalah Boullier, tapi itu tampaknya bagaimana itu digunakan. Dalam analisis waktu berjalan dari algoritma parsing, dikatakan bahwa jumlah argumen yang mungkin untuk klausa adalah O (n ^ 2h) di mana h adalah maksimum dari klausa dan n adalah panjang input. Dalam tata bahasa Anda, XZ secara umum tidak akan bersebelahan dengan input asli.
Kurt
3
@ Kurt, saya pikir Anda menemukan kekurangannya. Dalam makalah lain ("Bilangan Cina, MIX, Scrambling, dan Range Concatenation Grammars"), Boullier secara eksplisit menyatakan: "Tentu saja, hanya rentang berurutan yang dapat digabungkan menjadi rentang baru. Dalam PRCG, terminal, variabel, dan argumen dalam klausa apa pun adalah seharusnya terikat pada rentang dengan mekanisme substitusi. " Ini mungkin berarti bahwa tata bahasa saya bukan RCG yang valid, bahwa keraguan Radu masuk akal, dan bahwa pendekatan ini juga tidak berhasil.
DaniCL
2
@Kurt benar. Tanpa batasan persentuhan, saya cukup yakin saya dapat membuat seperangkat aturan produksi yang mengenali bahasa NP-lengkap UNARY 3PARTISI. Setiap set bilangan bulat non-negatif dapat dikodekan secara unary oleh string dalam bahasa (1 * 0) ^ *. UNARY 3PARTITION adalah himpunan semua string yang set kodekannya dapat dipartisi menjadi himpunan bagian 3 elemen, semua dengan jumlah yang sama. (Lihat en.wikipedia.org/wiki/3-partition_problem .)
Jeffε
1
Tata bahasa untuk UNARY 3PARTISI: S (X0Y0Z) -> A (e, X0, Y0, Z); A (W, 1X, Y, Z), A (W, X, 1Y, Z), A (W, X, Y, 1Z) -> A (W1, X, Y, Z); A (W, 0X, 0Y, 0Z) -> B (W, XYZ); B (W, e) -> e; B (W, X0Y0Z) -> C (W, W, X0, Y0, Z); C (W, 1V, 1X, Y, Z), C (W, 1V, X, 1Y, Z), C (W, 1V, X, Y, 1Z) -> C (W, V, X, Y, Z); C (W, e, X, Y, Z) -> B (W, XYZ)
Radu GRIGore