La evaluación de un dato de entrada t a su valor s por medio de un programa funcional, puede descomponerse en una serie de pasos simples de evaluación t=t1 -> t2 -> ... -> tn=s. A menudo se expresa también como t->> s. Esto describe la ejecucion del programa sobre el dato de entrada como una relación entre términos que contiene pares t1 -> t2, t2 -> t3, ..., tn-1 -> tn de pasos de evaluación elementales involucrados en la evaluación completa del dato de entrada.

Ahora podemos describir y estudiar las características operacionales del programa en función de las características de su relación de ejecución asociada.

• Terminación: Se dice que un programa termina si su ejecución no se prolonga indefinidamente. En términos de su relación de ejecución, si no existen secuencias de reducción infinitas como t=t1 -> t2 -> ... -> tn -> ...
• La ejecución de programas funcionales por reescritura suele llevar aparejado un cierto grado de indeterminismo. Esto significa que, dado un término t, pueden arrancar de él secuencias de evaluación distintas. Lo que nos importa es que todas ellas nos lleven al mismo lugar. Esto es lo que expresa la propiedad de confluencia de las computaciones. En términos de la relación de reducción se expresa como sigue: si t->> t' y t->> t'' (es decir, podemos tener dos secuencias de evaluación diferentes que parten del mismo dato de entrada) siempre se verifica t'->> s y t''->> s, es decir, ambas secuencias pueden volver a 'reencauzarse' llevando al mismo valor.