{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T23:04:03Z","timestamp":1784675043122,"version":"3.55.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319402284","type":"print"},{"value":"9783319402291","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40229-1_14","type":"book-chapter","created":{"date-parts":[[2016,6,11]],"date-time":"2016-06-11T08:54:04Z","timestamp":1465635244000},"page":"195-212","source":"Crossref","is-referenced-by-count":11,"title":["Interpolant Synthesis for Quadratic Polynomial Inequalities and Combination with EUF"],"prefix":"10.1007","author":[{"given":"Ting","family":"Gan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liyun","family":"Dai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bican","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Naijun","family":"Zhan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deepak","family":"Kapur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingshuai","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,12]]},"reference":[{"key":"14_CR1","unstructured":"CSDP. http:\/\/projects.coin-or.org\/Csdp\/"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/978-3-540-70545-1_29","volume-title":"Computer Aided Verification","author":"D Beyer","year":"2008","unstructured":"Beyer, D., Zufferey, D., Majumdar, R.: CSIsat: interpolation for LA+EUF. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 304\u2013308. Springer, Heidelberg (2008)"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/978-3-540-78800-3_30","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A Cimatti","year":"2008","unstructured":"Cimatti, A., Griggio, A., Sebastiani, R.: Efficient interpolant generation in satisfiability modulo theories. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 397\u2013412. Springer, Heidelberg (2008)"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Dai, L., Gan, T., Xia, B., Zhan, N.: Barrier certificate revisited. J. Symbolic Comput. (2016, to appear)","DOI":"10.1016\/j.jsc.2016.07.010"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/978-3-642-39799-8_25","volume-title":"Computer Aided Verification","author":"L Dai","year":"2013","unstructured":"Dai, L., Xia, B., Zhan, N.: Generating non-linear interpolants by semidefinite programming. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 364\u2013380. Springer, Heidelberg (2013)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-642-11319-2_12","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"V D\u2019Silva","year":"2010","unstructured":"D\u2019Silva, V., Kroening, D., Purandare, M., Weissenbacher, G.: Interpolant strength. In: Barthe, G., Hermenegildo, M. (eds.) VMCAI 2010. LNCS, vol. 5944, pp. 129\u2013145. Springer, Heidelberg (2010)"},{"issue":"4","key":"14_CR7","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1023\/A:1008282830093","volume":"10","author":"T Fujie","year":"1997","unstructured":"Fujie, T., Kojima, M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. 10(4), 367\u2013380 (1997)","journal-title":"J. Global Optim."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Gan, T., Dai, L., Xia, B., Zhan, N., Kapur, D., Chen, M.: Interpolation synthesis for quadratic polynomial inequalities and combination with EUF. CoRR, abs\/1601.04802 (2016)","DOI":"10.1007\/978-3-319-40229-1_14"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-63166-6_10","volume-title":"Computer Aided Verification","author":"S Graf","year":"1997","unstructured":"Graf, S., Sa\u00efdi, H.: Construction of abstract state graphs with PVS. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 72\u201383. Springer, Heidelberg (1997)"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Henzinger, T., Jhala, R., Majumdar, R., McMillan, K.: Abstractions from proofs. In: POPL 2004, pp. 232\u2013244 (2004)","DOI":"10.1145\/964001.964021"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-642-19835-9_17","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"Y Jung","year":"2011","unstructured":"Jung, Y., Lee, W., Wang, B.-Y., Yi, K.: Predicate generation for learning-based quantifier-free loop invariant inference. In: Abdulla, P.A., Leino, K.R.M. (eds.) TACAS 2011. LNCS, vol. 6605, pp. 205\u2013219. Springer, Heidelberg (2011)"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Kapur, D., Majumdar, R., Zarba, C.: Interpolation for data structures. In: FSE 2006, pp. 105\u2013116 (2006)","DOI":"10.1145\/1181775.1181789"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/978-3-642-02959-2_17","volume-title":"Automated Deduction \u2013 CADE-22","author":"L Kov\u00e1cs","year":"2009","unstructured":"Kov\u00e1cs, L., Voronkov, A.: Interpolation and symbol elimination. In: Schmidt, R.A. (ed.) CADE-22. LNCS, vol. 5663, pp. 199\u2013213. Springer, Heidelberg (2009)"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Kraj\u00edc\u0306cek, J.: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symbolic Logic 62(2), 457\u2013486 (1997)","DOI":"10.2307\/2275541"},{"key":"14_CR15","series-title":"The IMA Volumes in Mathematics and its Applications","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/978-0-387-09686-5_7","volume-title":"Emerging Applications of Algebraic Geometry","author":"M Laurent","year":"2009","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry. The IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157\u2013270. Springer, New York (2009)"},{"key":"14_CR16","series-title":"lecture notes in computer science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-45069-6_1","volume-title":"Computer Aided Verification","author":"KL McMillan","year":"2003","unstructured":"McMillan, K.L.: Interpolation and SAT-based model checking. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 1\u201313. Springer, Heidelberg (2003)"},{"issue":"1","key":"14_CR17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.tcs.2005.07.003","volume":"345","author":"K McMillan","year":"2005","unstructured":"McMillan, K.: An interpolating theorem prover. Theor. Comput. Sci. 345(1), 101\u2013121 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR18","series-title":"lecture notes in computer scienced","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/978-3-540-78800-3_31","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"KL McMillan","year":"2008","unstructured":"McMillan, K.L.: Quantified invariant generation using an interpolating saturation prover. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 413\u2013427. Springer, Heidelberg (2008)"},{"issue":"3","key":"14_CR19","doi-asserted-by":"crossref","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symbolic Logic 62(3), 981\u2013998 (1997)","journal-title":"J. Symbolic Logic"},{"issue":"11","key":"14_CR20","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1016\/j.jsc.2010.06.005","volume":"45","author":"A Rybalchenko","year":"2010","unstructured":"Rybalchenko, A., Sofronie-Stokkermans, V.: Constraint solving for interpolation. J. Symb. Comput. 45(11), 1212\u20131233 (2010)","journal-title":"J. Symb. Comput."},{"key":"14_CR21","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1998)"},{"issue":"4","key":"14_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-4(4:1)2008","volume":"4","author":"V Sofronie-Stokkermans","year":"2008","unstructured":"Sofronie-Stokkermans, V.: Interpolation in local theory extensions. Logical Methods Comput. Sci. 4(4), 1\u201331 (2008)","journal-title":"Logical Methods Comput. Sci."},{"key":"14_CR23","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01362149","volume":"207","author":"G Stengle","year":"1974","unstructured":"Stengle, G.: A nullstellensatz and a positivstellensatz in semialgebraic geometry. Ann. Math. 207, 87\u201397 (1974)","journal-title":"Ann. Math."},{"issue":"2","key":"14_CR24","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. J. Math. Program. 95(2), 189\u2013217 (2003)","journal-title":"J. Math. Program."},{"issue":"1","key":"14_CR25","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/2629424","volume":"14","author":"Z Yang","year":"2015","unstructured":"Yang, Z., Lin, W., Wu, M.: Exact safety verification of hybrid systems based on bilinear SOS representation. ACM Trans. Embed. Comput. Syst. 14(1), 16:1\u201316:19 (2015)","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"14_CR26","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/11532231_26","volume-title":"Automated Deduction \u2013 CADE-20","author":"G Yorsh","year":"2005","unstructured":"Yorsh, G., Musuvathi, M.: A combination method for generating interpolants. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS (LNAI), vol. 3632, pp. 353\u2013368. Springer, Heidelberg (2005)"},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-642-39698-4_22","volume-title":"Theories of Programming and Formal Methods","author":"H Zhao","year":"2013","unstructured":"Zhao, H., Zhan, N., Kapur, D.: Synthesizing switching controllers for hybrid systems by generating invariants. In: Liu, Z., Woodcock, J., Zhu, H. (eds.) Theories of Programming and Formal Methods. LNCS, vol. 8051, pp. 354\u2013373. Springer, Heidelberg (2013)"},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/978-3-642-32759-9_38","volume-title":"FM 2012: Formal Methods","author":"H Zhao","year":"2012","unstructured":"Zhao, H., Zhan, N., Kapur, D., Larsen, K.G.: A \u201cHybrid\u201d approach for synthesizing optimal controllers of hybrid systems: a case study of the oil pump industrial example. In: Giannakopoulou, D., M\u00e9ry, D. (eds.) FM 2012. LNCS, vol. 7436, pp. 471\u2013485. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40229-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T12:38:41Z","timestamp":1568032721000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40229-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319402284","9783319402291"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40229-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}