www.wikidata.id-id.nina.az

Transformasi semigrup Dalam aljabar transformasi semigrup atau komposisi semigrup adalah kumpulan fungsi dari himpunan k

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 sunting

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 .

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 TX. 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:

Ini adalah aksi monoid jika S adalah transformasi monoid.

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

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 Ts of X by

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

Representasi Cayley sunting

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 sunting

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 sunting

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 TS. 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 sunting

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

Referensi sunting

  1. Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. hlm. 448. ISBN 978-0-12-532111-2. 
  2. Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. hlm. 254. ISBN 978-0-8218-0272-4. 
  3. ^ Anderson, James A. (2006). Automata Theory with Modern Applications. With contributions by Tom Head. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049. 
  4. Rivas, Exequiel; Jaskelioff, Mauro (2017). "Notions of Computation as Monoids". Journal of Functional Programming. 27 (e21). arXiv:1406.4823 . doi:10.1017/S0956796817000132. 
  • 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.
wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
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 1 Ada sebuah korespondensi antara dua gagasan Daftar isi 1 Transformasi semigrup dan monoid 2 Representasi Cayley 2 1 Dalam ilmu komputer 3 Transformasi monoid robot 4 Lihat pula 5 ReferensiTransformasi semigrup dan monoid suntingTransformasi 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 P T X displaystyle mathcal PT X nbsp 2 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 TX 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 x s x for s S x X displaystyle s cdot x s x text for s in S x in X nbsp Ini adalah aksi monoid jika S adalah transformasi monoid Ciri karakteristik semigroup transformasi sebagai tindakan adalah bahwa mereka efektif yaitu jika s x t x untuk x X displaystyle s cdot x t cdot x text untuk x in X nbsp 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 Ts of X by T s x T s x displaystyle T s x T s x nbsp Peta mengirim s pada Ts bersifat injeksi jika dan hanya jika X T efektif dalam hal ini citra peta ini adalah transformasi semigrup isomorfik menjadi S Representasi Cayley suntingDalam 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 3 21 Dalam ilmu komputer sunting 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 4 Transformasi monoid robot suntingMisalkan 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 TS Citra morfisme ini adalah transformasi semigroup dari M 3 78Untuk bahasa reguler monoid sintaktik adalah isomorfik ke transformasi monoid dari robot minimal bahasa 3 81Lihat pula suntingSemiautomaton Teori Krohn Rhodes Semigrup invers simetris Himpunan Biordered Kelas khusus semigrup Gelanggang komposisiReferensi sunting Dominique Perrin Jean Eric Pin 2004 Infinite Words Automata Semigroups Logic and Games Academic Press hlm 448 ISBN 978 0 12 532111 2 Alfred Hoblitzelle Clifford G B Preston 1967 The Algebraic Theory of Semigroups Volume II American Mathematical Soc hlm 254 ISBN 978 0 8218 0272 4 a b c Anderson James A 2006 Automata Theory with Modern Applications With contributions by Tom Head Cambridge Cambridge University Press doi 10 1017 CBO9780511607202 ISBN 978 0 521 61324 8 Zbl 1127 68049 Rivas Exequiel Jaskelioff Mauro 2017 Notions of Computation as Monoids Journal of Functional Programming 27 e21 arXiv 1406 4823 nbsp doi 10 1017 S0956796817000132 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 Diperoleh dari https id wikipedia org w index php title Transformasi semigrup amp oldid 18348990