Masalah kata untuk grup

Halaman ini berisi artikel tentang masalah algoritmik dalam teori grup. Untuk penggunaan terkait, lihat masalah kata.

Dalam matematika, terutama di bidang aljabar abstrak dikenal sebagai teori grup kombinatorial, masalah kata untuk grup yang dihasilkan secara hingga G adalah masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama. Lebih tepatnya, jika A adalah himpunan terbatas generator untuk G maka kata uji coba adalah masalah keanggotaan untuk bahasa formal dari semua kata dalam A dan sekumpulan formal invers yang memetakan identitas di bawah peta alami dari monoid bebas. Jika B adalah himpunan penghasil hingga lain untuk G , maka masalah kata di himpunan pembangkit B setara dengan masalah kata di atas himpunan pembangkit A . Jadi seseorang dapat berbicara dengan jelas tentang desidabilitas dari masalah kata untuk grup G yang dihasilkan secara tak terbatas.

Masalah kata seragam yang terkait tetapi berbeda untuk kelas K dari grup yang disajikan secara rekursif adalah masalah algoritmik dalam memutuskan, diberikan sebagai masukan presentasi P untuk grup G di kelas K dan dua kata di generator G , baik kata mewakili elemen yang sama dari G . Beberapa penulis mensyaratkan kelas K untuk didefinisikan oleh sekumpulan presentasi secara rekursif dapat dihitung.

Sejarah

Sepanjang sejarah subjek, komputasi dalam kelompok telah dilakukan menggunakan berbagai bentuk normal. Ini biasanya secara implisit memecahkan masalah kata untuk kelompok yang bersangkutan. Pada tahun 1911 Max Dehn mengusulkan bahwa masalah kata adalah bidang studi penting dalam dirinya sendiri, bersama dengan masalah konjugasi dan masalah isomorfisme grup. Pada tahun 1912 ia memberikan algoritme yang memecahkan masalah kata dan konjugasi untuk grup fundamental dari manifold dua dimensi yang dapat diorientasikan tertutup dari genus yang lebih besar dari atau sama dengan 2. Penulis selanjutnya telah memperluas Algoritma Dehn dan menerapkannya ke berbagai teori grup masalah keputusan.

Hal ini ditunjukkan oleh Pyotr Novikov pada tahun 1955 bahwa terdapat kelompok G yang disajikan secara terbatas sehingga kata masalah untuk G adalah tidak dapat diputuskan. Segera diikuti bahwa masalah kata seragam juga tidak dapat diputuskan. Bukti berbeda diperoleh oleh William Boone pada tahun 1958.

Kata masalah adalah salah satu contoh pertama dari masalah yang tidak dapat diselesaikan yang tidak ditemukan di logika matematika atau teori algoritma, tetapi di salah satu cabang utama matematika klasik, aljabar. Sebagai hasil dari ketidakmampuannya, beberapa masalah lain dalam teori gruo kombinatorial telah terbukti tidak dapat diselesaikan juga.

Penting untuk disadari bahwa kata problem sebenarnya dapat dipecahkan untuk banyak grup G . Misalnya, grup polisiklik memiliki masalah kata yang dapat dipecahkan karena bentuk normal dari kata arbitrer dalam presentasi polisiklik mudah dihitung; algoritma lain untuk grup mungkin, dalam keadaan yang sesuai, juga memecahkan masalah kata, lihat Algoritma Todd-Coxeter dan Algoritma penyelesaian Knuth–Bendix. Di sisi lain, fakta bahwa algoritme tertentu tidak menyelesaikan masalah kata untuk grup tertentu tidak menunjukkan bahwa grup tersebut memiliki masalah kata yang tidak dapat diselesaikan. Misalnya algoritma Dehn tidak memecahkan masalah kata untuk grup fundamental dari torus. Bagaimanapun kelompok ini adalah produk langsung dari dua grup siklik tak hingga dan memiliki masalah kata yang dapat dipecahkan.

Penjelasan yang lebih konkrit

Dalam istilah yang lebih konkret, soal kata seragam dapat diekspresikan sebagai pertanyaan menulis ulang, untuk pita literal. Untuk presentasi P dari grup G , P akan menentukan sejumlah generator

x, y, z, ...

untuk G . Kita perlu memperkenalkan satu huruf untuk x dan huruf lainnya (untuk kenyamanan) untuk elemen grup yang diwakili oleh x⁻¹. Sebut huruf-huruf ini (dua kali lebih banyak dari generator) alfabet $\Sigma$ untuk masalah kita. Kemudian setiap elemen di G diwakili dalam beberapa cara oleh produk

abc ... pqr

simbol dari $\Sigma$, dari beberapa panjang, dikalikan dengan G . String dengan panjang 0 ( string null) adalah singkatan dari elemen identitas e dari G . Inti dari keseluruhan masalah adalah untuk dapat mengenali semua cara e dapat direpresentasikan, dengan beberapa hubungan.

Efek dari relasi dalam G adalah membuat berbagai string tersebut mewakili elemen yang sama dari G . Sebenarnya relasi menyediakan daftar string yang bisa dikenalkan di tempat yang kita inginkan, atau dibatalkan setiap kali kita melihatnya, tanpa mengubah 'nilai', yaitu elemen grup yang merupakan hasil perkalian.

Untuk contoh sederhana, ambil presentasi {a | a³}. Menulis A untuk kebalikan dari a , kami memiliki kemungkinan string yang menggabungkan sejumlah simbol a dan A . Kapanpun kita melihat aaa , atau aA atau Aa kita mungkin mencoretnya. Kami juga harus ingat untuk mencoret AAA ; Ini mengatakan bahwa karena kubus a adalah elemen identitas G , begitu pula kubus dari kebalikan dari a . Dalam kondisi seperti ini kata soal menjadi mudah. Pertama kurangi string menjadi string kosong, a , aa , A atau AA . Kemudian perhatikan bahwa kami juga dapat mengalikan dengan aaa , sehingga kami dapat mengonversi A menjadi aa dan mengubah AA menjadi a . Hasilnya adalah bahwa masalah kata, di sini untuk grup siklik dari orde tiga, dapat dipecahkan.

Namun, ini bukan kasus yang khas. Sebagai contoh, kami memiliki bentuk kanonik tersedia yang mengurangi string apa pun menjadi satu string maksimal tiga, dengan mengurangi panjangnya secara monoton. Secara umum, tidak benar bahwa seseorang bisa mendapatkan bentuk kanonik untuk elemen, dengan pembatalan bertahap. Seseorang mungkin harus menggunakan relasi untuk memperluas pita berkali-kali lipat, untuk akhirnya menemukan pembatalan yang menurunkan panjangnya.

Hasilnya adalah, dalam kasus terburuk, bahwa hubungan antara string yang mengatakan mereka sama di G adalah Masalah yang tidak dapat diputuskan .

Contoh

Grup berikut memiliki masalah kata yang bisa dipecahkan:

• Grup otomatis, termasuk:
  • Grup hingga
  • Grup melengkung negatif (alias hiperbolik)
  • Grup Euklides
  • Grup Coxeter
  • Grup kepang
  • Grup hingga geometris
• Dibuat tanpa batas grup gratis
• Dibuat tanpa batas grup abelian bebas
• Grup poliklik
• Dibuat secara rekursif grup obsolut, termasuk:
  • Grup sederhana yang disajikan dengan sempurna.
• Grup residual finite yang ditampilkan secara terbatas
• Satu grup relator (ini adalah teorema Magnus), termasuk:
  • Gruo dasar manifold dua dimensi berorientasi tertutup.
• Kelompok yang dapat diserang
• Grup autostackable

Contoh dengan masalah kata yang tidak terpecahkan juga diketahui:

• Diberikan himpunan yang dapat dihitung secara rekursif A dari bilangan bulat positif yang memiliki masalah keanggotaan yang tidak terpecahkan, ⟨a,b,c,d | aⁿbaⁿ = cⁿdcⁿ : n ∈ A⟩ adalah grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif yang masalah katanya tidak terpecahkan
• Setiap grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif dan masalah kata yang tidak terpecahkan adalah subkelompok dari grup yang disajikan secara terbatas dengan masalah kata yang tidak dapat larut
• Jumlah relator dalam kelompok yang disajikan secara terbatas dengan masalah kata yang tidak terpecahkan mungkin serendah 14 kali atau bahkan 12 kali.
• Contoh eksplisit dari presentasi singkat yang masuk akal dengan masalah kata yang tidak terpecahkan diberikan dalam Collins 1986:

${\begin{array}{lllll}\langle &a,b,c,d,e,p,q,r,t,k&|&&\\&p^{10}a=ap,&pacqr=rpcaq,&ra=ar,&\\&p^{10}b=bp,&p^{2}adq^{2}r=rp^{2}daq^{2},&rb=br,&\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},&rc=cr,&\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},&rd=dr,&\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},&re=er,&\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},&pt=tp,&\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},&qt=tq,&\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},&&\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},&&\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}&&\rangle \end{array}}$

Solusi parsial dari masalah kata

Masalah kata untuk grup yang disajikan secara rekursif dapat diselesaikan sebagian dalam pengertian berikut:

Diberikan presentasi rekursif P = ⟨X|R⟩ untuk grup G , tentukan:

$S=\{\langle u,v\rangle :u{\text{ dan }}v{\text{ adalah kata-kata }}X{\text{ dan }}u=v{\text{ pada }}G\ \}$

lalu ada fungsi rekursif parsial f_P yaitu:

$f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{jika}}\ \langle u,v\rangle \in S\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}$

Lebih informal, ada algoritma yang berhenti jika u = v , tapi tidak melakukannya sebaliknya.

Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif g sedemikian rupa sehingga:

$g(\langle u,v\rangle )={\begin{cases}0&{\text{jika}}\ \langle u,v\rangle \notin S\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ \langle u,v\rangle \in S\end{cases}}$

Namun u = v di G jika dan hanya jika uv⁻¹=1 di G . Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif h sehingga:

$h(x)={\begin{cases}0&{\text{jika}}\ x\neq 1\ {\text{pada}}\ G\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ x=1\ {\text{pada}}\ G\end{cases}}$

Contoh

Berikut ini akan dibuktikan sebagai contoh penggunaan teknik ini:

Teorema: Grup residual finit yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan.

Bukti: Seharusnya G = ⟨X|R⟩ adalah suatu grup yang terbatas sisa.

Misalkan S menjadi grup dari semua permutasi dari N, bilangan asli, yang memperbaiki semua kecuali banyak bilangan hingga:

1. S adalah terbatas lokal dan berisi salinan dari setiap grup hingga.
2. Masalah kata dalam S dapat dipecahkan dengan menghitung produk permutasi.
3. Ada pencacahan rekursif dari semua pemetaan himpunan hingga X menjadi S .
4. Karena G adalah residual finite, jika w adalah sebuah kata di generator X dari G maka w ≠ 1 dalam G jika dan hanya beberapa pemetaan X menjadi S menyebabkan homomorfisme sedemikian rupa sehingga w ≠ 1 pada S.

Dengan fakta-fakta ini, algoritma ditentukan oleh pseudocode berikut:

For setiap pemetaan X menjadi S
    If setiap relator di R puas di S
        If w ≠ 1 pada S
            return 0
        End if
    End if
End for

mendefinisikan fungsi rekursif h seperti itu:

$h(x)={\begin{cases}0&{\text{jika}}\ x\neq 1\ {\text{pada}}\ G\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ x=1\ {\text{pada}}\ G\end{cases}}$

Ini menunjukkan bahwa G memiliki masalah kata yang dapat dipecahkan.

Struktur aljabar dan soal kata

Ada beberapa hasil yang menghubungkan solvabilitas dari soal kata dan struktur aljabar. Yang paling signifikan dari ini adalah Teorema Boone-Higman:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan dalam grup sederhana yang dapat disematkan dalam grup yang disajikan secara terbatas.

Dipercaya secara luas bahwa konstruksi harus mungkin dilakukan sehingga kelompok sederhana itu sendiri disajikan dengan baik. Jika demikian, orang akan sulit untuk membuktikannya karena pemetaan dari presentasi ke grup sederhana harus non-rekursif.

Berikut ini telah dibuktikan oleh Bernhard Neumann dan Angus Macintyre:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan di setiap grup tertutup aljabar

Hal yang luar biasa tentang hal ini adalah bahwa grup tertutup secara aljabar sangat liar sehingga tidak ada yang memiliki presentasi rekursif.

Hasil tertua yang menghubungkan struktur aljabar dengan solvabilitas masalah kata adalah teorema Kuznetsov:

Grup sederhana yang disajikan secara rekursif S memiliki masalah kata yang dapat dipecahkan.

Untuk membuktikan ini mari ⟨X|R⟩ menjadi presentasi rekursif untuk S . Pilih a ∈ S sehingga a ≠ 1 pada S .

Jika w adalah kata pada generator X dari S , maka biarkan:

$S_{w}=\langle X|R\cup \{w\}\rangle .$

Ada fungsi rekursif $f_{\langle X|R\cup \{w\}\rangle }$ yaitu:

$f_{\langle X|R\cup \{w\}\rangle }(x)={\begin{cases}0&{\text{jika}}\ x=1\ {\text{pada}}\ S_{w}\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ x\neq 1\ {\text{pada}}\ S_{w}.\end{cases}}$

Menulis:

$g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).$

Kemudian karena konstruksi f seragam, ini adalah fungsi rekursif dari dua variabel.

Maka dari itu: $h(w)=g(w,a)$ bersifat rekursif. Dengan konstruksi:

$h(w)={\begin{cases}0&{\text{jika}}\ a=1\ {\text{pada}}\ S_{w}\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ a\neq 1\ {\text{pada}}\ S_{w}.\end{cases}}$

Karena S adalah grup sederhana, satu-satunya grup hasil bagi adalah dirinya sendiri dan grup trivial. Karena itu:

$h(w)={\begin{cases}0&{\text{jika}}\ w\neq 1\ {\text{pada}}\ S\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ w=1\ {\text{pada}}\ S.\end{cases}}$

Adanya fungsi seperti itu cukup untuk membuktikan bahwa masalah kata dapat dipecahkan untuk S .

Bukti ini tidak membuktikan adanya algoritma yang seragam untuk menyelesaikan masalah kata untuk kelas kelompok ini. Ketidakseragaman terletak pada pemilihan elemen non-sepele dari kelompok sederhana. Tidak ada alasan untuk menganggap bahwa ada fungsi rekursif yang memetakan presentasi dari grup sederhana ke elemen non-trivial grup. Namun, dalam kasus grup yang disajikan secara terbatas, kami tahu bahwa tidak semua generator bisa sepele (Generator individual apa pun, tentu saja). Menggunakan fakta ini dimungkinkan untuk memodifikasi bukti untuk menunjukkan:

Masalah kata dapat dipecahkan secara seragam untuk kelas kelompok sederhana yang disajikan secara terbatas.

Lihat pula

• Kombinatorik pada kata
• SQ-grup universal
• Masalah kata (matematika)
• Reachability problem
• Automata tumpukan bersarang (telah digunakan untuk memecahkan masalah kata untuk grup)

Referensi

• Word problem, PlanetMath.org.
• W. W. Boone, F. B. Cannonito, and R. C. Lyndon. Word Problems: Decision Problem in Group Theory. Netherlands: North-Holland. 1973.
• Boone, W. W.; Higman, G. (1974). "An algebraic characterization of the solvability of the word problem". J. Austral. Math. Soc. 18: 41–53. doi:10.1017/s1446788700019108 . 
• Boone, W. W.; Rogers Jr, H. (1966). "On a problem of J. H. C. Whitehead and a problem of Alonzo Church". Math. Scand. 19: 185–192. doi:10.7146/math.scand.a-10808 . 
• Borisov, V. V. (1969), "Simple examples of groups with unsolvable word problem", Akademiya Nauk SSSR. Matematicheskie Zametki, 6: 521–532, ISSN 0025-567X, MR 0260851 
• Collins, Donald J. (1969), "Word and conjugacy problems in groups with only a few defining relations", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 15 (20–22): 305–324, doi:10.1002/malq.19690152001, MR 0263903 
• Collins, Donald J. (1972), "On a group embedding theorem of V. V. Borisov", Bulletin of the London Mathematical Society, 4 (2): 145–147, doi:10.1112/blms/4.2.145, ISSN 0024-6093, MR 0314998 
• Collins, Donald J. (1986), "A simple presentation of a group with unsolvable word problem", Illinois Journal of Mathematics, 30 (2): 230–234, doi:10.1215/ijm/1256044631 , ISSN 0019-2082, MR 0840121 
• Collins, Donald J.; Zieschang, H. (1990), Combinatorial group theory and fundamental groups, Berlin, New York: Springer-Verlag, hlm. 166, MR 1099152 
• Dehn, Max (1911), "Über unendliche diskontinuierliche Gruppen", Mathematische Annalen, 71 (1): 116–144, doi:10.1007/BF01456932, ISSN 0025-5831, MR 1511645, diarsipkan dari versi asli tanggal 2016-03-05, diakses tanggal 2020-12-11 
• Dehn, Max (1912), "Transformation der Kurven auf zweiseitigen Flächen", Mathematische Annalen, 72 (3): 413–421, doi:10.1007/BF01456725, ISSN 0025-5831, MR 1511705, diarsipkan dari versi asli tanggal 2016-03-05, diakses tanggal 2020-12-11 
• A. V. Kuznetsov, "Algorithms as operations in algebraic systems", Izvestia Akad. Nauk SSSR Ser Mat (1958)
• C. F. Miller. "Decision problems for groups -- survey and reflections." In Algorithms and Classification in Combinatorial Group Theory, pages 1–60. Springer, 1991.
• Rotman, Joseph (1994), An introduction to the theory of groups, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94285-8 
• Stillwell, J. (1982). "The word problem and the isomorphism problem for groups". Bulletin of the AMS. 6: 33–56. doi:10.1090/s0273-0979-1982-14963-1 .