Algorithme de Knuth-Bendix
- Algorithme de Knuth-Bendix
-
La procédure de complétion de Knuth-Bendix transforme un ensemble d'identités (sur des termes) décrivant une structure algébrique en un système de réécriture de terme confluent et qui termine (dit alors convergent). Quand cette procédure se termine en produisant un système de réécriture convergent, elle donne un moyen effectif de résoudre le problème du mot pour l'algèbre en question. Le problème du mot étant indécidable en général, la procédure ne se termine pas toujours avec succès. Elle peut soit s'exécuter indéfiniment, soit échouer en rencontrant une identité non-orientable (qu'elle ne peut pas transformer en règle de réécriture sans être sûre de ne pas mettre en danger la terminaison).
Il existe une procédure de complétion améliorée qui n'échoue pas sur les identités non orientables. Elle fournit une procédure de semi-décision pour le problème du mot, autrement dit, elle permet de dire si une identité donnée est déductible des identités qui décrivent l'algèbre en question.
Article connexe
Combinatoire des mots
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Knuth-Bendix de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Knuth-Bendix (algorithme) — La procédure de complétion de Knuth Bendix transforme un ensemble d identités (sur des termes) décrivant une structure algébrique en un système de réécriture de terme confluent et qui termine (dit alors convergent). Quand cette procédure se… … Wikipédia en Français
Knuth-bendix (algorithme) — La procédure de complétion de Knuth Bendix transforme un ensemble d identités (sur des termes) décrivant une structure algébrique en un système de réécriture de terme confluent et qui termine (dit alors convergent). Quand cette procédure se… … Wikipédia en Français
Knuth — Donald Knuth Donald Knuth en 2005 Donald Ervin Knuth ( … Wikipédia en Français
Don Knuth — Donald Knuth Donald Knuth en 2005 Donald Ervin Knuth ( … Wikipédia en Français
Donald E. Knuth — Donald Knuth Donald Knuth en 2005 Donald Ervin Knuth ( … Wikipédia en Français
Donald Ervin Knuth — Donald Knuth Donald Knuth en 2005 Donald Ervin Knuth ( … Wikipédia en Français
Donald Knuth — en 2005 Donald Ervin Knuth ([kəˈnuːθ] … Wikipédia en Français
Problème du mot — Le problème du mot est un problème de décision en algèbre abstraite qui consiste, étant données une paire de termes t1 et t2 et une présentation d une structure algébrique, à répondre par algorithme (à décider) si oui ou non l égalité t1 = t2 est … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Reecriture (informatique) — Réécriture (informatique) Pour les articles homonymes, voir Réécriture. La réécriture (ou récriture) est un modèle de calcul utilisé en informatique, en algèbre, en logique mathématique et en linguistique. Il s’agit de transformer des objets… … Wikipédia en Français
