Reescritura con restricciones de reemplazamiento

Abstract

La reescritura de términos constituye un mecanismo operacional útil para implementar un buen número de sistemas computacionales cuyo modelo de ejecución de basa en reducir una expresión inicial hasta obtener otra expresión con un contenido semántico bien definido y suficiente para los fines perseguidos, Para conseguir este objetivo computacional es necesario, en la práctica, restingir el espacio de reducciones asociado a la expresión inicial, filtrando las secuencias de reescritrua que no conducen a una forma canónica de interés. Esta optimización se pude realizar introduciendo restriciones de reemplazamiento sintácticas vinculadas a los términos que participan en las secuencias de reducción. En este trabajo formulamos y caracterizamos una forma de cómputo, que denominamos reescritura sensible al contexto, que explota este tipo de restricciones de la reescritura. Demostramos que el empleo de la reescritura sensible al contexto permite computar una gran variedad de formas canónicas evitando muchas secuencias de reducción no deseables y preservando aún la completitud de los cálculos.