Skip to Main content Skip to Navigation
Reports

On the Equivalence of Two Systems of Affine Recurrence Equations

Denis Barthou 1 Paul Feautrier Xavier Redon
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : This paper deals with the problem of deciding whether two Systems of Affine Recurrence Equations are equivalent or not. A solution to this problem would be a first step toward algorithm recognition, an important tool in program analysis, optimization and parallelization. We first prove that in the general case, the problem is undecidable. The proof is by reducing any instance of Hilbert's tenth problem (the solution of Diophantine equations) to the equivalence of two SAREs. We then show that there neverthele- ss exists a semi-algorithm, in which the key ingredient is the computation of transitive closures of affine relations. This is again an undecidable problem which has been extensively studied. Many partial solutions are known. We then report on a pilot implementation of the algorithm, describe its limitations, and point to unsolved problems.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072302
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:21:07 PM
Last modification on : Wednesday, September 16, 2020 - 4:57:21 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:02:58 PM

Identifiers

  • HAL Id : inria-00072302, version 1

Collections

Citation

Denis Barthou, Paul Feautrier, Xavier Redon. On the Equivalence of Two Systems of Affine Recurrence Equations. RR-4285, INRIA. 2001. ⟨inria-00072302⟩

Share

Metrics

Record views

229

Files downloads

699