Polynomial invariant generation for non-deterministic recursive programs

K. Chatterjee, H. Fu, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 672–687.


Conference Paper | Published | English

Scopus indexed
Department
Abstract
We consider the classical problem of invariant generation for programs with polynomial assignments and focus on synthesizing invariants that are a conjunction of strict polynomial inequalities. We present a sound and semi-complete method based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize positive polynomials over a semi-algebraic set. On the theoretical side, the worst-case complexity of our approach is subexponential, whereas the worst-case complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential. Even when restricted to linear invariants, the best previous complexity for complete invariant generation is exponential (Colon et al, CAV 2003). On the practical side, we reduce the invariant generation problem to quadratic programming (QCLP), which is a classical optimization problem with many industrial solvers. We demonstrate the applicability of our approach by providing experimental results on several academic benchmarks. To the best of our knowledge, the only previous invariant generation method that provides completeness guarantees for invariants consisting of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination and cannot even handle toy programs such as our running example.
Publishing Year
Date Published
2020-06-11
Proceedings Title
Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
Page
672-687
Conference
PLDI: Programming Language Design and Implementation
Conference Location
London, United Kingdom
Conference Date
2020-06-15 – 2020-06-20
IST-REx-ID

Cite this

Chatterjee K, Fu H, Goharshady AK, Goharshady EK. Polynomial invariant generation for non-deterministic recursive programs. In: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2020:672-687. doi:10.1145/3385412.3385969
Chatterjee, K., Fu, H., Goharshady, A. K., & Goharshady, E. K. (2020). Polynomial invariant generation for non-deterministic recursive programs. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 672–687). London, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3385412.3385969
Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, 672–87. Association for Computing Machinery, 2020. https://doi.org/10.1145/3385412.3385969.
K. Chatterjee, H. Fu, A. K. Goharshady, and E. K. Goharshady, “Polynomial invariant generation for non-deterministic recursive programs,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, London, United Kingdom, 2020, pp. 672–687.
Chatterjee K, Fu H, Goharshady AK, Goharshady EK. 2020. Polynomial invariant generation for non-deterministic recursive programs. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation 672–687.
Chatterjee, Krishnendu, et al. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 672–87, doi:10.1145/3385412.3385969.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1902.04373v3

Search this title in

Google Scholar
ISBN Search