Bahasa dikenali oleh DFA ukuran polinomial

Untuk alfabet yang terbatas tetap $\Sigma$ , bahasa formal $L$ lebih $\Sigma$ adalah biasa jika ada sebuah robot yang terbatas deterministik (DFA) lebih $\Sigma$ yang menerima persis $L$ .

Saya tertarik pada bahasa yang "hampir" teratur dalam arti bahwa mereka dapat dikenali oleh automata keluarga ukuran yang hanya tumbuh secara polinomi dengan kata panjang.

Secara formal, saya katakan bahwa bahasa formal adalah diakui oleh DFA keluarga ( A n ) jika untuk setiap kata w ∈ Σ * , membiarkan n = | w | , W adalah L IFF A n menerima w (tidak peduli jika yang lain A i menerimanya atau tidak), dan biarkan aku menentukan p-biasa bahasa sebagai bahasa yang diakui oleh PTIME-dihitung keluarga DFA ( A n$L$ $(A_n)$$w \in \Sigma^*$$n = |w|$$w$$L$$A_n$$w$$A_i$$(A_n)$dari ukuran polinom, yaitu, ada polinom sehingga | A n | ≤ P ( n ) untuk semua n . (Nama ini, "p-regular", adalah sesuatu yang saya buat, pertanyaan saya adalah untuk mengetahui apakah nama lain sudah ada untuk ini. Perhatikan bahwa ini tidak sama dengan bahasa p-regular dalam arti permutasi automata .)$P$$|A_n| \leq P(n)$$n$

Kelas bahasa p-reguler ini termasuk bahasa biasa saja (ambil saja untuk semua n , di mana A adalah beberapa DFA yang mengenali bahasa biasa); tetapi ini adalah superset ketat: misalnya, diketahui bahwa { a n b n ∣ n ∈ N } bebas konteks tapi tidak reguler, tetapi p-reguler ( A n hanya harus menghitung n kemunculan a dan n kemunculan b ). Namun, karena saya memerlukan automata menjadi DFA berukuran polinomial$A_n = A$$n$$A$$\{a^n b^n \mid n \in \mathbb{N}\}$$A_n$$n$$a$$n$$b$, beberapa bahasa formal (sebenarnya beberapa bahasa bebas konteks) tidak p-reguler: misalnya, bahasa palindrom tidak p-reguler, karena, secara intuitif, ketika Anda telah membaca bagian pertama kata, Anda harus memiliki sebanyak mungkin negara yang berbeda karena ada kata-kata yang mungkin, karena Anda harus mencocokkan dengan tepat babak pertama ini dengan yang kedua.

Jadi kelas bahasa p-reguler adalah superset ketat dari bahasa-bahasa biasa yang tidak ada bandingannya dengan bahasa bebas konteks. Bahkan, tampaknya Anda bahkan bisa mendapatkan hierarki bahasa dengan membedakan bahasa p-reguler berdasarkan tingkat terkecil dari polinomial mana mereka adalah P- regular. Tidak terlalu sulit untuk membangun contoh untuk menunjukkan bahwa hierarki ini ketat; meskipun saya belum mengerti dengan baik interaksi antara ini, dan definisi alternatif dari hierarki yang juga akan membatasi kompleksitas komputasi A n .$P$$P$$A_n$

Pertanyaan saya adalah: apakah kelas ini yang saya sebut p-regular, dan hierarki terkait, telah dipelajari sebelumnya? Jika ya, di mana dan dengan nama apa?

(Tautan yang mungkin adalah dengan bidang atau streaming, atau algoritma online. Dalam terminologi algoritma Streaming untuk masalah pengenalan bahasa , saya tertarik pada kelas (atau hierarki) bahasa yang dapat memiliki algoritma deterministik, pengenalan sekali jalan, menggunakan jumlah polinomial negara (jadi ukuran memori logaritmik), tetapi saya tidak menemukan definisi kelas ini dalam makalah ini atau makalah terkait. Namun, perhatikan, dalam ungkapan saya tentang masalah, panjang kata diketahui di muka , yang kurang alami dalam konteks streaming: dalam streaming Anda bisa melihat ini sebagai otomat tak terbatas, simbol "akhir kata" khusus, dan batasan bahwa jumlah negara yang dapat dijangkau setelah membaca karakter adalah polinomial dalam $n$$n$. Saya pikir perbedaan ini membuat perbedaan, contoh yang mungkin: bahasa kata-kata biner yang nilainya dapat dibagi dengan panjangnya, yang mudah untuk panjang tetap tetapi (saya duga) tidak dapat diwakili oleh robot tak terbatas dalam pengertian sebelumnya karena tidak ada identifikasi dapat dibuat jika panjangnya tidak diketahui sebelumnya.)

(Motivasi untuk kelas p-reguler ini adalah bahwa beberapa masalah, seperti kemungkinan keanggotaan bahasa untuk kata-kata probabilistik, tampaknya menjadi PTIME tidak hanya ketika bahasa itu teratur, tetapi juga ketika itu adalah p-reguler, dan saya sedang mencoba untuk mengkarakterisasi secara tepat dalam keadaan apa masalah-masalah itu dapat dituntaskan.)

pertanyaannya sepertinya tidak banyak dipelajari (satu kemungkinan mencoba menemukan hubungan dengan kelas kompleksitas "terdekat", katakan P / poly, dll); meskipun di sini setidaknya ada satu referensi yang menyentuh:

• Operasi bahasa dengan ekspresi reguler ukuran polinomial Gruber / Holzer

  Karya ini berkaitan dengan pertanyaan mengenai sejauh mana operasi pengawetan keteraturan memengaruhi kompleksitas deskriptif ekspresi reguler. Beberapa operasi bahasa diidentifikasi yang layak untuk ekspresi reguler dalam arti bahwa hasil operasi dapat direpresentasikan sebagai ekspresi reguler polinomial ukuran dalam operan. Kami membuktikan bahwa mengambil quotient bahasa, khususnya awalan dan penutup sufiks, dari himpunan biasa dapat paling banyak menimbulkan ledakan kuadrat pada ukuran ekspresi yang diperlukan. Operasi shift melingkar hanya dapat menyebabkan peningkatan ukuran kubik dan setidaknya mengasapi kuadrat dapat diperlukan dalam kasus terburuk.

seperti yang disarankan SA mungkin ada cara lain yang lebih alami untuk mempelajari sesuatu seperti pertanyaan yang diajukan. di sini adalah cara lain yang agak mirip untuk mempelajari pertumbuhan bahasa reguler berdasarkan jumlah kata-kata ukuran yang memang memiliki beberapa hubungan yang longgar dengan pertanyaan misalnya$n$

• Menemukan tingkat pertumbuhan bahasa reguler atau bebas konteks dalam waktu polinomial (Gawrychowski, Krieger, Rampersad, Shallit)

  Diberi bahasa L bebas konteks, kita dapat menguji apakah itu polinomial atau pertumbuhan eksponensial dalam waktu polinomial. Selain itu, jika pertumbuhan polinomnya, kita juga dapat menemukan urutan polinomial ini dengan tepat dalam waktu polinomial.