Knuth-Bendix (algorithme)
- Knuth-Bendix (algorithme)
-
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 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 sure 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.
Portail de la logique
Portail des mathématiques
Portail de l’informatique
Catégories : Réécriture | Algorithmique | Informatique théorique | Algèbre | Algèbre générale | Algorithme
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Knuth-Bendix (algorithme) 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
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… … 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
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
Réécriture (arithmétique) — 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
