Jelaskan Sejarah dan Aplikasi dari Teori Krohn–Rhodes

Pada konferensi tahun 1962, Kenneth Krohn dan John Rhodes mengumumkan metode untuk menguraikan (deterministik) robot terbatas menjadi komponen "sederhana" yang merupakan automata terbatas itu sendiri. Kerja sama ini, yang memiliki implikasi bagi filsafat, terdiri dari tesis doktoral Krohn di Universitas Harvard, dan tesis doktoral Rhodes di MIT.<ref group="nb">Morris W. Hirsch, "Foreword to Rhodes' Applications of Automata Theory and Algebra". In J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games", (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010.</ref> Bukti yang lebih sederhana, dan generalisasi teorema ke struktur tak hingga, telah diterbitkan sejak saat itu (lihat Bab 4 dari buku Steinberg dan Rhodes '2009Theq -Theory of Finite Semigroups untuk ikhtisar).

Dalam makalah tahun 1965 oleh Krohn dan Rhodes, bukti teorema tentang dekomposisi automata hingga (atau, setara mesin sekuensial) membuat penggunaan ekstensif aljabar semigrup struktur. Bukti selanjutnya berisi penyederhanaan besar menggunakan produk karangan bunga dari semigroup transformasi hingga. Teorema menggeneralisasi dekomposisi Jordan–Hölder untuk grup hingga (di mana bilangan prima adalah grup sederhana hingga), ke semua semigroup transformasi hingga (di mana bilangan prima merupakan grup sederhana hingga ditambah semua sub-grup dari "flip-flop" (lihat di atas)). Baik grup maupun dekomposisi automata hingga yang lebih umum memerlukan perluasan himpunan keadaan umum, tetapi memungkinkan jumlah simbol input yang sama. Dalam kasus umum, ini tertanam dalam struktur yang lebih besar dengan "sistem koordinat" hierarkis.

One must be careful in understanding the notion of "prime" as Krohn and Rhodes explicitly refer to their theorem sebagai "teorema dekomposisi utama" untuk automata. Namun, komponen dalam dekomposisi bukanlah prime automata (dengan  prime  didefinisikan dengan cara yang naif); sebaliknya, gagasan  prima  lebih canggih dan aljabar: semigroup dan grup yang terkait dengan automata penyusun dekomposisi adalah prima (atau tidak dapat direduksi) dalam arti aljabar yang ketat dan alami sehubungan dengan produk karangan bunga (Eilenberg, 1976). Juga, tidak seperti teorema dekomposisi sebelumnya, dekomposisi Krohn–Rhodes biasanya memerlukan perluasan dari kumpulan negara, sehingga penutup otomatis yang diperluas (mengemulasi) yang sedang diurai. Fakta-fakta ini membuat teorema sulit dipahami, dan menantang untuk diterapkan secara praktis — hingga saat ini, ketika implementasi komputasi tersedia (Egri-Nagy & Nehaniv 2005, 2008).

H.P. Zeiger (1967) membuktikan varian penting yang disebut dekomposisi holonomi (Eilenberg 1976). Metode holonomy tampaknya relatif efisien dan telah diterapkan secara komputasi oleh A. Egri-Nagy (Egri-Nagy & Nehaniv 2005).

Meyer dan Thompson (1969) memberikan versi dekomposisi Krohn – Rhodes untuk automata hingga yang setara dengan dekomposisi yang dikembangkan sebelumnya oleh Hartmanis dan Stearns, tetapi untuk dekomposisi yang berguna, gagasan tentang  memperluas  himpunan keadaan dari robot asli sangat penting (untuk kasus automata non-permutasi).

Banyak bukti dan konstruksi sekarang ada dari dekomposisi Krohn – Rhodes (misalnya, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), dengan metode holonomy yang paling populer dan efisien secara umum (walaupun tidak di semua kasus). Karena hubungan erat antara monoid s dan kategori, versi teorema Krohn – Rhodes dapat diterapkan pada teori kategori. Pengamatan ini dan bukti dari hasil yang serupa ditawarkan oleh Wells (1980).

Teorema Krohn–Rhodes untuk semigroup/monoid adalah analog dari Teorema Jordan – Hölder untuk grup hingga (untuk semigroup/monoid daripada grup). Dengan demikian, teorema adalah hasil yang dalam dan penting dalam teori semigroup / monoid. Teorema ini juga mengejutkan banyak ahli matematika dan ilmuwan komputer karena sebelumnya secara luas diyakini bahwa aksioma semigroup/monoid terlalu lemah untuk menerima teorema struktur dengan kekuatan, dan pekerjaan sebelumnya (Hartmanis & Stearns) hanya mampu menunjukkan hasil dekomposisi yang jauh lebih kaku dan kurang umum untuk automata hingga.

Karya Egri-Nagy dan Nehaniv (2005, 2008–) terus mengotomatiskan versi holonomi dekomposisi Krohn–Rhodes yang diperpanjang dengan dekomposisi terkait untuk grup hingga (disebut koordinat Frobenius – Lagrange) menggunakan sistem aljabar komputer GAP.

Aplikasi di luar teori semigroup dan monoid sekarang layak secara komputasi. Mereka termasuk perhitungan dalam biologi dan sistem biokimia (misalnya Egri-Nagy & Nehaniv 2008), kecerdasan buatan, keadaan-hingga fisika, psikologi, dan teori permainan (lihat, misalnya, Rhodes 2009).