Optimization Online


Mathematical Programming: Turing completeness and applications to software analysis

Leo Liberti(leoliberti***at***yahoo.com)
Fabrizio Marinelli(fabrizio.marinelli***at***univpm.it)

Abstract: Mathematical Programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of Mathematical Programming to software verification obtained by relaxing one of the properties of Turing complete languages.

Keywords: static analysis, abstract interpretation, verification, MINLP

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Other )

Category 3: Global Optimization (Applications )


Download: [PDF]

Entry Submitted: 10/07/2013
Entry Accepted: 10/08/2013
Entry Last Modified: 10/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society