About: dbpedia-fr:Problème_du_mot     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : fr.dbpedia.org associated with source document(s)

AttributesValues
rdfs:label
  • Problème du mot (fr)
rdfs:comment
  • Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donnée une paire de termes et de la structure, est-ce que l'égalité est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncé par Tarski en 1949 et publié dans le livre Undecidable Theories. (fr)
sameAs
Wikipage page ID
Wikipage revision ID
dbo:wikiPageWikiLink
page length (characters) of wiki page
dct:subject
prop-fr:wikiPageUsesTemplate
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
has abstract
  • Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donnée une paire de termes et de la structure, est-ce que l'égalité est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncé par Tarski en 1949 et publié dans le livre Undecidable Theories. Le problème du mot en logique combinatoire est indécidable. Le problème du mot pour les groupes est indécidable en général, mais décidable dans de nombreux cas : il existe un algorithme qui décide si est vraie dans tous les groupes. Le problème du mot dans les groupes est aussi décidable pour de nombreuses classes de présentations de groupes, par exemple pour les groupes de Coxeter et plus généralement pour les groupes automatiques, mais est indécidable en général, pour une présentation quelconque d'un groupe par générateurs et relations. En 1955, Novikov a même prouvé qu'il existe des présentations de groupes ayant un problème du mot indécidable. De nombreux problèmes de décision en mathématiques peuvent être formulés comme des problèmes du mot (voir la (en)). (fr)
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of
Faceted Search & Find service v1.16.111 as of Oct 19 2022


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 14 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software