Untuk apa kisi digunakan?

Wikipedia mengatakan :

Kisi lengkap muncul di banyak aplikasi dalam matematika dan ilmu komputer

Apakah itu hanya merujuk pada fakta bahwa aljabar Boolean standar yang digunakan dalam perhitungan adalah kisi yang lengkap? Adakah yang bisa kita dapatkan dengan bekerja pada level abstrak kisi-kisi alih-alih dengan logika Boolean secara khusus?

Pencarian google tidak menemukan banyak tentang subjek, tapi saya mungkin menggunakan kata kunci yang salah.

Lihat misalnya buku ini: Teori Lattice dengan Aplikasi, Vijay K. Garg , yang dimulai sebagai berikut:

Tatanan parsial dan teori kisi sekarang memainkan peran penting dalam banyak disiplin ilmu komputer dan teknik. Sebagai contoh, mereka memiliki aplikasi dalam komputasi terdistribusi (jam vektor, deteksi predikat global), teori konkurensi (pomset, jaring kejadian), semantik bahasa pemrograman (semantik titik tetap), dan penggalian data (analisis konsep). Mereka juga berguna dalam disiplin ilmu matematika lainnya seperti kombinatorik, teori bilangan dan teori kelompok. Dalam buku ini, saya memperkenalkan hasil penting dalam teori urutan parsial bersama dengan aplikasi mereka dalam ilmu komputer. Bias buku ini adalah pada aspek komputasi teori kisi (algoritma) dan aplikasi (terutama sistem terdistribusi).

Buku ini tampaknya tidak menyebutkan teori rekursi (teori set yang dapat dihitung), tetapi dari artikel Wikipedia tentang teori Komputasi , kita melihat:

Ketika Post mendefinisikan gagasan tentang himpunan sederhana sebagai himpunan ulang dengan himpunan tak terbatas yang tidak berisi himpunan ulang tak terbatas, ia mulai mempelajari struktur himpunan himpunan enumerable yang rekursif dengan inklusi. Kisi ini menjadi struktur yang dipelajari dengan baik. Set rekursif dapat didefinisikan dalam struktur ini dengan hasil dasar bahwa set adalah rekursif jika dan hanya jika set dan komplemennya keduanya dihitung secara rekursif. Kumpulan ulang infinite selalu merupakan himpunan rekursif tak terbatas; tetapi di sisi lain, set sederhana ada tetapi tidak memiliki superset rekursif coinfinite. Post (1944) memperkenalkan set hypersimple dan hyperhypersimple; set maksimum kemudian dibangun yang merupakan set ulang sehingga setiap re superset adalah varian terbatas dari set maksimal yang diberikan atau merupakan co-finite. Pos' Motivasi orisinal dalam studi kisi ini adalah untuk menemukan gagasan struktural sedemikian rupa sehingga setiap set yang memenuhi properti ini tidak dalam tingkat Turing dari set rekursif maupun dalam tingkat Turing dari masalah penghentian. Post tidak menemukan properti seperti itu dan solusi untuk masalahnya menerapkan metode prioritas sebagai gantinya; Harrington dan Soare (1991) akhirnya menemukan properti semacam itu.

Bacaan lebih lanjut, lihat posting blog Teori Kisi untuk Programer dan Ilmuwan Non Komputer .

Referensi yang diberikan oleh Pål GD memang sangat tepat. Jadi mari kita fokus pada masalah sampingan kecil dalam jawaban ini sebagai gantinya. Saya telah membaca beberapa kisi beberapa waktu lalu, dan mulai bertanya-tanya apakah pengertian semilattice tidak akan lebih cocok untuk aplikasi. Anda mungkin keberatan bahwa semi-kisi lengkap secara otomatis juga merupakan kisi, tetapi homomorfisme dan substruktur (yaitu sublattis dan subsemilattis) berbeda.

Saya pertama kali menemukan (semi) kisi ketika mempelajari semigroup, sebagai semigroup idempoten komutatif. Kemudian saya berpikir tentang hubungan antara struktur hierarki dan kisi-kisi, dan memperhatikan bahwa sebuh pohon secara alami juga merupakan semilattice. Kemudian saya menemukan kisi-kisi dalam konteks keamanan dan analisis program, dan selalu bagi saya sepertinya struktur semilattis adalah bagian yang sangat penting, dan kisi-kisi itu hanya diambil karena dapat diperoleh "gratis". Bahkan untuk aljabar Heyting, ada asimetri antara konjungsi dan disjungsi yang menunjukkan kepada saya bahwa model semilattis asimetris mungkin memberikan wawasan lebih di sini daripada model kisi simetris.

kasus yang sangat penting, tetapi tidak terlalu terkenal — kasus ini terkenal di kalangan ahli teori tetapi tidak begitu dikenal dalam arti diajarkan kepada mahasiswa tingkat sarjana — penggunaan kisi adalah untuk membuktikan batas bawah superpolinomial pada ukuran sirkuit monoton menghitung Clique yang mana Razborov memenangkan hadiah Nevanlinna . konstruksi asli namun sangat teknis dan kemudian konstruksi misalnya Berg / Ulfberg menyederhanakan kerangka kerja tanpa mengacu pada kisi-kisi.

jadi dalam hal ini teori kisi digunakan sebagai kerangka kerja untuk menemukan bukti asli tetapi formulasi kemudian cenderung tidak merujuk secara langsung sebagai penyederhanaan konseptual.

jadi ya kisi dapat dianggap sebagai objek matematika yang lebih eksotis [Razborov telah berbicara di tempat lain tentang gaya menerapkan matematika canggih untuk CS] yang mungkin sesuai dengan beberapa objek lain yang lebih "konkret" di CS, dalam hal ini adalah "gerbang perkiraan" yaitu gerbang boolean di sirkuit yang memberikan jawaban "kira-kira benar" dan yang kisi-kisi adalah semacam "struktur induksi" untuk mengkonversi antara sirkuit yang tepat ke sirkuit perkiraan yang tidak tepat.

Saya telah menemukan kertas gratis Set Pesanan dan Kisi Lengkap: Primer untuk Ilmu Komputer , untuk pembaca yang tertarik lainnya.

Pelabelan tepi biasa dan struktur terkait membentuk kisi distributif (lihat contoh di sini ). Ini dapat dieksploitasi untuk mencari secara efisien melalui ruang semua label tepi biasa untuk grafik yang diberikan (lihat di sini ). Sebagai aplikasi, Anda dapat menentukan apakah peta dapat digambarkan sebagai kartogram dengan penugasan area tertentu untuk wajah.

Juga, secara mengejutkan (bagi saya, setidaknya) kriptografi . Lihat itu, itu memungkinkan serangan baru dari cryptosystem yang dikenal dan memberikan harapan untuk kriptografi pasca-kuantum-komputasi.