@inbook{c9bd139f3da748ffbe60ad56a6c70504,
title = "A note on Karr's algorithm",
abstract = "We give a simple formulation of Karr's algorithm for computing all affine relationships in affine programs. This simplified algorithm runs in time script O sign(nk3) where n is the program size and k is the number of program variables assuming unit cost for arithmetic operations. This improves upon the original formulation by a factor of 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 script O sign(nk3d).",
author = "Markus M{\"u}ller-Olm and Helmut Seidl",
year = "2004",
doi = "10.1007/978-3-540-27836-8_85",
language = "English",
isbn = "3540228497",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "1016--1028",
editor = "Josep D{\'i}az and Juhani Karhum{\"a}ki and Arto Lepist{\"o} and Donald Sannella",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}