On the Recognition of Algorithm Templates
Christophe Alias, Denis Barthou · Electronic Notes in Theoretical Computer Science · 2004
This paper deals with the problem of deciding whether a System of Affine Recurrent Equations (SARE) is an instantiation of a SARE template. A solution to this problem would be a step toward algorithm template recognition and open new perspectives in program analysis, optimization and parallelization. The problem is known to be undecidable and we show that there exists a semi-decision procedure, in which the key ingredient is the computation of transitive closures of affine relations. This is a non-effective process which has been extensively studied. We then describe the limitations of our algorithm and point to unsolved problems.