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.

Definisi dan deskripsi teorema Krohn–Rhodes

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).

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. 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 grup

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.

Sejarah dan Aplikasi

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. 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).

Lihat pula

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

---

Referensi

• Barrington, David A. Mix (1992). "Some problems involving Razborov-Smolensky polynomials". Dalam Paterson, M.S. Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990. London Mathematical Society Lecture Notes Series. 169. hlm. 109–128. ISBN 978-0-521-40826-4. Zbl 0769.68041. 
• Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). "The Krohn-Rhodes Theorem and Local Divisors". Fundamenta Informaticae. 116 (1–4): 65–77. arXiv:1111.1585 . doi:10.3233/FI-2012-669. ISSN 0169-2968. 
• Pál Dömösi; Chrystopher L. Nehaniv (2005). Algebraic Theory of Automata Networks: An Introduction. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-569-9. 
• Egri-Nagy, A.; and Nehaniv, C. L. (2005), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn–Rhodes Theory", in 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, July 22–24, 2004, Revised Selected Papers, Editors: Domaratzki, M.; Okhotin, A.; Salomaa, K.; et al.; Springer Lecture Notes in Computer Science, Vol. 3317, pp. 315–316, 2005
• Egri-Nagy, Attila; Nehaniv, Chrystopher L. (Summer 2008). "Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks" (PDF). Artificial Life. 14 (3): 299–312. doi:10.1162/artl.2008.14.3.14305. ISSN 1064-5462. PMID 18489252. 
• Eilenberg, Samuel (1976). Automata, Languages and Machines. Pure and applied mathematics, Lecture notes in mathematics. New York: Academic Press. ISBN 978-0-12-234001-7.  Two chapters are written by Bret Tilson.
• Ésik, Z. (March 2000). "A proof of the Krohn–Rhodes decomposition theorem". Theoretical Computer Science. 234 (1–2): 287–300. doi:10.1016/s0304-3975(99)00315-1 . ISSN 0304-3975. 
• Hartmanis, Juris; Stearns, R. E. (1966). Algebraic structure theory of sequential machines. Prentice–Hall. ASIN B0006BNWTE. 
• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. 1. Cambridge University Press. ISBN 978-0-521-60492-5. Zbl 0489.68046. 
• Kambites, Mark (2007). "On the Krohn–Rhodes complexity of semigroups of upper triangular matrices". International Journal of Algebra and Computation. 17 (1): 187–201. CiteSeerX 10.1.1.657.4000 . doi:10.1142/S0218196707003548. ISSN 0218-1967. 
• Krohn, K. R.; and Rhodes, J. L. (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (editor: Fox, J.), (Wiley–Interscience)
• Krohn, Kenneth; Rhodes, John (April 1965). "Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines" (PDF). Transactions of the American Mathematical Society. 116: 450–464. doi:10.2307/1994127. ISSN 0002-9947. JSTOR 1994127. Diakses tanggal September 18, 2010. 
• Krohn, Kenneth; Rhodes, John L. (August 1968). Arbib, Michael A., ed. Algebraic Theory of Machines, Languages and Semigroups. Academic Press. ISBN 978-0-12-059050-6. 
• Lallement, Gerard (1971-03-01). "On the prime decomposition theorem for finite monoids". Theory of Computing Systems. 5 (1): 8–12. doi:10.1007/BF01691462. ISSN 1433-0490. 
• Meyer, A. R.; Thompson, C. (1969-06-01). "Remarks on algebraic decomposition of automata" (PDF). Theory of Computing Systems. 3 (2): 110–118. CiteSeerX 10.1.1.649.4716 . doi:10.1007/BF01746516. ISSN 1432-4350. 
• John Rhodes; Benjamin Steinberg (2008-12-17). The q-theory of finite semigroups. Springer Verlag. ISBN 978-0-387-09780-0. 
• Straubing, Howard; Thérien, Denis (2002). "Weakly iterated block products of finite monoids". Dalam Raisbaum, Sergio. Lecture Notes in Computer Science. LATIN 2002: Theoretical Informatics. 2286. Berlin: Springer. hlm. 91–104. doi:10.1007/3-540-45995-2_13. ISBN 978-3-540-43400-9. Diakses tanggal September 18, 2010. 
• Rhodes, John L. (September 3, 2009). Nehaniv, Chrystopher L., ed. Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games. Singapore: World Scientific Publishing Company. ISBN 978-981-283-696-0. 
• Tilson, Bret (September 1987). "Categories as algebra: an essential ingredient in the theory of monoids". Journal of Pure and Applied Algebra. 48 (1–2): 83–198. doi:10.1016/0022-4049(87)90108-3 . ISSN 0022-4049. 
• Wells, C. (1980). "A Krohn–Rhodes theorem for categories". Journal of Algebra. 64: 37–45. doi:10.1016/0021-8693(80)90130-1 . ISSN 0021-8693. 
• Zeiger, H. P. (April 1967). "Cascade synthesis of finite state machines". Information and Control. 10 (4): 419–433. doi:10.1016/S0019-9958(67)90228-8 . ISSN 1462-3889.  Erratum: Information and Control 11(4): 471 (1967), plus erratum.

Bacaan lebih lanjut

• 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. 

Pranala luar

• 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.