Termination of integer linear programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

79 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 18th International Conference, CAV 2006, Proceedings
PublisherSpringer Verlag
Pages372-385
Number of pages14
ISBN (Print)354037406X, 9783540374060
StatePublished - Jan 1 2006
Externally publishedYes
Event18th International Conference on Computer Aided Verification, CAV 2006 - Seattle, WA, United States
Duration: Aug 17 2006Aug 20 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4144 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Conference on Computer Aided Verification, CAV 2006
CountryUnited States
CitySeattle, WA
Period8/17/068/20/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Termination of integer linear programs'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M. (2006). Termination of integer linear programs. In Computer Aided Verification - 18th International Conference, CAV 2006, Proceedings (pp. 372-385). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4144 LNCS). Springer Verlag.