Termination of Linear Programs with Nonlinear Constraints

Details Termination of Linear Programs with Nonlinear Constraints Termination of Linear Programs with Nonlinear Constraints

2009-04-23

arxiv.org/abs/0904.3588v1

Computer Science

Logic in Computer Science

17pages, 0 figures

Scientific paper

Tiwari proved that termination of linear programs (loops with linear loop conditions and updates) over the reals is decidable through Jordan forms and eigenvectors computation. Braverman proved that it is also decidable over the integers. In this paper, we consider the termination of loops with polynomial loop conditions and linear updates over the reals and integers. First, we prove that the termination of such loops over the integers is undecidable. Second, with an assumption, we provide an complete algorithm to decide the termination of a class of such programs over the reals. Our method is similar to that of Tiwari in spirit but uses different techniques. Finally, we conjecture that the termination of linear programs with polynomial loop conditions over the reals is undecidable in general by %constructing a loop and reducing the problem to another decision problem related to number theory and ergodic theory, which we guess undecidable.

Affiliated with

Also associated with

No associations

Rating

Termination of Linear Programs with Nonlinear Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Termination of Linear Programs with Nonlinear Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Termination of Linear Programs with Nonlinear Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408527