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 de la logique
  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Knuth-Bendix (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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”