| dbo:abstract
|
- En mathématiques, plus précisément dans le domaine de la théorie combinatoire des groupes, le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs du groupe représentent le même élément. Plus précisément, si X un ensemble fini de générateurs pour G, on considère le langage formel constitué des mots sur X et son ensemble d'inverses formels qui sont envoyés par l'application naturelle sur l'identité du groupe G. Le problème du mot est le problème algorithmique qui consiste à décider de l’appartenance ou non d'un mot à ce langage formel. On peut voir que si Y est un autre ensemble de générateurs pour G, alors le problème du mot avec l'ensemble Y est équivalent au problème du mot avec ensemble X. On peut donc parler sans ambiguïté de la décidabilité du problème du mot pour un groupe G de type fini. Un problème différent mais lié est le problème du mot uniforme pour une classe K de groupes donnés par un ensemble récursif de présentations ; le problème algorithmique est alors de décider, étant donné une présentation P d'un groupe G de la classe K, si deux mots représentent le même élément de G. On peut aussi considérer que la classe K est définissable seulement par un ensemble récursivement énumérable de présentations. Le problème du mot est indécidable dans le cas général, mais est décidable pour de nombreux groupes. Par exemple, les (en) ont un problème du mot décidable ; de même, l'algorithme de Todd-Coxeter et la complétion de Knuth-Bendix donnent des résultats effectifs. D'un autre côté, le fait qu'un algorithme particulier ne s'applique pas dans un cas particulier n'implique pas que le problème du mot est indécidable. Par exemple, l'algorithme de Dehn ne résout pas le problème du mot pour le groupe fondamental du tore, et pourtant ce groupe est le produit direct de deux groupes cycliques infinis et possède donc un problème du mot décidable. (fr)
- Dalam matematika, terutama di bidang aljabar abstrak dikenal sebagai , masalah kata untuk G adalah masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama. Lebih tepatnya, jika A adalah himpunan terbatas 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 . (in)
- In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G. The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G, whether the words represent the same element of G. Some authors require the class K to be definable by a recursively enumerable set of presentations. (en)
- Na álgebra abstrata, o problema da palavra de um receptor recursivo na resolução de um algoritmo de nome grupo G, fornece um algoritmo de duas palavras para G, de forma que representem o mesmo elemento G. Apesar de ser dito popularmente como "Problema da palavra para grupos G" precisamente, ela é uma representação de um grupo que faz ou não faz soluções para esses tipos de problemas. Dadas duas representações finitas P e Q de um grupo G, P têm solução por meio do Problema da palavra para grupos caso Q apresente uma solução e/ou um valor diferente de uma incógnita. Neste caso não há nenhuma confusão em dizer problema da palavra para G (pois G representa quaisquer grandezas e/ou algoritmos inseridos em um conjunto). Quando um conjunto é recursivamente representado, mas não finitamente representado, as distinções se tornam importantes. A relatada (mas não definida) forma desconhecida da palavra para uma classe K recursivamente representa grupos nos problemas aritméticos, dados como uma representação de P de um conjunto G da classe K como duas palavras geradoras de G, como também as palavras também representam os mesmos elementos de G. Alguns problemas requerem a classe K para ser definida como uma "tabela recursiva enumerada de representações". (pt)
|
| rdfs:comment
|
- En mathématiques, plus précisément dans le domaine de la théorie combinatoire des groupes, le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs du groupe représentent le même élément. (fr)
- Dalam matematika, terutama di bidang aljabar abstrak dikenal sebagai , masalah kata untuk G adalah masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama. Lebih tepatnya, jika A adalah himpunan terbatas 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. (in)
- In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G. (en)
- Na álgebra abstrata, o problema da palavra de um receptor recursivo na resolução de um algoritmo de nome grupo G, fornece um algoritmo de duas palavras para G, de forma que representem o mesmo elemento G. Apesar de ser dito popularmente como "Problema da palavra para grupos G" precisamente, ela é uma representação de um grupo que faz ou não faz soluções para esses tipos de problemas. Dadas duas representações finitas P e Q de um grupo G, P têm solução por meio do Problema da palavra para grupos caso Q apresente uma solução e/ou um valor diferente de uma incógnita. Neste caso não há nenhuma confusão em dizer problema da palavra para G (pois G representa quaisquer grandezas e/ou algoritmos inseridos em um conjunto). Quando um conjunto é recursivamente representado, mas não finitamente repres (pt)
|
