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 where is the program size and is the number of program variables assuming unit cost for arithmetic operations. This improves upon the original formulation by a factor of . 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 .
Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com