{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T02:39:57Z","timestamp":1774838397804,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540691631","type":"print"},{"value":"9783540691662","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69166-2_13","type":"book-chapter","created":{"date-parts":[[2008,7,13]],"date-time":"2008-07-13T09:25:03Z","timestamp":1215941103000},"page":"189-204","source":"Crossref","is-referenced-by-count":33,"title":["Inferring Min and Max Invariants Using Max-Plus Polyhedra"],"prefix":"10.1007","author":[{"given":"Xavier","family":"Allamigeon","sequence":"first","affiliation":[]},{"given":"St\u00e9phane","family":"Gaubert","sequence":"additional","affiliation":[]},{"given":"\u00c9ric","family":"Goubault","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44978-7_10","volume-title":"Programs as Data Objects","author":"A. Min\u00e9","year":"2001","unstructured":"Min\u00e9, A.: A new numerical abstract domain based on difference-bound matrices. In: Danvy, O., Filinski, A. (eds.) PADO 2001. LNCS, vol.\u00a02053, Springer, Heidelberg (2001)"},{"key":"13_CR2","first-page":"310","volume-title":"AST 2001 in WCRE 2001","author":"A. Min\u00e9","year":"2001","unstructured":"Min\u00e9, A.: The octagon abstract domain. In: AST 2001 in WCRE 2001, pp. 310\u2013319. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"13_CR3","volume-title":"PLDI 2003","author":"N. Dor","year":"2003","unstructured":"Dor, N., Rodeh, M., Sagiv, M.: Cssv: towards a realistic tool for statically detecting all buffer overflows in C. In: PLDI 2003, ACM Press, New York (2003)"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11823230_4","volume-title":"Static Analysis","author":"X. Allamigeon","year":"2006","unstructured":"Allamigeon, X., Godard, W., Hymans, C.: Static Analysis of String Manipulations in Critical Embedded C Programs. In: Yi, K. (ed.) SAS 2006. LNCS, vol.\u00a04134, Springer, Heidelberg (2006)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Rival, X., Mauborgne, L.: The trace partitioning abstract domain. ACM TOPLAS\u00a029(5) (2007)","DOI":"10.1145\/1275497.1275501"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Karr, M.: Affine relationships among variables of a program. Acta Inf.\u00a06 (1976)","DOI":"10.1007\/BF00268497"},{"key":"13_CR7","volume-title":"POPL 1978","author":"P. Cousot","year":"1978","unstructured":"Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: POPL 1978, Tucson, Arizona, USA. ACM Press, New York (1978)"},{"issue":"2","key":"13_CR8","first-page":"179","volume":"13","author":"K. Zimmermann","year":"1977","unstructured":"Zimmermann, K.: A general separation theorem in extremal algebras. Ekonom.-Mat. Obzor.\u00a013(2), 179\u2013201 (1977)","journal-title":"Ekonom.-Mat. Obzor."},{"issue":"5","key":"13_CR9","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1023\/A:1010266012029","volume":"69","author":"G. Litvinov","year":"2001","unstructured":"Litvinov, G., Maslov, V., Shpiz, G.: Idempotent functional analysis: an algebraical approach. Math. Notes\u00a069(5), 696\u2013729 (2001); Also eprint arXiv:math.FA\/0009128","journal-title":"Math. Notes"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023465","volume-title":"STACS 97","author":"S. Gaubert","year":"1997","unstructured":"Gaubert, S., Plus, M.: Methods and applications of (max,+) linear algebra. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, Springer, Heidelberg (1997)"},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S1367-5788(99)90091-3","volume":"23","author":"G. Cohen","year":"1999","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.P.: Max-plus algebra and system theory: where we are and where to go now. Annual Reviews in Control\u00a023, 207\u2013219 (1999)","journal-title":"Annual Reviews in Control"},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4171\/dm\/154","volume":"9","author":"M. Develin","year":"2004","unstructured":"Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math.\u00a09, 1\u201327 (2004)","journal-title":"Doc. Math."},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.laa.2003.08.010","volume":"379","author":"G. Cohen","year":"2004","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorem in idempotent semimodules. Linear Algebra and Appl.\u00a0379, 395\u2013422 (2004)","journal-title":"Linear Algebra and Appl."},{"key":"13_CR14","series-title":"Math. Sci. Res. Inst. Publ.","volume-title":"Combinatorial and computational geometry","author":"M. Joswig","year":"2005","unstructured":"Joswig, M.: Tropical halfspaces. In: Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ., vol.\u00a052. Cambridge Univ. Press, Cambridge (2005)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.P., Singer, I.: Max-plus convex sets and functions. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, vol.\u00a0377, pp. 105\u2013129. AMS (2005)","DOI":"10.1090\/conm\/377\/06987"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11828563_13","volume-title":"Relations and Kleene Algebra in Computer Science","author":"S. Gaubert","year":"2006","unstructured":"Gaubert, S., Katz, R.: Max-plus convex geometry. In: Schmidt, R.A. (ed.) RelMiCS\/AKA 2006. LNCS, vol.\u00a04136, pp. 192\u2013206. Springer, Heidelberg (2006)"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.laa.2006.10.004","volume":"421","author":"P. Butkovi\u010d","year":"2007","unstructured":"Butkovi\u010d, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max cones. Linear Algebra Appl.\u00a0421, 394\u2013406 (2007)","journal-title":"Linear Algebra Appl."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.laa.2006.09.019","volume":"421","author":"S. Gaubert","year":"2006","unstructured":"Gaubert, S., Katz, R.: The Minkowski theorem for max-plus convex sets. Linear Algebra and Appl.\u00a0421, 356\u2013369 (2006)","journal-title":"Linear Algebra and Appl."},{"key":"13_CR19","volume-title":"POPL 1977","author":"P. Cousot","year":"1977","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL 1977, Los Angeles, California. ACM Press, New York (1977)"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11823230_2","volume-title":"Static Analysis","author":"S. Sankaranarayanan","year":"2006","unstructured":"Sankaranarayanan, S., Ivancic, F., Shlyakhter, I., Gupta, A.: Static analysis in disjunctive numerical domains. In: Yi, K. (ed.) SAS 2006. LNCS, vol.\u00a04134, pp. 3\u201317. Springer, Heidelberg (2006)"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"Programming Languages and Systems - ESOP \u201996","author":"R. Giacobazzi","year":"1996","unstructured":"Giacobazzi, R., Ranzato, F.: Compositional Optimization of Disjunctive Abstract Interpretations. In: Riis Nielson, H. (ed.) ESOP 1996. LNCS, vol.\u00a01058, Springer, Heidelberg (1996)"},{"key":"13_CR22","series-title":"ENTCS","volume-title":"QAPL 2006","author":"P. Sotin","year":"2006","unstructured":"Sotin, P., Cachera, D., Jensen, T.: Quantitative static analysis over semirings: analysing cache behaviour for java card. In: QAPL 2006. ENTCS, vol.\u00a01380, Elsevier, Amsterdam (2006)"},{"issue":"2","key":"13_CR23","first-page":"203","volume":"20","author":"P. Butkovi\u010d","year":"1984","unstructured":"Butkovi\u010d, P., Heged\u00fcs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonomicko-matematicky Obzor.\u00a020(2), 203\u2013215 (1984)","journal-title":"Ekonomicko-matematicky Obzor."},{"issue":"6","key":"13_CR24","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/0041-5553(68)90115-8","volume":"8","author":"N.V. Chernikova","year":"1968","unstructured":"Chernikova, N.V.: Algorithm for discovering the set of all solutions of a linear programming problem. U.S.S.R. Computational Mathematics and Mathematical Physics\u00a08(6), 282\u2013293 (1968)","journal-title":"U.S.S.R. Computational Mathematics and Mathematical Physics"},{"key":"13_CR25","unstructured":"Le Verge, H.: A note on Chernikova\u2019s algorithm (1992)"},{"key":"13_CR26","unstructured":"Gaubert, S., Katz, R.: External and internal representation of max-plus polyhedra. Privately circuled draft (2008)"},{"key":"13_CR27","volume-title":"Synchronization and Linearity","author":"F. Baccelli","year":"1992","unstructured":"Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.P.: Synchronization and Linearity. Wiley, Chichester (1992)"},{"key":"13_CR28","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.P.: Regular matrices in max-plus algebra (preprint, 2008)"},{"key":"13_CR29","unstructured":"Halbwachs, N.: D\u00e9termination Automatique de Relations Lin\u00e9aires V\u00e9rifi\u00e9es par les Variables d\u2019un Programme. Th\u00e8se de 3eme cycle d\u2019informatique, Universit\u00e9 scientifique et m\u00e9dicale de Grenoble, Grenoble, France (March 1979)"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Halbwachs, N., Proy, Y., Roumanoff, P.: Verification of real-time systems using linear relation analysis. Formal Methods in System Design\u00a011(2) (August 1997)","DOI":"10.1023\/A:1008678014487"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11609773_23","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"A. Min\u00e9","year":"2005","unstructured":"Min\u00e9, A.: Symbolic methods to enhance the precision of numerical abstract domains. In: Emerson, E.A., Namjoshi, K.S. (eds.) VMCAI 2006. LNCS, vol.\u00a03855, pp. 348\u2013363. Springer, Heidelberg (2005)"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Gopan, D., Reps, T., Sagiv, M.: A framework for numeric analysis of array operations. SIGPLAN Not.\u00a040(1) (2005)","DOI":"10.1145\/1047659.1040333"},{"key":"13_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-540-78739-6_14","volume-title":"ESOP 2008","author":"X. Allamigeon","year":"2008","unstructured":"Allamigeon, X.: Non-disjunctive Numerical Domain for Array Predicate Abstraction. In: Drossopoulou, S. (ed.) ESOP 2008. LNCS, vol.\u00a04960, pp. 163\u2013177. Springer, Heidelberg (2008)"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Batcher, K.: Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference 32, pp. 307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"13_CR35","series-title":"Lecture Notes in Computer Science","volume-title":"VMCAI 2008","author":"Y. Moy","year":"2008","unstructured":"Moy, Y.: Sufficient preconditions for modular assertion checking. In: Logozzo, F., Peled, D.A., Zuck, L.D. (eds.) VMCAI 2008. LNCS, vol.\u00a04905. Springer, Heidelberg (2008)"},{"issue":"S\u00e9rie I","key":"13_CR36","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0764-4442(97)82710-3","volume":"326","author":"S. Gaubert","year":"1998","unstructured":"Gaubert, S., Gunawardena, J.: The duality theorem for min-max functions. C. R. Acad. Sci. Paris.\u00a0326 (S\u00e9rie I), 43\u201348 (1998)","journal-title":"C. R. Acad. Sci. Paris."},{"key":"13_CR37","series-title":"Lecture Notes in Computer Science","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"S. Sankaranarayanan","year":"2005","unstructured":"Sankaranarayanan, S., Sipma, H., Manna, Z.: Scalable analysis of linear systems using mathematical programming. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol.\u00a03385, Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Static Analysis"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69166-2_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T05:06:43Z","timestamp":1684472803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69166-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540691631","9783540691662"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69166-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}