@inproceedings{b3368836ec554760895b2cd99f09a505,

title = "Termination of integer linear programs",

abstract = "We show that termination of a simple class of linear loops over the integers is decidable. Namely we show that termination of deterministic linear loops is decidable over the integers in the homogeneous case, and over the rationals in the general case. This is done by analyzing the powers of a matrix symbolically using its eigenvalues. Our results generalize the work of Tiwari [Tiw04], where similar results were derived for termination over the reals. We also gain some insights into termination of non-homogeneous integer programs, that are very common in practice.",

author = "Mark Braverman",

year = "2006",

month = jan,

day = "1",

language = "English (US)",

isbn = "354037406X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "372--385",

booktitle = "Computer Aided Verification - 18th International Conference, CAV 2006, Proceedings",

address = "Germany",

note = "18th International Conference on Computer Aided Verification, CAV 2006 ; Conference date: 17-08-2006 Through 20-08-2006",

}