Asimptotik dari jumlah kata dalam bahasa biasa dengan panjang yang diberikan

28

Untuk bahasa biasa L., misalkan menjadi jumlah kata dalam dengan panjang . Menggunakan bentuk kanonik Jordan (diterapkan pada matriks transisi yang tidak terotomatisasi dari beberapa DFA untuk ), orang dapat menunjukkan bahwa untuk , di mana adalah polinomial yang kompleks dan adalah "nilai eigen" yang kompleks. (Untuk kecil , kami mungkin memiliki ketentuan tambahan dari bentuk , di mana adalah jika sebaliknya. Ini sesuai dengan ukuran blok Jordan setidaknyaL n L n c n ( L ) = k i = 1 P i ( n ) λ n i , P i λ i n C k [ n = k ] [ n = k ] [ n = k ] 1 n = kcn(L.)L.nL.n

cn(L.)=saya=1kPsaya(n)λsayan,
PsayaλsayanCk[n=k][n=k]1n=k dank + 10k+1 dengan nilai eigen )0

Representasi ini tampaknya menyiratkan bahwa jika tidak terbatas maka asimptotik, untuk beberapa . Namun, ini benar-benar salah: untuk bahasa lebih dari dari semua kata dengan panjang genap, tetapi . Ini menunjukkan bahwa untuk beberapa dan untuk semua , baik untuk cukup besar atau . Ini terbukti dalam Flajolet & Sedgewickc n ( L ) C n k λ n C , λ > 0 L { 0 , 1 } c 2 n ( L ) = 2 2 n c 2 n + 1 ( L ) = 0 d a { 0 , , d - 1 } c d m + a (L.cn(L.)CnkλnC,λ>0L.{0,1}c2n(L.)=22nc2n+1(L.)=0dSebuah{0,...,d-1}m c d m + a ~ C a ( d m + a ) k suatu λ d m + a acdm+Sebuah(L.)=0mcdm+SebuahCSebuah(dm+Sebuah)kSebuahλSebuahdm+Sebuah (Teorema V.3), yang mengaitkan bukti itu dengan Berstel.

Bukti yang diberikan oleh Flajolet dan Sedgewick agak teknis; sangat teknis, pada kenyataannya, mereka hanya membuat sketsa. Saya mencoba bukti yang lebih mendasar menggunakan teori Perron-Frobenius. Kita dapat menganggap grafik transisi DFA sebagai digraf. Jika digrafnya primitif, maka hasilnya mengikuti hampir secara langsung dari teorema Perron-Frobenius. Jika digraf tidak dapat direduksikan tetapi tidakrim dengan indeks , maka dengan mempertimbangkan " th power" dari DFA (setiap transisi sesuai denganr rrrr simbol), kami mendapatkan hasil yang sama. Kasus yang sulit adalah ketika digraf dapat direduksi. Kita dapat mengurangi kasus path komponen yang sangat terhubung, dan kemudian kita mendapatkan hasilnya dengan memperkirakan jumlah formulir

m1++mk=msaya=1kλsayamsaya.
(Setiap jumlah tersebut sesuai dengan cara tertentu dalam menerima kata, melalui komponen yang berbeda dengan cara tertentu.) Jumlah ini, pada gilirannya, dapat diperkirakan dengan menunjukkan dengan tepat istilah terbesar, yang sesuai dengan . Untuk setiap nilai eigen yang diulang kali, kita mendapatkan faktor tambahan . r Θ ( m r - 1 )msayalogλsayarΘ(mr-1)

Buktinya memiliki tepi yang kasar: dalam kasus yang dapat direduksi, kita perlu beralih dari istilah asimptotik ke dengan jumlah yang disebutkan di atas, dan kemudian kita perlu memperkirakan jumlahnya.Cλsayam

Buktinya oleh Flajolet dan Sedgewick mungkin lebih sederhana, tetapi kurang mendasar. Titik awalnya adalah fungsi pembangkit rasional , dan melibatkan induksi pada jumlah besaran kutub (!). Ide dasarnya adalah bahwa semua nilai eigen dari modulus maksimal adalah akar persatuan (jika dinormalisasi oleh modulus mereka), karena teorema Berstel (cukup mudah). Memilih tepat dan melihat kata-kata dengan panjang , semua nilai eigen ini menjadi nyata. Mengingat ekspansi fraksi parsial, kita dapatkan bahwa jika nilai eigen dari modulus maksimal "bertahan", maka ia menentukan asimptotik, yang merupakan bentukcn(L.)ddm+SebuahCnkλn. Jika tidak, kami menemukan fungsi pembangkit rasional baru yang sesuai hanya dengan kata-kata sepanjang ini (menggunakan produk Hadamard), dan ulangi argumennya. Kuantitas yang disebutkan di atas terus menurun, dan akhirnya kami menemukan asimptotik yang diinginkan; mungkin harus tumbuh dalam proses, untuk mencerminkan segala sesuatu yang terjadi dalam langkah-langkah induktif.d

Apakah ada bukti sederhana dan dasar untuk properti asimptotik dari ?cn(L.)

Yuval Filmus
sumber
"Properti asimptotik" manakah yang Anda maksudkan, yang tepat di atas?
Raphael
Persis properti itu.
Yuval Filmus
Untuk kasus yang dapat direduksi, apakah tidak ada batas kombinatorial sederhana (mungkin diperoleh dengan mempertimbangkan subset jalur, dan multiset jalur)?
András Salamon
Ada batasan yang mudah, tetapi Anda mungkin kehilangan faktor polinomial di sana. Ada penjumlahan dengan banyak istilah secara polinomi, dan kami dapat memperkirakannya menggunakan istilah terbesar. Namun, ini tidak akan memberi kita asimptotik yang benar, karena istilah lain membusuk dengan cepat. Mungkin perkiraan dengan integral mungkin, tapi itu sudah agak berantakan.
Yuval Filmus
1
umumnya, menemukan alternatif atau lebih banyak bukti dasar masalah bisa sangat sulit dan sebagian besar merupakan latihan teoretis ... adakah motivasi / bkg / aplikasi lebih lanjut? sarankan bermigrasi ke cstheory.
vzn

Jawaban:

3

Argumen yang telah Anda buat sketsa tampaknya sejalan dengan perlakuan Richard Stanley terhadap Metode Transfer-Matriks dalam Enumerative Combinatorics, Volume 1 (tautan: hal. 573; cetak: hal. 500).

Dia mulai dengan fungsi pembangkit, dan membukanya dengan mempertimbangkan digraf dan faktor yang diizinkan dan dilarang. Dia kemudian mengabstraksi menjadi monoids gratis, di mana dia menggunakan versi jumlah yang telah Anda berikan untuk membuktikan:

BABB(λ)=(IB(λ))-1

Setelah mengerjakan beberapa aplikasi, ia juga menutup bagian itu dengan mendiskusikan produk Hadamard sehubungan dengan polyominoes yang cembung secara horizontal.

JSS
sumber
Bisakah Anda menunjukkan teorema dalam teks Stanley yang memberikan perkiraan asimptotik?
Yuval Filmus
Saya tidak dapat menemukan referensi langsung dan eksplisit di Stanley, tetapi Flajolet dan Sedgewick mengakui pengaruhnya terhadap perlakuan mereka terhadap metode matriks transfer di bagian V.6. Secara khusus, Corollary V.1 merangkum Teorema sebelumnya (V.7, V.8) yang tampaknya mengikuti alur penalaran Anda. Mereka juga tampaknya mengikuti garis besar Stanley mulai pada ayat V.5, di mana Proposisi V.6 sesuai dengan Teorema Stanley 4.7.2 dan Corollary 4.7.3
JSS
Yang saya cari secara spesifik adalah analisis asimptotik. Rumus tepat untuk jumlah kata dengan panjang tertentu, yang diberikan oleh metode matriks transfer, adalah apa yang saya terima begitu saja.
Yuval Filmus