{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T00:50:31Z","timestamp":1782953431613,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404385","type":"print"},{"value":"9783540450139","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45013-0_7","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:06:29Z","timestamp":1184601989000},"page":"71-89","source":"Crossref","is-referenced-by-count":48,"title":["Two Variables per Linear Inequality as an Abstract Domain"],"prefix":"10.1007","author":[{"given":"Axel","family":"Simon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andy","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacob M.","family":"Howe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"7_CR1","unstructured":"R. Bagnara. Data-Flow Analysis for Constrant Logic-Based Languages. PhD thesis, Dipartimento di Informatica, Universit\u00e0 di Pisa, 1997."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"V. Balasundaram and K. Kennedy. A Technique for Summarizing Data Access and its Use in Parallelism Enhancing Transformations. In Programming Language Design and Implementation, pages 41\u201353. ACM Press, 1989.","DOI":"10.1145\/73141.74822"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"F. Bancilhon and R. Ramakrishnan. An Amateur\u2019s Introduction to Recursive Query Processing Strategies. In International Conference on Management of Data, pages 16\u201352. ACM Press, 1986.","DOI":"10.1145\/16894.16859"},{"key":"7_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/3-540-62718-9_12","volume-title":"Logic Program Synthesis and Transformation (Selected Papers)","author":"F. Benoy","year":"1997","unstructured":"F. Benoy and A. King. Inferring Argument Size Relationships with CLP(\u211d). In Logic Program Synthesis and Transformation (Selected Papers), volume 1207 of Lecture Notes in Computer Science, pages 204\u2013223. Springer-Verlag, 1997."},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"J. L. Bentley","year":"1978","unstructured":"J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the Average Number of Maxima in a Set of Vectors. Journal of the ACM, 25:536\u2013543, 1978.","journal-title":"Journal of the ACM"},{"issue":"6","key":"7_CR6","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/0041-5553(68)90115-8","volume":"8","author":"N. V. Chernikova","year":"1968","unstructured":"N. V. Chernikova. Algorithm for Discovering the Set of All Solutions of a Linear Programming Problem. USSR Computational Mathematics and Mathematical Physics, 8(6):282\u2013293, 1968.","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"key":"7_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/3-540-55844-6_142","volume-title":"Programming Language Implementation and Logic Programming","author":"P. Cousot","year":"1992","unstructured":"P. Cousot and R. Cousot. Comparing the Galois Connection and Widening\/Narrowing Approaches to Abstract Interpretation. In Programming Language Implementation and Logic Programming, volume 631 of Lecture Notes in Computer Science, pages 269\u2013295. Springer-Verlag, 1992."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"P. Cousot and N. Halbwachs. Automatic Discovery of Linear Restraints among Variables of a Program. In Principles of Programming Languages, pages 84\u201397. ACM Press, 1978.","DOI":"10.1145\/512760.512770"},{"issue":"3","key":"7_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0004-3702(87)90091-9","volume":"32","author":"E. Davis","year":"1987","unstructured":"E. Davis. Constraint Propagation with Interval Labels. Artificial Intelligence, 32(3):281\u2013331, 1987.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"7_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/2422.322417","volume":"31","author":"S. D. Feit","year":"1984","unstructured":"S. D. Feit. A Fast Algorithm for the Two-Variable Integer Programming Problem. Journal of the ACM, 31(1):99\u2013113, 1984.","journal-title":"Journal of the ACM"},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1(4):132\u2013133, 1972.","journal-title":"Information Processing Letters"},{"key":"7_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/3-540-53982-4_10","volume-title":"International Joint Conference on the Theory and Practice of Software Development","author":"P. Granger","year":"1991","unstructured":"P. Granger. Static Analysis of Linear Congruence Equalities among Variables of a Program. In International Joint Conference on the Theory and Practice of Software Development, volume 493 of Lecture Notes in Computer Science, pages 169\u2013192. Springer-Verlag, 1991."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"W. H. Harrison. Compiler Analysis of the Value Ranges for Variables. IEEE Transactions on Software Engineering, SE-3(3), 1977.","DOI":"10.1109\/TSE.1977.231133"},{"issue":"6","key":"7_CR14","doi-asserted-by":"publisher","first-page":"2285","DOI":"10.1137\/S009753979528977X","volume":"28","author":"W. Harvey","year":"1999","unstructured":"W. Harvey. Computing Two-Dimensional Integer Hulls. SIAM Journal on Computing, 28(6):2285\u20132299, 1999.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"7_CR15","first-page":"102","volume":"19","author":"W. Harvey","year":"1997","unstructured":"W. Harvey and P. J. Stuckey. A Unit Two Variable per Inequality Integer Constraint Solver for Constraint Logic Programming. Australian Computer Science Communications, 19(1):102\u2013111, 1997.","journal-title":"Australian Computer Science Communications"},{"issue":"6","key":"7_CR16","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"D. S. Hochbaum","year":"1994","unstructured":"D. S. Hochbaum and J. Naor. Simple and Fast Algorithms for Linear and Integer Programs with Two Variables per Inequality. SIAM Journal on Computing, 23(6):1179\u20131192, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/10720327_8","volume-title":"Logic Programming, Synthesis and Transformation (Selected Papers)","author":"J. M. Howe","year":"1999","unstructured":"J. M. Howe and A. King. Specialising Finite Domain Programs using Polyhedra. In Logic Programming, Synthesis and Transformation (Selected Papers), volume 1817 of Lecture Notes in Computer Science, pages 118\u2013135. Springer-Verlag, 1999."},{"key":"7_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-58601-6_92","volume-title":"International Workshop on Principles and Practice of Constraint Programming","author":"J. Jaffar","year":"1994","unstructured":"J. Jaffar, M. J. Maher, P. J. Stuckey, and R. H. C. Yap. Beyond Finite Domains. In International Workshop on Principles and Practice of Constraint Programming, volume 874 of Lecture Notes in Computer Science, pages 86\u201394. Springer-Verlag, 1994."},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF00268497","volume":"6","author":"M. Karr","year":"1976","unstructured":"M. Karr. Affine Relationships Among Variables of a Program. Acta Informatica, 6:133\u2013151, 1976.","journal-title":"Acta Informatica"},{"key":"7_CR20","volume-title":"Inequalities-III","author":"V. Klee","year":"1972","unstructured":"V. Klee and G. J. Minty. How Good is the Simplex Algorithm? In Inequalities-III. Academic Press, New York and London, 1972."},{"issue":"1","key":"7_CR21","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"J. C. Lagarias","year":"1985","unstructured":"J. C. Lagarias. The Computational Complexity of Simultaneous Diophantine Approximation Problems. SIAM Journal on Computing, 14(1):196\u2013209, 1985.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"7_CR22","first-page":"271","volume":"6","author":"K. G. Larsen","year":"1999","unstructured":"K. G. Larsen, J. Pearson, C. Weise, and W. Yi. Clock Difference Diagrams. Nordic Journal of Computing, 6(3):271\u2013298, 1999.","journal-title":"Nordic Journal of Computing"},{"key":"7_CR23","series-title":"Technical Report","volume-title":"A Note on Chernikova\u2019s Algorithm","author":"H. Verge Le","year":"1992","unstructured":"H. Le Verge. A Note on Chernikova\u2019s Algorithm. Technical Report 1662, Institut de Recherche en Informatique, Campus Universitaire de Beaulieu, France, 1992."},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"N. Lindenstrauss and Y. Sagiv. Automatic Termination Analysis of Logic Programs. In International Conference on Logic Programming, pages 63\u201377. MIT Press, 1997.","DOI":"10.7551\/mitpress\/4299.003.0011"},{"key":"7_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-44978-7_10","volume-title":"Programs as Data Objects","author":"A. Min\u00e9","year":"2001","unstructured":"A. Min\u00e9. A New Numerical Abstract Domain Based on Difference-Bound Matrices. In Programs as Data Objects, volume 2053 of Lecture Notes in Computer Science, pages 155\u2013172. Springer, 2001."},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"A. Min\u00e9. The Octagon Abstract Domain. In Eighth Working Conference on Reverse Engineering, pages 310\u2013319. IEEE Computer Society, 2001.","DOI":"10.1109\/WCRE.2001.957836"},{"key":"7_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/3-540-45789-5_11","volume-title":"Ninth International Static Analysis Symposium","author":"A. Min\u00e9","year":"2002","unstructured":"A. Min\u00e9. A Few Graph-Based Relational Numerical Abstract Domains. In Ninth International Static Analysis Symposium, volume 2477 of Lecture Notes in Computer Science, pages 117\u2013132. Springer-Verlag, 2002."},{"key":"7_CR28","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-48168-0_9","volume-title":"Conference of the European Association for Computer Science Logic","author":"J. M\u00f8ller","year":"1999","unstructured":"J. M\u00f8ller, J. Lichtenberg, H. R. Andersen, and H. Hulgaard. Difference Decision Diagrams. In Conference of the European Association for Computer Science Logic, volume 1683 of Lecture Notes in Computer Science, pages 111\u2013125. Springer-Verlag, 1999."},{"key":"7_CR29","unstructured":"C. G. Nelson. An n log(n) Algorithm for the Two-Variable-Per-Constraint Linear Programming Satisfiability Problem. Technical Report STAN-CS-78-689, Stanford University, Department of Computer Science, 1978."},{"key":"7_CR30","unstructured":"V. R. Pratt. Two Easy Theories Whose Combination is Hard, September 1977. http:\/\/boole.stanford.edu\/pub\/sefnp.pdf ."},{"issue":"1","key":"7_CR31","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3212146","volume":"7","author":"H. Raynaud","year":"1970","unstructured":"H. Raynaud. Sur L\u2019enveloppe Convexe des Nuages de Points Al\u00e9atoires dans \u211dn. Journal of Applied Probability, 7(1):35\u201348, 1970.","journal-title":"Journal of Applied Probability"},{"key":"7_CR32","unstructured":"R. Seidel. Convex Hull Computations. In J. E. Goodman and J. O\u2019Rourke, editors, Handbook of Discrete and Computational Geometry, pages 361\u2013376. CRC Press, 1997."},{"key":"7_CR33","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/3-540-46423-9_4","volume-title":"Compiler Construction","author":"R. Shaham","year":"2000","unstructured":"R. Shaham, H. Kolodner, and M. Sagiv. Automatic Removal of Array Memory Leaks in Java. In Compiler Construction, volume 1781 of Lecture Notes in Computer Science, pages 50\u201366. Springer, 2000."},{"issue":"4","key":"7_CR34","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1145\/322276.322288","volume":"28","author":"R. Shostak","year":"1981","unstructured":"R. Shostak. Deciding Linear Inequalities by Computing Loop Residues. Journal of the ACM, 28(4): 769\u2013779, 1981.","journal-title":"Journal of the ACM"},{"key":"7_CR35","unstructured":"Z. Su and D. Wagner. Efficient Algorithms for General Classes of Integer Range Constraints, July 2001. http:\/\/www.cs.berkeley.edu\/~zhendong\/ ."},{"key":"7_CR36","unstructured":"D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A First Step Towards Detection of Buffer Overrun Vulnerabilities. In Network and Distributed System Security Symposium. Internet Society, 2000."}],"container-title":["Lecture Notes in Computer Science","Logic Based Program Synthesis and Transformation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45013-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:48:21Z","timestamp":1737287301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45013-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404385","9783540450139"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-45013-0_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}