Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S1571-0661(05)82599-X | Electronic Notes in Theoretical Computer Science |
Keywords | Field | DocType |
algorithm recognition,SARE,templates,unification,preliminary approach | Affine transformation,Discrete mathematics,Existential quantification,Computer science,Unification,Algorithm,Theoretical computer science,Template,Program analysis,Transitive relation,Computation,Undecidable problem | Journal |
Volume | Issue | ISSN |
82 | 2 | 1571-0661 |
Citations | PageRank | References |
11 | 0.56 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christophe Alias | 1 | 161 | 8.05 |
Denis Barthou | 2 | 238 | 26.14 |