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 (elektronik)|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 [[semigrup dengan tiga elemen|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 ** 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 (matematika)|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 (matematika)|matriks]] di atas setiap terbatas terbatas [[bidang (matematika)|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 (matematikawan)|John Rhodes]] mengumumkan metode untuk menguraikan [[Otomat terbatas deterministik|(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 [[Massachusetts Institute of Technology|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 '2009''The''q -''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 (matematika)|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]] [[sistem aljabar komputer GAP|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]]

== Catatan ==
<references />
----


== Referensi ==

* 
* 
* 
* 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.&nbsp;315–316, 2005
* 
*  Two chapters are written by Bret Tilson.
* 
* 
* 
* 
* 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]])
* 
* 
* 
* 
* 
* 
* 
* 
* 
*  Erratum: Information and Control **11'''(4): 471 (1967), plus erratum.

## Bacaan lebih lanjut
* 
* 
* 

## 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.
* 
* An introduction to the Krohn-Rhodes Theorem (Section 5); part of the Santa Fe Institute Complexity Explorer MOOC Introduction to Renormalization, by Simon DeDeo.