Mathematical programming: Turing completeness and applications to software analysis

Leo Liberti; Fabrizio Marinelli

doi:10.1007/s10878-014-9715-3

Mathematical programming: Turing completeness and applications to software analysis

Leo Liberti
, Fabrizio Marinelli

IBM Watson Research Center
Polytechnic University of Marche

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	82-104
Nombre de pages	23
journal	Journal of Combinatorial Optimization
Volume	28
Numéro de publication	1
Les DOIs	https://doi.org/10.1007/s10878-014-9715-3
état	Publié - 1 janv. 2014

Accès au document

10.1007/s10878-014-9715-3

Contient cette citation

@article{6a7cbd83b6574ba0a36e11991b9777b7,

title = "Mathematical programming: Turing completeness and applications to software analysis",

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 = "Abstract interpretation, Code verification, Static analysis",

author = "Leo Liberti and Fabrizio Marinelli",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/s10878-014-9715-3",

language = "English",

volume = "28",

pages = "82--104",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

number = "1",

}

TY - JOUR

T1 - Mathematical programming

T2 - Turing completeness and applications to software analysis

AU - Liberti, Leo

AU - Marinelli, Fabrizio

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Abstract interpretation

KW - Code verification

KW - Static analysis

U2 - 10.1007/s10878-014-9715-3

DO - 10.1007/s10878-014-9715-3

M3 - Article

AN - SCOPUS:84903577259

SN - 1382-6905

VL - 28

SP - 82

EP - 104

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Mathematical programming: Turing completeness and applications to software analysis

Résumé

Accès au document

Empreinte digitale

Contient cette citation