Penggunaan struktur aljabar dalam ilmu komputer teoretis

Saya seorang praktisi perangkat lunak dan saya sedang menulis survei tentang struktur aljabar untuk penelitian pribadi dan saya sedang mencoba untuk menghasilkan contoh bagaimana struktur ini digunakan dalam ilmu komputer teoretis (dan pada tingkat yang lebih rendah, sub-bidang ilmu komputer lainnya) .

Dalam teori grup, saya menemukan monoid sintaksis untuk bahasa formal dan jejak dan monoid sejarah untuk komputasi paralel / bersamaan.

Dari sudut pandang teori cincin, saya telah menemukan kerangka kerja semiring untuk pemrosesan grafik dan penguraian berbasis semiring.

Saya belum menemukan kegunaan struktur aljabar dari teori modul dalam penelitian saya (dan saya ingin).

Saya berasumsi bahwa ada contoh lebih lanjut dan saya hanya tidak mencari di tempat yang tepat untuk menemukannya.

Apa saja contoh lain dari struktur aljabar dari domain yang tercantum di atas yang umumnya ditemukan dalam ilmu komputer teoretis (dan sub-bidang ilmu komputer lainnya)? Atau, jurnal atau sumber daya apa yang bisa Anda rekomendasikan yang mungkin membahas topik-topik ini?

Kesan saya adalah, pada umumnya, aljabar tradisional agak terlalu spesifik untuk digunakan dalam Ilmu Komputer. Jadi Ilmuwan Komputer menggunakan struktur yang lebih lemah (dan karenanya lebih umum), atau menggeneralisasi struktur tradisional sehingga mereka dapat menyesuaikannya dengan kebutuhan mereka. Kami juga menggunakan kategori teori banyak, yang oleh ahli matematika tidak dianggap sebagai bagian dari aljabar, tetapi kami tidak melihat mengapa tidak. Kami menemukan resimentasi matematika tradisional menjadi "aljabar" dan "topologi" sebagai cabang terpisah yang tidak nyaman, bahkan tidak ada gunanya, karena aljabar umumnya orde pertama sedangkan topologi memiliki peluang untuk berurusan dengan aspek tingkat tinggi. Jadi, struktur yang digunakan dalam Ilmu Komputer memiliki aljabar dan topologi bercampur. Bahkan, saya akan mengatakan mereka cenderung lebih ke arah topologi daripada aljabar. Regimentasi penalaran menjadi "aljabar" dan "logika" adalah pembagian tak berguna dari sudut pandang kami, karena aljabar berkaitan dengan sifat-sifat persamaan sedangkan logika juga berhubungan dengan semua jenis sifat lainnya.

Kembali ke pertanyaan Anda, semigroup dan monoids digunakan cukup intens dalam teori automata. Eilenberg telah menulis koleksi 2 volume , yang kedua hampir seluruhnya merupakan aljabar. Saya diberitahu bahwa ia merencanakan empat volume tetapi usianya tidak memungkinkan proyek untuk diselesaikan. Jean-Eric Pin memiliki versi modern dari banyak konten ini dalam buku online . Automata adalah "modul monoid" (juga disebut tindakan monoid atau "tindakan"), yang berada pada tingkat yang tepat untuk Ilmu Komputer. Modul dering tradisional mungkin terlalu spesifik.

Teori kisi adalah kekuatan utama dalam pengembangan semantik denotasional. Topologi dicampur menjadi teori kisi ketika Ilmuwan Komputer, bersama-sama dengan matematikawan, mengembangkan kisi - kisi berkelanjutan dan kemudian menggeneralisasikannya ke domain . Saya akan mengatakan bahwa teori domain adalah matematika Ilmuwan Komputer sendiri, yang matematika tradisional tidak memiliki pengetahuan tentang.

Aljabar universal digunakan untuk menentukan spesifikasi aljabar tipe data . Setelah sampai di sana, Ilmuwan Komputer segera menemukan kebutuhan untuk berurusan dengan sifat-sifat yang lebih umum: persamaan kondisional (juga disebut klausa tanduk persamaan) dan sifat logika orde pertama, masih menggunakan ide yang sama dari aljabar universal. Seperti yang akan Anda perhatikan, aljabar sekarang bergabung ke dalam teori model.

Teori kategori adalah dasar untuk teori tipe. Sebagai Ilmuwan Komputer terus menciptakan struktur baru untuk menghadapi berbagai fenomena komputasi, teori kategori adalah kerangka kerja yang sangat nyaman untuk menempatkan semua ide ini. Kami juga menggunakan struktur yang diaktifkan oleh teori kategori, yang tidak memiliki keberadaan dalam matematika "tradisional", seperti kategori functor. Juga, aljabar kembali ke gambar dari sudut pandang kategoris dalam penggunaan monad dan teori efek aljabar . Coalgebras , yang merupakan dual dari algebras, juga menemukan banyak aplikasi.

Jadi, ada banyak aplikasi "aljabar" dalam Ilmu Komputer, tetapi itu bukan jenis aljabar yang ditemukan dalam buku teks aljabar tradisional.

Catatan tambahan : Ada pengertian konkret di mana teori kategori adalah aljabar. Monoid adalah struktur mendasar dalam aljabar. Ini terdiri dari operator "multiplikasi" biner yang asosiatif dan memiliki identitas. Teori kategori generalisasi ini dengan mengasosiasikan "jenis" untuk unsur-unsur monoid itu, . Anda dapat "berkembang biak" elemen hanya ketika jenis cocok: jika dan kemudian . Sebagai contoh, matriks memiliki operasi multiplikasi menjadikannya monoid. Namun, matriks (di mana dan$a : X \rightarrow Y$$a : X \rightarrow Y$$b : Y \to Z$$ab : X \to Z$$n \times n$$m \times n$$m$$n$bisa berbeda) membentuk suatu kategori. Karenanya monoids adalah kasus khusus dari kategori yang memiliki tipe tunggal. Dering adalah kasus khusus dari kategori aditif yang memiliki tipe tunggal. Modul adalah kasus khusus dari fungsi-fungsi di mana kategori sumber dan target memiliki tipe tunggal. Sebagainya. Teori kategori adalah aljabar yang diketik yang tipenya membuatnya jauh lebih dapat diterapkan daripada aljabar tradisional.

Aplikasi teori grup favorit saya sepanjang masa di TCS adalah Teorema Barrington. Anda dapat menemukan eksposisi teorema ini di blog kompleksitas , dan eksposisi Barrington di bagian komentar pada posting itu.

Grup, cincin, bidang, dan modul ada di mana-mana dalam topologi komputasi. Lihat khususnya karya Carlsson dan Zomorodian [ex: 1 ] pada homologi persisten (multidimensi), yang semuanya tentang modul bergradasi di atas domain ideal utama.

Berikut ini adalah penggunaan praktis yang sangat bagus: sebuah algoritma untuk menghitung konektivitas grafik (dari FOCS2011 ). Untuk menghitung konektivitas s-> t dari grafik, penulis memberikan algoritma yang menetapkan vektor acak dengan entri yang ditarik dari bidang hingga ke tepi keluar dari s, kemudian membuat vektor serupa untuk semua tepi dalam grafik dengan mengambil secara acak kombinasi linier, dan akhirnya menemukan konektivitas dengan menghitung pangkat vektor yang dihasilkan ditugaskan ke tepi t.

Kisi-kisi dan titik-titik tetap berada di dasar analisis dan verifikasi program. Meskipun hasil lanjut dari teori kisi jarang digunakan karena kami khawatir dengan masalah algoritmik seperti komputasi dan perkiraan titik tetap, sedangkan penelitian dalam teori kisi memiliki fokus yang berbeda (koneksi ke topologi, teori dualitas, dll). Makalah interpretasi abstrak awal menggunakan teori kisi dasar. Karya Roberto Giacobazzi dan rekan-rekannya menggunakan hasil yang lebih maju.

Dalam komputasi terdistribusi, keluarga hasil ketidakmungkinan yang terkenal diturunkan menggunakan metode topologi aljabar (Lihat karya Maurice Herlihy dan Nir Shavit).

[Sunting: Lihat Aplikasi Topologi untuk Ilmu Komputer .]

Aljabar universal adalah alat penting dalam mempelajari kompleksitas masalah kepuasan kendala.

Sebagai contoh, Dichotomy Conjecture menyatakan bahwa, secara kasar, masalah kepuasan kendala atas domain yang terbatas dapat diselesaikan dengan NP-complete atau polinomial-time. Perhatikan bahwa menurut teorema Ladner ada masalah dalam NP yang tidak dalam P dan tidak NP-lengkap, kecuali P = NP, sehingga dugaan mengatakan bahwa CSP khusus dalam memiliki dikotomi yang tidak dimiliki oleh kelas kompleksitas yang lebih besar. Ini juga akan memberikan beberapa penjelasan mengapa sebagian besar masalah yang kita temui dalam praktik dapat diklasifikasikan sebagai NP-complete atau dalam P.

Dikotomi terbukti untuk beberapa kasus khusus, misalnya CSP domain biner (Schaefer) dan CSP domain terner (Bulatov), ​​dan homomorfisme menjadi grafik yang tidak terarah (Hell dan Nesetril). Tetapi kasus umum cukup terbuka. Salah satu garis serangan utama adalah melalui aljabar universal. Sangat kasar (dan saya jelas bukan ahli dalam hal ini!) Seseorang mendefinisikan polimorfisme CSP menjadi fungsi pada domain CSP yang membuat semua kendala puas dipenuhi jika diterapkan pada masing-masing variabel. Himpunan polimorfisme dari CSP dalam beberapa hal menangkap kompleksitasnya. Sebagai contoh jika CSP A menerima semua polimorfisme dari CSP B, maka A adalah waktu polinom yang dapat direduksi menjadi B. Himpunan polimorfisme membentuk aljabar, yang strukturnya tampaknya membantu dalam menentukan algoritma / menunjukkan reduksi. Misalnya jika aljabar polimorfisme dari CSP adalah idempoten dan mengakui tipe unary, maka CSP adalah NP-complete. Idempotence adalah asumsi penyederhanaan yang bisa dibuat lebih atau kurang tanpa kehilangan keumuman. Menunjukkan bahwa CSP yang aljabarnya idempoten dan tidak mengakui tipe unary dapat diselesaikan dalam waktu polinomial akan membuktikan Dichotomy Conjecture.

Lihat survei oleh Bulatov: http://www.springerlink.com/content/a553847g6h673k05/ .

Berikut adalah dua aplikasi dari bagian TCS yang berbeda.

Semiring digunakan untuk memodelkan anotasi dalam database (terutama yang diperlukan untuk sumber), dan sering juga untuk struktur penilaian dalam kepuasan kendala yang dihargai. Dalam kedua aplikasi ini, nilai-nilai individual harus digabungkan bersama dengan cara-cara yang secara alami mengarah pada struktur semiring, dengan asosiatif dan satu operasi semiring yang mendistribusikan lebih dari yang lain. Mengenai pertanyaan Anda tentang modul, monoid tidak memiliki kebalikan dalam aplikasi ini, secara umum.

• Todd J. Green, Grigoris Karvounarakis dan Val Tannen. Semir provenance , PODS 2007. doi: 10.1145 / 1265530.1265535 ( pracetak )
• Stefano Bistarelli, Ugo Montanari dan Francesca Rossi. Kepuasan dan optimisasi kendala berbasis semiring, JACM 1997. doi: 10.1145 / 256303.256306 ( pracetak )

Cincin, modul, dan varietas aljabar digunakan dalam koreksi kesalahan dan, lebih umum, teori pengkodean.

Secara khusus, ada skema koreksi kesalahan abstrak (kode aljabar-geometri) yang menggeneralisasi kode Reed-Solomon dan kode Sisa Cina. Skema ini pada dasarnya untuk mengambil pesan Anda dari ring R dan menyandikannya dengan mengambil residu modulo banyak cita-cita berbeda dalam R. Berdasarkan asumsi tertentu tentang R, orang dapat membuktikan bahwa ini membuat kode koreksi kesalahan yang layak.

Dalam dunia decoding daftar, makalah baru-baru ini oleh Guruswami memberikan metode linear-aljabar daftar decoding dilipat kode Reed-Solomon, yang memiliki properti bagus bahwa semua pesan kandidat terletak di subruang affine dimensi rendah ruang pesan . Seseorang dapat membangun himpunan ruang subruang , set yang hampir sama besar dengan seluruh ruang tetapi memiliki persimpangan kecil dengan setiap subruang affine dimensi rendah. Jika seseorang membatasi pesan yang berasal dari subruang yang ditempatkan di dalam ruang pesan, maka skema Guruswami memberikan algoritma yang menjamin ukuran daftar yang bagus. Sejauh ini satu-satunya konstruksi eksplisit set subruang evasive diberikan oleh Dvir dan Lovett dalam makalah STOC mereka yang akan datang, Subruang Evasive Set dan membangun himpunan dengan mengambil varietas afin tertentu (dan membawa produk Cartesiannya sendiri).

Lihat Teori Ramsey - pada dasarnya generalisasi yang signifikan dari prinsip pigeonhole yang mendasari banyak automata dan teori bahasa formal (atau harus saya katakan, prinsip pigeonhole adalah kasus paling sederhana dari Teori Ramsey). Pada dasarnya dikatakan bahwa bahkan struktur yang sangat tidak teratur ternyata mengandung banyak pesanan jika cukup besar. Sebagai contoh kecil tepat di luar prinsip pigeonhole, perhatikan bahwa jika Anda mengambil enam orang, maka mereka bertiga saling kenal atau bertiga saling tidak mengenal satu sama lain.

Makalah ini terlihat seperti tempat yang bagus untuk memulai koneksi dengan ilmu komputer, tetapi Anda dapat mencari lebih banyak di google. Ini lebih bersifat kombinatorik daripada aljabar, tetapi memiliki banyak aplikasi dalam aljabar dan CS teoretis.

Dan juga lihat kisah penemunya, Frank Ramsey - benar-benar polymath luar biasa yang membuat kontribusi fundamental, bahkan revolusioner di bidang ekonomi dan filsafat serta matematika, banyak yang tidak dihargai sampai kemudian, semuanya sebelum mati pada usia 26 - hanya berpikir! Faktanya, teorema asli Ramsey, dasar Ramsey Theory, hanyalah sebuah lemma dalam sebuah makalah dengan tujuan yang lebih besar dalam logika matematika.

Menganalisis setiap masalah dengan banyak simetri difasilitasi dengan menggunakan teori grup. Contohnya adalah menemukan algoritma untuk hal-hal seperti kubus rubic. Meskipun saya tidak tahu perinciannya, saya yakin bahwa untuk membuktikan bahwa jumlah Tuhan adalah 20, diperlukan pemangkasan teori kelompok yang serius. Dalam konteks yang berbeda, pemecah praktis untuk masalah isomorfisme grafik seperti nauty menggunakan kelompok automorfisme grafik.

Aljabar (dan geometri aljabar) telah memainkan peran yang cukup besar dalam kriptografi, dengan kelompok kurva eliptik, kisi (angka-teoretis), dan tentu saja menjadi dasar untuk hampir semua karya kriptografi modern.$\mathbb{Z}_p$

Dalam pemrograman fungsional, abstraksi yang paling umum dan elegan untuk masalah sering bersifat aljabar (atau kategori-teoretik) di alam: monoids, semiring , functors, monads, F-algebras, F-coalgebras, dll. Beberapa hasil klasik (misalnya, Yoneda lemma) kebetulan memiliki konten dan utilitas komputasi.

Juga, ada teori tipe homotopy, yang menafsirkan teori tipe dalam (semacam) pengaturan topologi aljabar.

Baru-baru ini, kami mengeksplorasi (lihat makalah kami pada springerlink: Penyatuan berbasis seri formal dari pendekatan penambangan itemset sering ) upaya penyatuan untuk pola penambangan (contoh populer dari penambangan data) pendekatan dengan cara seri formal dan automata tertimbang. Alat-alat ini didasarkan pada pemetaan antara monoids dan struktur semiring.