@inproceedings{10.1007/978-3-540-27836-8_85,
    Abstract = {We give a simple formulation of Karr's algorithm for computing all affine relationships in affine programs. This simplified algorithm runs in time {\$}{\backslash}mathcal{\{}O{\}}(nk^{\{}3{\}}){\$}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 {\$}{\backslash}mathcal{\{}O{\}}(nk^{\{}3d{\}}){\$}.},
    Address = {Berlin, Heidelberg},
    Author = {M{\"u}ller-Olm, Markus and Seidl, Helmut},
    BookTitle = {Automata, Languages and Programming},
    Editor = {D{\'\i}az, Josep and Karhum{\"a}ki, Juhani and Lepist{\"o}, Arto and Sannella, Donald},
    File = {A Note on Karr's Algorithm.pdf},
    ISBN = {978-3-540-27836-8},
    Pages = {1016--1028},
    Publisher = {Springer Berlin Heidelberg},
    Title = {A Note on Karr's Algorithm},
    Year = {2004},
    date-added = {2023-07-22 06:46:22 +0200},
    date-modified = {2023-07-22 06:46:22 +0200},
    doi = {10.1007/978-3-540-27836-8_85}
}

@inproceedings{10.1007/978-3-540-27836-8_85, Abstract = {We give a simple formulation of Karr's algorithm for computing all affine relationships in affine programs. This simplified algorithm runs in time {\$}{\backslash}mathcal{{}O{}}(nk^{{}3{}}){\$}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 {\$}{\backslash}mathcal{{}O{}}(nk^{{}3d{}}){\$}.}, Address = {Berlin, Heidelberg}, Author = {M{\"u}ller-Olm, Markus and Seidl, Helmut}, BookTitle = {Automata, Languages and Programming}, Editor = {D{\'\i}az, Josep and Karhum{\"a}ki, Juhani and Lepist{\"o}, Arto and Sannella, Donald}, File = {A Note on Karr's Algorithm.pdf}, ISBN = {978-3-540-27836-8}, Pages = {1016--1028}, Publisher = {Springer Berlin Heidelberg}, Title = {A Note on Karr's Algorithm}, Year = {2004}, date-added = {2023-07-22 06:46:22 +0200}, date-modified = {2023-07-22 06:46:22 +0200}, doi = {10.1007/978-3-540-27836-8_85} }