Masalah kata untuk grup

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.