Lazi

ligne de traces dans un calcul

Contexte

On a vue qu'une trace est un arbre. On veut ici étudier un parcour particulier, c'est à dire que l'on extrait un sous-arbre maximal ayant au plus un enfant par nœud.

Définition

Soit t une trace d'un calcul c. On dit que l est une ligne de traces de c ssi l est un sous-arbre de t de longueur maximal et n'ayant au plus un enfant par nœud.

Remarque : un arbre ayant au plus un enfant par nœud est une liste. C'est pourquoi on représentera les lignes de traces par des listes.