Bahasa-bahasa yang tidak dapat (dis) kita buktikan bebas konteks

Saya mencari bahasa yang "mungkin bukan Bebas Konteks" tetapi kami tidak dapat (buktikan) menggunakan teknik standar yang dikenal.

Apakah ada survei terbaru pada subjek atau bagian masalah terbuka dari konferensi baru-baru ini?

Mungkin tidak banyak bahasa yang tidak dikenal sebagai CF, jadi jika Anda mengetahuinya, Anda juga dapat mempostingnya sebagai jawaban.

Contoh yang saya temukan adalah:

bahasa yang terkenal dari kata-kata Primitif (ada buku terbaru yang bagus tentangnya: Bahasa Bebas Konteks dan Kata-kata Primitif ) $Q = \{ w \mid w \neq u^i (|u| > 1) \}$
yang representasi Base-k dari co-domain dari polinomial (lihat pertanyaan " representasi Base-k dari co-domain dari polinomial - itu bebas konteks? " pada cstheory, yang mungkin telah diselesaikan dengan domotorp, lihat nya pracetak )

Catatan : seperti yang ditunjukkan oleh Aryeh dalam jawabannya, Anda dapat membangun seluruh kelas bahasa tersebut jika Anda "menautkan" bahasa ke dugaan yang tidak diketahui tentang (bukan) keterbatasan atau kekosongan (bukan) dari beberapa set (mis. tidak dapat dinyatakan sebagai jumlah dari dua bilangan prima ). Saya tidak begitu tertarik dengan contoh-contoh seperti itu. $L_{Goldbach} = \{ 1^{2n} \mid 2n$ $\}$

reference-request big-list context-free Marzio De Biasi
sumber

Untuk contoh kedua Anda, saya menulis makalah dari jawaban saya yang sedang ditinjau (dan umpan balik pertama positif): arxiv.org/abs/1901.03913

domotorp

Ada banyak varian dari contoh pertama yang tidak dikenal bebas konteks, saya tidak tahu apakah Anda ingin memasukkannya sebagai contoh terpisah; lihat Bab 10 dari buku yang ditautkan (Teori Kászonyi-Katsura).

domotorp

@domotorp: Saya baru saja melihatnya (saya masih membaca bab 2) ... menurut saya lebih banyak upaya teknis untuk menyerang masalah utama.

Marzio De Biasi

Jawaban:

Satu lagi yang bagus adalah komplemen dari himpunan $S$ dari kata kunci yang berdekatan (alias "faktor") dari urutan Thue-Morse ${\bf t} = 0110100110010110 \cdots$ . Untuk memberikan beberapa konteks, Jean Berstel membuktikan bahwa komplemen dari himpunan $T$ dari prefiks dari kata Thue-Morse adalah bebas konteks (dan benar-benar sesuatu yang lebih umum dari itu). Tetapi hasil yang sesuai untuk subword masih terbuka.

Jeffrey Shallit
sumber

Terima kasih banyak! Jika Anda melihatnya dinyatakan di suatu tempat (mungkin di salah satu dari banyak makalah Anda tentang urutan Thue-Morse? ;-) Anda dapat menambahkan referensi (bahkan jika dinyatakan dalam bentuk morfisme iterated).

Marzio De Biasi

$L_{TP}$ $(p,p')$ $p,p'$ $p'=p+2$ $L_{TP}$

$L_{TP}$ $L$ $0\le a_1\le a_2\le\ldots$ $\ell$ $\ell$ $L$ $L$ $R>0$ $a_{n+1}-a_n\le R$ $n$

Aryeh
sumber

Terima kasih banyak! Tapi saya tidak terlalu tertarik pada bahasa yang terkait dengan dugaan yang tidak diketahui tentang (tidak) keterbatasan beberapa set. BTW jika dugaan itu benar bahasa yang dihasilkan juga teratur :-)

Marzio De Biasi

L_{T P}

$L_{TP}$

L_{T P}

$L_{TP}$

Oh, maaf, saya tidak melihat Anda mewakili angka-angka di unary. Maka jelas. (Saya percaya bahwa membuktikan hal ini untuk representasi biner akan membutuhkan kemajuan yang cukup besar pada dugaan kembar prima.)

Emil Jeřábek mendukung Monica

Sebaliknya, Emil, bukti "standar" bahwa bilangan prima dalam biner tidak bebas konteks dengan mudah cukup untuk membuktikan bahwa setiap rangkaian bilangan tak terbatas tidak bebas konteks. Jadi, jika ada banyak bilangan prima kembar yang tak terhingga, hasilnya langsung.

Jeffrey Shallit