Résumé : On donne dans cet article
une condition suffisante pour que le plus petit point fixe de
l'équation X = a + f(X)X soit égal au plus petit point
fixe de l'équation X = a + f(a)X. On applique ensuite cette
condition aux programmes logiques récursifs contenant des
règles chaînées: on la traduit en une condition
suffisante sous laquelle un programme récursif contenant n ≥
2 appels récursifs dans le corps de ses règles est
équivalent à un programme linéaire contenant au plus
un appel récursif dans le corps de ses règles. On termine par
une discussion qui replace notre condition par rapport à d'autres
approches existant dans la littérature.
Abstract : We first give in this paper a sufficient condition under
which the the least fixpoint of the equation X = a + f(X)X equals
the least fixpoint of the equation X = a + f(a)X; we then apply that
condition to recursive logic programs containing chain rules: we translate
it into a sufficient condition under which a recursive logic program
containing n ≥ 2 recursive calls in the bodies of the rules is
equivalent to a linear program containing at most one recursive call in the
bodies of the rules. We conclude with a discussion comparing our condition
with the other approaches to linearization studied in the literature.