{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T09:59:24Z","timestamp":1648893564453},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,9,16]],"date-time":"2012-09-16T00:00:00Z","timestamp":1347753600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s10601-012-9127-x","type":"journal-article","created":{"date-parts":[[2012,9,15]],"date-time":"2012-09-15T12:30:13Z","timestamp":1347712213000},"page":"461-487","source":"Crossref","is-referenced-by-count":1,"title":["A complexity perspective on entailment of parameterized linear constraints"],"prefix":"10.1007","volume":"17","author":[{"given":"Pavlos","family":"Eirinakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salvatore","family":"Ruggieri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Wojciechowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,9,16]]},"reference":[{"key":"9127_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01758841","volume":"8","author":"I Adler","year":"1992","unstructured":"Adler, I., & Monteiro, R. (1992). A geometric view of parametric linear programming. Algorithmica, 8, 161\u2013176.","journal-title":"Algorithmica"},{"issue":"6","key":"9127_CR2","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., et al. (1996). On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43(6), 1002\u20131045.","journal-title":"Journal of the ACM"},{"issue":"1","key":"9127_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10601-008-9054-z","volume":"14","author":"M Bodirsky","year":"2009","unstructured":"Bodirsky, M., & Chen, H. (2009). Relatively quantified constraint satisfaction. Constraints, 14(1), 3\u201315.","journal-title":"Constraints"},{"issue":"3","key":"9127_CR4","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1023\/B:JOTA.0000004869.66331.5c","volume":"118","author":"F Borrelli","year":"2003","unstructured":"Borrelli, F., et al. (2003). Geometric algorithm for multiparametric linear programming. Journal of Optimization Theory and Applications, 118(3), 515\u2013540.","journal-title":"Journal of Optimization Theory and Applications"},{"issue":"4","key":"9127_CR5","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/968708.968710","volume":"37","author":"CW Brown","year":"2003","unstructured":"Brown, C.W. (2003). QEPCAD B: a program for computing with semi-algebraic sets using CADs. ACM SIGSAM Bullettin, 37(4), 97\u2013108.","journal-title":"ACM SIGSAM Bullettin"},{"issue":"2","key":"9127_CR6","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/1067915.1067917","volume":"4","author":"D Cachera","year":"2005","unstructured":"Cachera, D., & Morin-Allory, K. (2005). Verification of safety properties for parameterized regular systems. ACM Transactions on Embedded Computing Systems, 4(2), 228\u2013266.","journal-title":"ACM Transactions on Embedded Computing Systems"},{"issue":"1","key":"9127_CR7","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02136173","volume":"18","author":"M Cadoli","year":"1996","unstructured":"Cadoli, M., & Schaerf, M. (1996). On the complexity of entailment in propositional multivalued logics. Annals of Mathematics and Artificial Intelligence, 18(1), 29\u201350.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"3","key":"9127_CR8","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0747-7171(08)80152-6","volume":"12","author":"GE Collins","year":"1991","unstructured":"Collins, G.E., & Hong, H. (1991). Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, 12(3), 299\u2013328.","journal-title":"Journal of Symbolic Computation"},{"key":"9127_CR9","doi-asserted-by":"crossref","unstructured":"Col\u00f3n, M., & Sankaranarayanan, S. (2011). Generalizing the template polyhedral domain. In Proc. of the 20th European Symposium on Programming (ESOP 2011), Lecture notes in computer science (Vol. 6602, pp. 176\u2013195). Springer.","DOI":"10.1007\/978-3-642-19718-5_10"},{"issue":"1\u20132","key":"9127_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0747-7171(88)80004-X","volume":"5","author":"JH Davenport","year":"1988","unstructured":"Davenport, J.H., & Heintz, J. (1988). Real quantifier elimination is doubly exponential. Journal of Symbolic Computation, 5(1\u20132), 29\u201335.","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"9127_CR11","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s10601-010-9095-y","volume":"15","author":"E Di Rosa","year":"2010","unstructured":"Di Rosa, E., et al. (2010). Solving satisfiability problems with preferences. Constraints, 15(4), 485\u2013515.","journal-title":"Constraints"},{"issue":"2","key":"9127_CR12","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/261320.261324","volume":"31","author":"A Dolzmann","year":"1997","unstructured":"Dolzmann, A., & Sturm, T. (1997). REDLOG: computer algebra meets computer logic. ACM SIGSAM Bullettin, 31(2), 2\u20139.","journal-title":"ACM SIGSAM Bullettin"},{"issue":"3","key":"9127_CR13","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1023\/A:1006031329384","volume":"21","author":"A Dolzmann","year":"1998","unstructured":"Dolzmann, A., et al. (1998). A new approach for automatic theorem proving in real geometry. Journal of Automated Reasoning, 21(3), 357\u2013380.","journal-title":"Journal of Automated Reasoning"},{"key":"9127_CR14","unstructured":"Dolzmann, A., et al. (1998). Real quantifier elimination in practice. In B.H. Matzat, G.M. Greuel, G. Hiss, (Eds.), Algorithmic algebra and number theory (pp. 221\u2013248). Springer."},{"issue":"1","key":"9127_CR15","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s10601-008-9055-y","volume":"14","author":"U Egly","year":"2009","unstructured":"Egly, U., et al. (2009). A solver for QBFs in negation normal form. Constraints, 14(1), 38\u201379.","journal-title":"Constraints"},{"key":"9127_CR16","unstructured":"Eirinakis, P., et al. (2012). Computational complexities of inclusion queries over polyhedral sets. In Int. Symposium on Artif icial Intelligence and Mathematics (ISAIM 2012). Fort Lauderdale, FL."},{"key":"9127_CR17","volume-title":"Postoptimal analyses, parametric programming, and related topics","author":"T Gal","year":"1995","unstructured":"Gal, T. (1995). Postoptimal analyses, parametric programming, and related topics (2nd ed.). Berlin, Germany: de Gruyter and Co.","edition":"2"},{"key":"9127_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/978-3-540-30494-4_15","volume":"3312","author":"E Giunchiglia","year":"2004","unstructured":"Giunchiglia, E., et al. (2004). QuBE+\u2009+: an efficient QBF solver. Formal Methods in Computer-Aided Design, 3312, 201\u2013213.","journal-title":"Formal Methods in Computer-Aided Design"},{"issue":"1","key":"9127_CR19","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s10601-008-9053-0","volume":"14","author":"A Goldsztejn","year":"2009","unstructured":"Goldsztejn, A., et al. (2009). Efficient handling of universally quantified inequalities. Constraints, 14(1), 117\u2013135.","journal-title":"Constraints"},{"key":"9127_CR20","unstructured":"Gottlob, G., et al. (2005). The complexity of quantified constraint satisfaction problems under structural restrictions. In L.P. Kaelbling & A. Saffiotti (Eds.), Proc. of Int. Joint Conf. on Artificial Intelligence (IJCAI 2005) (pp. 150\u2013155). Professional Book Center."},{"issue":"1\u20132","key":"9127_CR21","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF02284624","volume":"17","author":"HJ Greenberg","year":"1996","unstructured":"Greenberg, H.J. (1996). Consistency, redundancy, and implied equalities in linear systems. Annals of Mathematics and Artificial Intelligence, 17(1\u20132), 37\u201383.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"11","key":"9127_CR22","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1002\/1097-0207(20000820)48:11<1583::AID-NME962>3.0.CO;2-W","volume":"48","author":"NI Ioakimidis","year":"2000","unstructured":"Ioakimidis, N.I. (2000). Derivation of feasibility conditions in engineering problems under parametric inequality constraints with classical Fourier elimination. International Journal for Numerical Methods in Engineering, 48(11), 1583\u20131599.","journal-title":"International Journal for Numerical Methods in Engineering"},{"key":"9127_CR23","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.K. (1984). A new polynomial\u2013time algorithm for linear programming. In Proceedings of the 16th annual ACM symposium on theory of computing (pp. 302\u2013311).","DOI":"10.1145\/800057.808695"},{"issue":"1","key":"9127_CR24","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF00941167","volume":"65","author":"SS Keerthi","year":"1990","unstructured":"Keerthi, S.S., & Sridharan, K. (1990). Solution of parameterized linear inequalities by Fourier elimination and its applications. Journal of Optimization Theory and Applications, 65(1), 161\u2013169.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"9127_CR25","first-page":"1093","volume":"20","author":"LG Khachiyan","year":"1979","unstructured":"Khachiyan, L.G. (1979). A polynomial algorithm in linear programming. Doklady Akademiia Nauk SSSR, 224, 1093\u20131096 (English Translation: Soviet Mathematics Doklady, 20, 1093\u20131096).","journal-title":"Soviet Mathematics Doklady"},{"key":"9127_CR26","unstructured":"Kvasnica, M. (2009). Real-time model predictive control via multi-parametric programming: Theory and tools. VDM Verlag."},{"key":"9127_CR27","unstructured":"Kvasnica, M., et al. (2011). Multi-Parametric Toolbox. Available at http:\/\/control.ee.ethz.ch\/~mpt ."},{"key":"9127_CR28","doi-asserted-by":"crossref","unstructured":"Le Berre, D., et al. (2004). Challenges in the QBF arena: the SAT\u201903 evaluation of QBF solvers. In Proc. of the 6th int. conf. on theory and applications of satisfiability testing (SAT 2003). Lecture notes in computer science (Vol. 2919, pp. 468\u2013485). Springer.","DOI":"10.1007\/978-3-540-24605-3_35"},{"key":"9127_CR29","unstructured":"Loechner, V. (2011). Polylib: a library for manipulating parameterized polyhedra. Available at http:\/\/icps.u-strasbg.fr\/polylib ."},{"key":"9127_CR30","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1023\/A:1025117523902","volume":"25","author":"V Loechner","year":"1997","unstructured":"Loechner, V., & Wilde, D.K. (1997). Parameterized polyhedra and their vertices. International Journal of Parallel Programming, 25, 525\u2013549.","journal-title":"International Journal of Parallel Programming"},{"key":"9127_CR31","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01581642","volume":"19","author":"KG Murty","year":"1980","unstructured":"Murty, K.G. (1980). Computational complexity of parametric linear programming. Mathematical Programming, 19, 213\u2013219.","journal-title":"Mathematical Programming"},{"key":"9127_CR32","volume-title":"Linear programming","author":"KG Murty","year":"1983","unstructured":"Murty, K.G. (1983). Linear programming. Hoboken, NJ, USA: Wiley."},{"key":"9127_CR33","doi-asserted-by":"crossref","DOI":"10.1002\/9783527631230","volume-title":"Multi-parametric model-based control: Theory and applications, Process systems engineering series, (Vol. 2)","author":"EN Pistikopoulos","year":"2007","unstructured":"Pistikopoulos, E.N., et al. (2007). Multi-parametric model-based control: Theory and applications, Process systems engineering series (Vol. 2). Weinheim: Wiley-VCH."},{"key":"9127_CR34","doi-asserted-by":"crossref","DOI":"10.1002\/9783527631216","volume-title":"Multi-parametric programming: Theory, algorithms and applications, process systems engineering series, (Vol. 1)","author":"EN Pistikopoulos","year":"2007","unstructured":"Pistikopoulos, E.N., et al. (2007). Multi-parametric programming: Theory, algorithms and applications, process systems engineering series (Vol. 1). Weinheim: Wiley-VCH."},{"issue":"1","key":"9127_CR35","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/s10601-008-9051-2","volume":"14","author":"L Pulina","year":"2009","unstructured":"Pulina, L., & Tacchella, A. (2009). A self-adaptive multi-engine solver for quantified boolean formulas. Constraints, 14(1), 80\u2013116.","journal-title":"Constraints"},{"issue":"4","key":"9127_CR36","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/1183278.1183282","volume":"7","author":"S Ratschan","year":"2006","unstructured":"Ratschan, S. (2006). Efficient solving of quantified inequality constraints over the real numbers. ACM Transactions on Computational Logic, 7(4), 723\u2013748.","journal-title":"ACM Transactions on Computational Logic"},{"key":"9127_CR37","unstructured":"Ratschan, S. (2011). RSOLVER. Available at http:\/\/rsolver.sourceforge.net ."},{"issue":"3","key":"9127_CR38","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"Renegar, J. (1992). On the computational complexity and geometry of the first-order theory of the reals. Journal of Symbolic Computation, 13(3), 255\u2013352.","journal-title":"Journal of Symbolic Computation"},{"key":"9127_CR39","doi-asserted-by":"crossref","unstructured":"Ruggieri, S., & Mesnard, F. (2010). Typing linear constraints. ACM Transactions on Programming Languages and Systems, 32(6), Article 21. doi: 10.1145\/1749608.1749610 .","DOI":"10.1145\/1749608.1749610"},{"issue":"2","key":"9127_CR40","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00939219","volume":"53","author":"M Schechter","year":"1987","unstructured":"Schechter, M. (1987). Polyhedral functions and multiparametric linear programming. Journal of Optimization Theory and Applications, 53(2), 269\u2013280.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"9127_CR41","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1987","unstructured":"Schrijver, A. (1987). Theory of linear and integer programming. New York: Wiley."},{"key":"9127_CR42","doi-asserted-by":"crossref","unstructured":"Solares, C., & Chaves, E.W.V. (2008). Feasibility conditions in engineering problems involving a parametric system of linear inequalities. In Advances in mathematical and statistical modeling. Statistics for industry and technology (pp. 331\u2013340). Birkhuser Boston.","DOI":"10.1007\/978-0-8176-4626-4_25"},{"issue":"3","key":"9127_CR43","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","volume":"20","author":"ED Sontag","year":"1985","unstructured":"Sontag, E.D. (1985). Real addition and the polynomial hierarchy. Information Processing Letters, 20(3), 115\u2013120.","journal-title":"Information Processing Letters"},{"issue":"1","key":"9127_CR44","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/s10601-008-9052-1","volume":"14","author":"D Stynes","year":"2009","unstructured":"Stynes, D., & Brown, K.N. (2009). Value ordering for quantified CSPs. Constraints, 14(1), 16\u201337.","journal-title":"Constraints"},{"key":"9127_CR45","doi-asserted-by":"crossref","unstructured":"Subramani, K. (2002). An analysis of zero-clairvoyant scheduling. In J.P. Katoen & P. Stevens (Eds.), Proceedings of the 8th international conference on tools and algorithms for the construction of Systems (TACAS). Lecture notes in computer science (Vol. 2280, pp. 98\u2013112). Springer.","DOI":"10.1007\/3-540-46002-0_8"},{"issue":"2","key":"9127_CR46","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10951-005-6367-2","volume":"8","author":"K Subramani","year":"2005","unstructured":"Subramani, K. (2005). An analysis of totally clairvoyant scheduling. Journal of Scheduling, 8(2), 113\u2013133.","journal-title":"Journal of Scheduling"},{"issue":"5","key":"9127_CR47","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/s00224-004-1220-0","volume":"38","author":"K Subramani","year":"2005","unstructured":"Subramani, K. (2005). Tractable fragments of presburger arithmetic. Theory of Computing Systems, 38(5), 647\u2013668.","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"9127_CR48","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10472-007-9085-y","volume":"51","author":"K Subramani","year":"2007","unstructured":"Subramani, K. (2007). On a decision procedure for quantified linear programs. Annals of Mathematics and Artificial Intelligence, 51(1), 55\u201377.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"9127_CR49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2009\/845804","volume":"2009","author":"K Subramani","year":"2009","unstructured":"Subramani, K. (2009). On the complexity of selected satisfiability and equivalence queries over boolean formulas and inclusion queries over hulls. Journal of Applied Mathematics and Decision Sciences (JAMDS), 2009, 1\u201318","journal-title":"Journal of Applied Mathematics and Decision Sciences (JAMDS)"},{"key":"9127_CR50","first-page":"29","volume-title":"Proceedings of the 19th annual ACM symposium on theory of computing","author":"PM Vaidya","year":"1987","unstructured":"Vaidya, P.M. (1987). An algorithm for linear programming which requires O(((m\u2009+\u2009n)n 2\u2009+\u2009(m\u2009+\u2009n)1.5 n)L) arithmetic operations. In A. Aho (Ed.), Proceedings of the 19th annual ACM symposium on theory of computing (pp. 29\u201338). New York: ACM Press."},{"issue":"1\u20132","key":"9127_CR51","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0747-7171(88)80003-8","volume":"4","author":"V Weispfenning","year":"1988","unstructured":"Weispfenning, V. (1988). The complexity of linear problems in fields. Journal of Symbolic Computation, 4(1\u20132), 3\u201327.","journal-title":"Journal of Symbolic Computation"},{"issue":"5","key":"9127_CR52","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0115107","volume":"15","author":"L Willner","year":"1967","unstructured":"Willner, L. (1967). On parametric linear programming. SIAM Journal on Applied Mathematics, 15(5), 1253\u20131257.","journal-title":"SIAM Journal on Applied Mathematics"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-012-9127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-012-9127-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-012-9127-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,4]],"date-time":"2019-07-04T00:01:14Z","timestamp":1562198474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-012-9127-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,16]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9127"],"URL":"https:\/\/doi.org\/10.1007\/s10601-012-9127-x","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,16]]}}}