Bahasa reguler dari sudut pandang kategori-teoretis

Saya perhatikan bahwa bahasa reguler di atas alfabet secara alami dapat dianggap sebagai masalah, dan memang sebuah kisi. Selain itu, rangkaian bersama dengan bahasa kosong mendefinisikan struktur monoid yang ketat pada kategori ini yang bersifat distributif atas gabungan (saya tidak yakin tentang ketemu). Apakah ini konstruksi yang berguna dalam teori atau praktik bahasa reguler? Adakah beberapa tambahan yang bagus untuk ditemukan, misalnya bisakah kita mendefinisikan bintang Kleene sebagai bintang?$\Sigma$$\epsilon$

Ini adalah salinan dari pertanyaan yang diajukan pada kursus Kompiler di Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311

Sudah banyak yang dilakukan menerapkan teori kategori ke bahasa dan automata biasa. Satu titik awal adalah makalah terbaru:

• Bialgebraic Review Deterministic Automata, Ekspresi Reguler dan Bahasa oleh Bart Jacobs
• Pendekatan Bialgebraic untuk Automata dan Teori Bahasa Formal oleh James Worthington.

Dalam makalah pertama dari makalah ini, struktur ekspresi reguler diperlakukan secara aljabar dan bahasa yang dihasilkan ditangani dengan batu bara. Kedua pandangan ini terintegrasi dalam pengaturan bialgebra. Bialgebra adalah pasangan aljabar-coalgebra dengan hukum distributif yang cocok yang menangkap interaksi antara istilah sintaksis (ekspresi reguler) dan perilaku komputasi (bahasa yang dihasilkan). Dasar dari makalah ini adalah aljabar dan batubara, sebagaimana diperlakukan dalam ilmu komputer di bawah payung universal aljabar dan batubara, bukan apa yang dilihat dalam matematika (kelompok, dll).

Makalah kedua menggunakan teknik yang berasal dari perawatan matematika yang lebih tradisional dari aljabar (modul dll) dan coalgebra, tapi saya khawatir saya tidak tahu detailnya.

Tidak ada yang memperlakukan bintang Kleene sebagai tambahan, sejauh yang saya tahu.

Secara umum, ada banyak pekerjaan yang menerapkan teori kategori ke automata alih-alih ekspresi reguler. Contoh karya ini meliputi:

• Bloom SL; Sabadini N.; Matriks, Mesin, dan Perilaku RFC Walters . Struktur Kategorikal Terapan, Volume 4, Nomor 4, Desember 1996, hlm. 343-360 (18)

• Michael A. Arbib, Ernest G. Manes: Pandangan seorang ahli kategori tentang automata dan sistem. Kategori Teori yang Diterapkan pada Komputasi dan Kontrol 1974: 51-64

• MA Arbib dan EG Manes. Menyesuaikan mesin, mesin perilaku negara, dan dualitas . Jurnal Aljabar Murni dan Terapan, 6: 313-344, 1975.

• MA Arbib dan EG Manes. Mesin dalam kategori . Jurnal Aljabar Murni dan Terapan, 19: 9-20, 1980.
• Buku Jirí Adámek dan Vera Trnková Automata and Algebras in Categories , sebagaimana ditunjukkan dalam komentar .

Akhirnya, ada pekerjaan pada teori iterasi, teori iterasi : logika persamaan proses iteratif oleh Stephen L. Bloom dan Zoltán Ésik, yang berfokus pada iterasi (misalnya, bintang Kleene), tetapi dari perspektif yang lebih umum, di mana bahasa biasa hanya satu hal yang termasuk dalam teori.

Sebenarnya, saya pikir yang Anda cari adalah aljabar Kleene. Lihat artikel klasik Dexter Kozen. Dia memberikan aksioma bintang Kleene. Saya menganggap ini adalah langkah pertama yang Anda minati.

Teorema kelengkapan untuk aljabar Kleene dan aljabar acara reguler. Informasi dan Komputasi, 110 (2): 366-390, Mei 1994.

Artikel itu tidak menggunakan teori kategori, tetapi ia memberikan aksioma kesetaraan dari aljabar Kleene, yang strukturnya termasuk dari bahasa-bahasa biasa. Aljabar Kleene dengan tes dapat dilihat sebagai perpanjangan dari ekspresi reguler untuk memodelkan program sederhana dengan loop dan kondisional (tetapi tanpa tugas). Ekstensi ini berguna untuk alasan tentang program-program sederhana semacam itu secara murni aljabar.

Pada teori coalgebraic aljabar Kleene dengan tes. Laporan teknikal. Universitas Cornell, Maret 2008.

Bahasa biasa membentuk aljabar Boolean dengan struktur tambahan, seperti yang Anda amati. Struktur ini telah dipelajari dari sudut pandang dualitas Batu oleh Nick Pippenger.

Bahasa Biasa dan Dualitas Batu . Nicholas Pippenger. Sistem Teori Komputasi, 1997: 121-134.

Pendekatan dualitas untuk pengenalan bahasa telah menjadi sorotan baru-baru ini dan telah diterapkan untuk memperoleh hasil baru tentang pengenalan bahasa.

Teori kualitas dan persamaan bahasa biasa. M. Gehrke, S. Grigorieff, J.-E. Pin.

Melihat dunia menggunakan kacamata teori kategori disebut kategorisasi . Terkadang menghasilkan hasil yang sangat bagus dan mengejutkan. Fisikawan telah mulai mengatakan bahwa memikirkan sebuah kelompok sebagai satu elemen gropoid membuat perbedaan yang sangat besar . Saya mulai menyadari bahwa memikirkan monoid sebagai kategori satu elemen juga menyederhanakan banyak hal. (Misalnya, tindakan monoid kemudian menjadi functor ke Set . Hal-hal semacam itu membentuk kategori tertutup dan tertutup. Jadi, mereka memiliki kalkulus lambda dan logika intuitionistic juga!)

Anda ingin mengelompokkan bahasa biasa. Saya tidak tahu apakah itu sudah dilakukan, atau dilakukan dan ternyata tidak menarik. Saya belum pernah melihat tulisan tentang hal itu. Namun, struktur aljabar bahasa reguler, Kleene algebras, cukup menarik. Ada banyak literatur tentang mereka. Tetapi, menurut saya, teori bahasa reguler dan automata terbatas menderita dari komitmen prematur terhadap keterbatasan. (Grup terbatas memang menarik dan penting, tetapi Anda tidak ingin definisi "grup" berkomitmen pada finiteness sejak awal.) Jadi, akan berguna untuk membuang finiteness dan mempelajari struktur secara lebih umum.

Pekerjaan paling menarik yang terjadi saat ini terkait dengan struktur yang disebut bimonoids lokalitas yang didefinisikan oleh Hoare. Aljabar Kleene bersamaan telah ditemukan sebagai contoh dari mereka . Bimonoid dan konkurensi lokalitas adalah arah penelitian aktif.