Metraipolis › archive › dc_2d47358d87a4

Complétion de Knuth-Bendix — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-05T09:45:30.968Z
SHA-256 of the archived text
04232eca76d1e0b0f50dca4436cb3f20994050d326a518fa287bffee3fa9134b
Stable URL of this page
https://metraipolis.com/documento/dc_2d47358d87a4

How to cite

Complétion de Knuth-Bendix — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2d47358d87a4 (Metraipolis archive dc_2d47358d87a4, sha256 04232eca76d1e0b0f50dca4436cb3f20994050d326a518fa287bffee3fa9134b)
BibTeX
@misc{dc2d47358d87a4,
  title = {Complétion de Knuth-Bendix — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2d47358d87a4; sha256 04232eca76d1e0b0f50dca4436cb3f20994050d326a518fa287bffee3fa9134b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

La procédure de complétion de Knuth-Bendix ou complétion de Knuth-Bendix (aussi appelée algorithme de Knuth-Bendix ) transforme, si elle réussit, un ensemble fini d'identités (sur des termes) décrivant une structure algébrique en un système de réécriture de termes confluent et qui termine (dit alors convergent). Le processus de complétion a été inventé par Donald Knuthaidé d'un étudiant, nommé Peter Bendix, pour la mise en œuvre. En cas de réussite, la complétion donne un moyen effectif de résoudre le problème du mot pour l'algèbre en question, comme cela a été démontré par Gérard Huet. Par exemple, pour la théorie équationnelle des groupes (voir schéma à droite), la complétion fournit un système de réécriture de terme confluent et qui termine. On peut alors décider si une équation t1 = t2 est vraie dans tous les groupes (même si décider si une formule du premier ordre est vraie dans tous les groupes est indécidable). Malheureusement, le problème du mot étant indécidable en général, la procédure de complétion 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 variante de la procédure de complétion 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, dans tous les cas où elle l'est effectivement, mais peut ne jamais terminer.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Complétion de Knuth-Bendix» — https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix
Wikidata Q2835803: «semi-decision algorithm for transforming a set of equations» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2835803
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Compl%C3%A9tion_de_Knuth-Bendix?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 240351324, consultata il 2026-11-05T09:43:03.906Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2d563f50dc2d9611e71166984ac58705a5882c9ec2643b7dbd5f3d8c8cf9be95