Transformasi semigrup

Dalam aljabar, transformasi semigrup (atau komposisi semigrup) adalah kumpulan fungsi dari himpunan ke dirinya sendiri yaitu tertutup di bawah komposisi fungsi. Jika itu menyertakan fungsi identitas, itu adalah monoid, disebut transformasi (atau komposisi) monoid. Ini adalah analogi grup semigrup dari grup permutasi.

Sebuah semigroup transformasi dari sebuah himpunan memiliki aksi semigroup tautologis pada himpunan tersebut. Tindakan semacam itu ditandai dengan efektif, yaitu jika dua elemen dari kelompok semigroup memiliki tindakan yang sama, maka keduanya sama.

Sebuah analogi dari Teorema Cayley menunjukkan bahwa setiap kelompok semigroup dapat direalisasikan sebagai sebuah grup semigrup transformasi dari beberapa himpunan.

Dalam teori automata, beberapa penulis menggunakan istilah transformasi semigrup untuk merujuk ke semigroup bertindak dengan setia pada satu set "keadaan" yang berbeda dari basis semigrup himpunan. Ada sebuah korespondensi antara dua gagasan.

Transformasi semigrup dan monoid

Transformasi semigrup adalah pasangan ( X , S ), di mana X adalah himpunan dan S adalah semigrup transformasi dari X . Di sini transformasi dari X hanyalah fungsi parsial dari subset X menjadi X , tidak harus dapat dibalik, dan karena itu S hanyalah seperangkat transformasi X yang tertutup di bawah komposisi fungsi. Himpunan semua fungsi parsial pada himpunan dasar tertentu, X , membentuk semigrup biasa yang disebut semigroup dari semua transformasi parsial (atau transformasi parsial semigroup pada X ), biasanya dilambangkan dengan ${\mathcal {PT}}_{X}$.

Jika S menyertakan transformasi identitas X , maka itu disebut transformasi monoid. Jelas setiap transformasi semigroup S menentukan transformasi monoid M dengan mengambil penyatuan S dengan transformasi identitas. Monoid transformasi yang elemennya dapat dibalik adalah grup permutasi.

Himpunan semua transformasi X adalah transformasi monoid yang disebut transformasi penuh monoid (atau semigrup) dari X . Ini juga disebut semigroup simetris dari X dan dilambangkan dengan T_X. Jadi, transformasi semigroup (atau monoid) hanyalah sebuah subsemigrup (atau submonoid) dari transformasi penuh monoid dari X .

Jika ( X , S ) adalah transformasi semigroup maka X dapat dibuat menjadi aksi semigrup dari S dengan evaluasi:

$s\cdot x=s(x){\text{ for }}s\in S,x\in X.$

Ini adalah aksi monoid jika S adalah transformasi monoid.

Ciri karakteristik semigroup transformasi, sebagai tindakan, adalah bahwa mereka efektif , yaitu jika

$s\cdot x=t\cdot x{\text{ untuk }}x\in X,$

lalu s = t . Sebaliknya jika semigroup S bekerja pada himpunan X sebesar T(s,x) = s • x lalu kita bisa mendefinisikan, untuk s ∈ S , sebuah transformasi T_s of X by

$T_{s}(x)=T(s,x).\,$

Peta mengirim 's' pada T_s bersifat injeksi jika dan hanya jika ( X , T ) efektif, dalam hal ini citra peta ini adalah transformasi semigrup isomorfik menjadi S .

Representasi Cayley

Dalam teori kelompok, Teorema Cayley menyatakan bahwa setiap kelompok G isomorfik ke subkelompok kelompok simetris dari G (dianggap sebagai himpunan), sehingga G adalah grup permutasi. Teorema ini secara langsung menggeneralisasi monoid: sembarang monoid M adalah transformasi monoid dari himpunan dasarnya, melalui aksi yang diberikan oleh perkalian kiri (atau kanan). Tindakan ini efektif karena jika ax = bx untuk semua x di M , maka dengan mengambil x sama dengan elemen identitas, kita memiliki a = b .

Untuk semigroup S tanpa elemen identitas (kiri atau kanan), kita mengambil X menjadi himpunan yang mendasari monoid yang sesuai dengan S untuk mewujudkan S sebagai semigrup transformasi dari X . Secara khusus, semigroup hingga apa pun dapat direpresentasikan sebagai subsemigrup dari transformasi himpunan X with |X| ≤ |S| + 1, dan jika S adalah monoid, kami memiliki ikatan yang lebih tajam |X| ≤ |S|, seperti dalam kasus grup terbatas.^:21

Dalam ilmu komputer

Dalam ilmu komputer, representasi Cayley dapat diterapkan untuk meningkatkan efisiensi asimtotik semigroup dengan menghubungkan kembali beberapa perkalian tersusun. Tindakan yang diberikan oleh perkalian kiri menghasilkan perkalian terkait kanan, dan sebaliknya untuk tindakan yang diberikan oleh perkalian kanan. Meskipun memiliki hasil yang sama untuk semua kelompok, efisiensi asimtotik akan berbeda. Dua contoh transformasi monoid berguna yang diberikan oleh tindakan perkalian kiri adalah variasi fungsional dari struktur data daftar diferensial, dan transformasi Codensity monadik (representasi Cayley dari sebuah monad, yang merupakan monoid dalam monoidal funktor kategori).

Transformasi monoid robot

Misalkan M menjadi deterministik automaton dengan spasi S dan alfabet A . Kata-kata di monoid bebas A^∗ menginduksi transformasi dari S sehingga menimbulkan morfisme monoid dari A^∗ ke monoid transformasi penuh T_S. Citra morfisme ini adalah transformasi semigroup dari M .^:78

Untuk bahasa reguler, monoid sintaktik adalah isomorfik ke transformasi monoid dari robot minimal bahasa.^:81

Lihat pula

• Semiautomaton
• Teori Krohn–Rhodes
• Semigrup invers simetris
• Himpunan Biordered
• Kelas khusus semigrup
• Gelanggang komposisi

Referensi

• Clifford, A.H.; Preston, G.B. (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys. 7. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-0272-4. Zbl 0111.03403. 
• Howie, John M. (1995). Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series. 12. Oxford: Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077. 
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.