Teori Krohn–Rhodes

Dalam matematika dan ilmu komputer, Teori Krohn-Rhodes (atau teori automata aljabar) adalah pendekatan untuk mempelajari semigroup terbatas dan automata yang berusaha untuk mendekomposisi mereka dalam istilah komponen dasar. Komponen-komponen ini sesuai dengan grup semigroup aperiodik dan grup sederhana terbatas yang digabungkan bersama dalam cara bebas umpan balik (disebut "produk karangan bunga" atau "kaskade").

Krohn dan Rhodes menemukan dekomposisi umum untuk automata terbatas. Namun, dalam melakukan penelitian mereka, penulis menemukan dan membuktikan hasil besar yang tidak terduga dalam teori semigroup hingga, yang mengungkapkan hubungan mendalam antara automata hingga dan semigrup hingga.

Semigrup S yang merupakan gambar homomorphic dari subsemigroup dari T dikatakan sebagai pembagi dari T .

Teorema Krohn–Rhodes untuk semigrup hingga menyatakan bahwa setiap semigrup hingga S adalah pembagi dari produk karangan bunga dari grup sederhana hingga, masing-masing adalah pembagi dari S , dan semigroup aperiodik terbatas (yang tidak mengandung subgrup nontrivial).^[1]

Dalam perumusan automata, Teorema Krohn–Rhodes untuk automata hingga menyatakan bahwa diberi automaton hingga A dengan status Q dan set input I , keluaran alfabet U , maka seseorang dapat memperluas status menjadi Q 'sehingga robot baru' 'A' menyematkan ke dalam rangkaian automata "sederhana" dan tidak dapat direduksi: Secara khusus, A diemulasikan oleh umpan-maju kaskade (1) automata yang semigroup transisinya adalah grup sederhana hingga dan (2) automata yang merupakan bank dari flip-flop.^{[nb 1]} Otomat baru A memiliki simbol input dan output yang sama dengan A. Di sini, baik status maupun masukan dari cascaded automata memiliki bentuk koordinat hierarki yang sangat khusus.

Selain itu, setiap grup sederhana ( prime ) atau non-grup semigroup yang tidak dapat direduksi (sub-grup dari flip-flop monoid) yang membagi semigroup transformasi A harus membagi semigroup transisi dari beberapa komponen kaskade, dan hanya bilangan prima yang harus muncul sebagai pembagi komponen adalah A' grup transisi.

Kompleksitas Krohn–Rhodes (juga disebut kompleksitas grup atau hanya kompleksitas) dari semigroup terbatas S adalah jumlah grup paling sedikit dalam produk karangan bunga dari grup hingga dan semigrup aperiodik hingga.

Semua semigroup aperiodik hingga memiliki kompleksitas 0, sedangkan grup berhingga non- trivial memiliki kompleksitas 1. Faktanya, ada setengah grup dari setiap kompleksitas bilangan bulat non-negatif. Misalnya, untuk sembarang n yang lebih besar dari 1, semigroup perkalian dari semua (n+1)×(n+1) segitiga atas matriks di atas setiap terbatas terbatas bidang memiliki kompleksitas n (Kambites, 2007).

Masalah terbuka utama dalam teori semigroup hingga adalah desidabilitas kompleksitas : apakah ada algoritme yang akan menghitung kompleksitas Krohn–Rhodes dari semigrup hingga, diberi tabel perkalian? Batas atas dan batas bawah yang lebih tepat pada kompleksitas telah diperoleh (lihat, misalnya Rhodes & Steinberg, 2009). Rhodes telah menduga bahwa masalahnya sudah pasti.^{[nb 2]}

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.^{[nb 3]} 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).^{[nb 4]} 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).^{[nb 5]}

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^{[nb 6]} 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).

• Aksi setengah grup
• Transformasi semigroup
• Teori automata aljabar
• Relasi Green

1. ^ Holcombe (1982) pp. 141–142

• Rhodes, John L. (2010). Chrystopher L. Nehaniv, ed. Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific Pub Co Inc. ISBN 978-981-283-696-0. 
• Rhodes, John; Steinberg, Benjamin (2008-12-17). The q-theory of finite semigroups. Springer Verlag. ISBN 978-0-387-09780-0. 
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 978-3-7643-3719-3. Zbl 0816.68086. 

• Prof. John L. Rhodes, University of California at Berkeley webpage
• SgpDec: Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups, developed by A. Egri-Nagy and C. L. Nehaniv. Open-source software package for the GAP computer algebra system.
• John L. Rhodes (2010). Chrystopher L. Nehaniv, ed. Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific Pub Co Inc. ISBN 978-981-283-696-0. 
• An introduction to the Krohn-Rhodes Theorem (Section 5); part of the Santa Fe Institute Complexity Explorer MOOC Introduction to Renormalization, by Simon DeDeo.