## [Completación Knuth–Bendix](/es/node/63958) Definición Un procedimiento algorítmico que toma un conjunto de reglas de reescritura (o relaciones) junto con un orden de reducción bien fundado e intenta extender el conjunto de reglas añadiendo consecuencias (resolviendo pares críticos) para producir un sistema de reescritura confluyente (y terminante) que resuelve el problema de las palabras en el álgebra presentada cuando tiene éxito. ## Principio Principio Calcular sistemáticamente los solapamientos (pares críticos) entre reglas, orientar las igualdades resultantes según un orden de términos elegido y añadir nuevas reglas para resolver divergencias; repetir hasta que no queden pares críticos sin resolver o el proceso no termine. ## Demostración Demostración Dada una presentación finitamente generada de un monoide o grupo, convertir las relaciones en reglas de reducción orientadas con un orden por longitud o lexicográfico, calcular los pares críticos de los solapamientos de las partes izquierdas, añadir reglas resolventes y simplificar de forma iterativa. Si el procedimiento termina en un sistema confluyente, dos palabras son iguales en el álgebra presentada si y sólo si se reducen a la misma forma normal. ## Aplicación incorrecta Aplicación incorrecta Suponer que el algoritmo siempre termina o que siempre logra la confluencia; empezar con un orden malo o no bien fundado o ignorar axiomas ecuacionales (como la conmutatividad) puede impedir el éxito o producir conclusiones incorrectas sobre el problema de las palabras. ## Consecuencia Consecuencia Cuando tiene éxito, la completación proporciona un sistema de reescritura terminante y confluyente y por tanto una solución efectiva por formas normales al problema de las palabras; también expone consecuencias estructurales como representantes canónicos y procedimientos de decisión para la igualdad. ## Inversión Inversión La perspectiva inversa es introducir deliberadamente solapamientos ambiguos (eliminando reglas o debilitando órdenes) para producir sistemas no confluyentes, lo que puede ser útil para explorar presentaciones alternativas pero pierde la decidibilidad de formas normales. ## Límite Límite Se aplica a sistemas de reescritura de términos, presentaciones de monoides o grupos y teorías ecuacionales cuando existe un orden bien fundado compatible; no garantiza éxito para todas las presentaciones y debe adaptarse (o reemplazarse) en teorías con conmutatividad incorporada, restricciones ecuacionales de aridad mayor o donde la terminación no puede imponerse. ## Tensión semántica Tensión semántica Tensión con técnicas de bases de Gröbner y completación modulo teorías: aunque superficiales semejanzas existen, en diferentes marcos algebraicos surgen métodos distintos (ideales polinómicos frente a reescritura de términos para palabras) y los usuarios a veces confunden las garantías de terminación/confluencia entre estos marcos. ## Síntesis Síntesis La Completación Knuth–Bendix es un intento algorítmico de convertir una presentación en un sistema de reescritura confluyente y terminante mediante la resolución de solapamientos mediante análisis de pares críticos y reducciones orientadas; el éxito da formas normales y un procedimiento de decisión para la igualdad de palabras, pero la terminación y confluencia no están garantizadas en general.