Teori Krohn–Rhodes itu apa sih?

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.