Taksonomi automata ekspresi reguler yang terkenal

Saya mencoba menyusun taksonomi algoritma untuk mengubah ekspresi reguler menjadi automata sehingga dapat melakukan beberapa tes empiris dari sifat kompleksitas mereka di domain tertentu.

Saya mengetahui beberapa nama 'besar', misalnya,

Thompson

"Algoritma Pencarian Ekspresi Reguler", Thompson, 1968

Glushkov

"Algoritma Quadratic Baru untuk Mengubah Ekspresi Reguler menjadi Automaton", Ponty, et. al, 1996

Antimirov

"Derivatif Parsial Ekspresi Reguler dan Konstruksi Automata Hingga", Antimirov, 1996

Mengikuti

"Ikuti Automata", Ilie, et. al, 2003;

"Menghitung ikuti otomat ekspresi", Champarnaud, et. al, 2002

Hromkovic

"Menerjemahkan Ekspresi Reguler ke Automata Terbatas Nondeterministic E-Free Kecil", Hromkovic, et. al, 2001

dan sifat-sifatnya yang membedakan (epsilon-free-ness, determinisme, ukuran, minimalisasi, dll) tetapi saya tahu ini bukan daftar lengkap.

Saya terutama tertarik pada algoritma yang menyajikan kompleksitas waktu yang sangat berbeda dengan yang tercantum di atas, dan / atau topologi yang sangat berbeda.

Jika Anda mengetahui orang lain, tautan ke makalah yang menjelaskan algoritme konstruksi secara terperinci akan sangat dihargai (perlu dibaca jika saya akan mengimplementasikannya!)

Sunting: Menambahkan beberapa referensi sesuai permintaan.

automata-theory fl.formal-languages regular-expressions s8soj3o289
sumber

@ Radu GRIGore Saya menambahkan beberapa referensi. Ini adalah referensi terbaik yang saya tahu untuk automata ini, tetapi mungkin ada yang lain.

s8soj3o289

Untuk Glushkov referensi saya yang biasa adalah J. Berstel dan J.-E. Pin, "Bahasa lokal dan algoritma Berry-Sethi", 1996.

Sylvain

Ngomong-ngomong, Anda dapat menemukan implementasi dari beberapa algoritma tersebut di pustaka Vaucanson C ++, untuk referensi membangun algoritma ini. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (di mana standard_of = Glushkov, thompson_of = Thompson, turunan_term_automaton = Antimirov, brzozowski = Brzozowski)

Michaël Cadilhac

@ michael-cadilhac Terima kasih atas penunjuknya. Seandainya saya tahu tentang ini sebelum saya menerapkan yang lain sendiri! Saya pasti akan melihatnya.

s8soj3o289

Jawaban:

Watson (Tech. Rep. Univ. Eindhoven 1995) telah menulis taksonomi algoritma konstruksi automata terbatas; beberapa perkembangan terbaru ditemukan di bawah ini.

Untuk NFA dengan transisi epsilon, buku teori parsing oleh Sippu / Soisalon-Soininen (Springer, 1998) berisi varian konstruksi Thompson. Ilie dan Yu (I&C 2003) dan Gulan dan Fernau (FSTTCS 2008) memberikan versi yang disempurnakan dari konstruksi klasik. Ukuran minimum yang diperlukan dari epsilon-NFA yang sesuai dengan ekspresi reguler dipelajari lebih lanjut oleh Gruber dan Gulan (LATA 2010). Struktur digraf dasar yang dihasilkan dari konstruksi Thompson dipelajari oleh Giammarresi, Ponty, Wood & Ziadi (Disc. Appl. Math 2004) dan oleh Gulan (Tech. Rep. Univ. Trier, 2010).

Mengenai NFA bebas epsilon, saya ingin menyebutkan karya sebelumnya oleh Berry & Sethi (TCS 1986) dan oleh Brüggemann-Klein (TCS 1993), tetapi itu mungkin dicakup oleh taksonomi Watson.

$n\cdot 2^{O(\log^*n)}$

Juga perhatikan: Mengenai algoritma cepat untuk pencocokan ekspresi reguler, saya mengetahui pekerjaan terbaru oleh Bille dan Thorup (ICALP 2009, SODA 2010). Mereka menggunakan konstruksi Thompson klasik (ditambah tentu saja banyak trik untuk mendapatkan kecepatan).

Hermann Gruber
sumber

ini jawaban yang bagus, terima kasih banyak. saya melihat Anda juga baru saja menerbitkan buku tentang masalah ini - mungkin saya juga bertanya apakah a. tersedia secara online dalam bentuk apa pun, dan b. apakah itu, atau apakah Anda pernah melihat kompleksitas 'kasus rata-rata' untuk domain tertentu? Saya terutama tertarik pada aplikasi untuk nlp di mana beberapa bukti anekdotal belum menunjukkan bahwa kompleksitas kasus rata-rata dari beberapa algoritma ini berbeda secara signifikan dari skenario terburuk yang dijelaskan dalam literatur cs.

s8soj3o289

Saya juga tidak begitu yakin etika apa yang menentukan dalam hal memilih jawaban. jawaban Anda jelas lebih unggul dari yang saya pilih sebelumnya.

s8soj3o289

Hanya penggoda buku ini tersedia online secara gratis.

Hermann Gruber

Mengenai kompleksitas keadaan kasus rata-rata, ada juga makalah tentang ukuran NFA rata-rata untuk bahasa yang terbatas dengan M. Holzer (TCS 2007); tetapi yang paling terkait tampaknya adalah karya Nicaud pada Glushkov automata (LATA 2009); ada juga makalah yang akan datang oleh Nicaud, Pivoteau & Razet (FSTTCS 2010) dengan judul yang menarik - saya belum bisa melihatnya.

Hermann Gruber

Gouveia, Moreira & Reis (CiE 2010) menjalankan eksperimen pada konversi RE ke NFA. Broda, Machiavelo, Moreira & Reis (DLT 2010) membandingkan jumlah keadaan posisi (Glushkov) automata dan persamaan (Antimirov) automata rata-rata. Ini mungkin juga menarik.

Hermann Gruber

Satu yang tidak dipertimbangkan dalam daftar Anda adalah Derivatif Ekspresi Reguler oleh Janusz Brzozowski, Jurnal ACM 1964, yang baru-baru ini dipertimbangkan kembali oleh Scott Owens, John Reppy, dan Aaron Turon dalam turunan ekspresi-reguler yang diperiksa ulang. Journal of Functional Programming (2009), 19: 173-190 , yang menyediakan implementasi praktis dari teknik untuk notasi yang diperluas untuk ekspresi reguler.

Dave Clarke
sumber

Antimirov adalah varian non-deterministik dari Brzozowski.

Sylvain

Nama itu terdengar akrab.

Dave Clarke

terima kasih untuk artikel yang 'diperiksa ulang', saya belum melihat itu!

s8soj3o289