Markus Müller-Olm and Helmut Seidl. A Note on Karr's Algorithm. In Josep Díaz, Juhani Karhumäki, Arto Lepistö and Donald Sannella, editors, Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 1016-1028, Turku, Finland, July 2004. Springer.

We give a simple formulation of Karr's algorithm for computing all affine relationships in affine programs. This simplified algorithm runs in time $\mathcal {O}(nk^{3})$ where $\mathnormal {n}$ is the program size and $\mathnormal {k}$ is the number of program variables assuming unit cost for arithmetic operations. This improves upon the original formulation by a factor of $\mathnormal {k}$ . Moreover, our re-formulation avoids exponential growth of the lengths of intermediately occurring numbers (in binary representation) and uses less complicated elementary operations. We also describe a generalization that determines all polynomial relations up to degree d in time $\mathcal {O}(nk^{3d})$ .

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com