Batas bawah pada ukuran CFG untuk bahasa terbatas tertentu

Pertimbangkan pertanyaan alami berikut: Dengan bahasa terbatas , apa yang menghasilkan tata bahasa L terkecil yang bebas konteks ?$L$$L$

Kita bisa membuat pertanyaan yang lebih menarik dengan menentukan urutan bahasa , misalnya L n adalah himpunan semua permutasi dari { 1 , ... , n } : intuitif, sebuah CFG untuk L n akan "kebutuhan" untuk memiliki ukuran Ω ( n ! ) . Jadi kami tertarik pada ukuran asimtotik CFG terkecil untuk bahasa.$L_n$$L_n$$\{1,\ldots,n\}$$L_n$$\Omega(n!)$

Pertanyaan serupa telah dijawab dalam beberapa makalah:

• Charikar et al. ("Perkiraan Tata Bahasa Terkecil: Kompleksitas Kolmogorov dalam Model Alami") mempertimbangkan betapa sulitnya memperkirakan ukuran CFG terkecil yang menghasilkan kata tertentu .
• Pekerjaan lebih ke arah itu adalah Arpe dan Reischuk, "Pada Kompleksitas Kompresi Berbasis Tata Bahasa Optimal".
• Peter Asveld memiliki beberapa makalah tentang subjek (misalnya "Menghasilkan Semua Permutasi oleh Tata Bahasa Bebas Konteks dalam Bentuk Normal Chomsky"). Dia mencoba untuk mengoptimalkan beberapa parameter pada tipe tata bahasa tertentu yang menghasilkan set semua permutasi, khususnya bentuk normal Chomsky dan Greibach.

Namun, sejauh ini saya belum bisa menemukan kertas mencoba untuk membuktikan terikat Pada ukuran dari pembangkit CFG L n .$\Omega(n!)$$L_n$

Apakah ada makalah yang menyediakan batas bawah untuk ukuran tata bahasa bebas konteks untuk bahasa terbatas tertentu?

Menanggapi beberapa pertanyaan di situs ini dan juga pada math.stackexchange, saya datang dengan metode sederhana yang dapat membuktikan batas bawah eksponensial pada CFG untuk bahasa tertentu, misalnya . Apakah hasil ini baru? Saya merasa sulit untuk percaya, dan saya akan senang mendapatkan petunjuk literatur.$L_n$

Seorang reviewer yang baik hati mengirimi saya kertas yang membuktikan batas bawah persis sama dengan yang saya lakukan, dengan cara yang persis sama. Kertas itu

K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Ekspresi reguler: hasil baru dan masalah terbuka , J. Autom. Lang. Sisir. 10 (2005), 407-432.

Hasilnya adalah Teorema 30 di koran.