{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:10Z","timestamp":1763467990341},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157684"},{"type":"electronic","value":"9783642157691"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15769-1_8","type":"book-chapter","created":{"date-parts":[[2010,9,13]],"date-time":"2010-09-13T06:09:40Z","timestamp":1284358180000},"page":"117-133","source":"Crossref","is-referenced-by-count":85,"title":["Multi-dimensional Rankings, Program Termination, and Complexity Bounds of Flowchart Programs"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Alias","sequence":"first","affiliation":[]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Feautrier","sequence":"additional","affiliation":[]},{"given":"Laure","family":"Gonnord","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","unstructured":"Alias, C., Darte, A., Feautrier, P., Gonnord, L.: Bounding the computational complexity of flowchart programs with multi-dimensional rankings. Research Report 7235, INRIA (March 2010)"},{"key":"8_CR2","unstructured":"Alias, C., Darte, A., Feautrier, P., Gonnord, L., Quinson, C.: Program termination and worst-time complexity with multi-dimensional affine ranking functions. Research Report 7037, INRIA (November 2009)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-540-40018-9_9","volume-title":"Programming Languages and Systems","author":"H. Anderson","year":"2003","unstructured":"Anderson, H., Khoo, S.C.: Affine-based size-change termination. In: Ohori, A. (ed.) APLAS 2003. LNCS, vol.\u00a02895, pp. 122\u2013140. Springer, Heidelberg (2003)"},{"issue":"3","key":"8_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1353445.1353450","volume":"30","author":"A.M. Ben-Amram","year":"2008","unstructured":"Ben-Amram, A.M.: Size-change termination with difference constraints. ACM Transactions on Programming Languages and Systems (TOPLAS)\u00a030(3), 1\u201331 (2008)","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-02658-4_12","volume-title":"Computer Aided Verification","author":"A.M. Ben-Amram","year":"2009","unstructured":"Ben-Amram, A.M.: Size change termination, monotonicity constraints, and ranking functions. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol.\u00a05643, pp. 109\u2013123. Springer, Heidelberg (2009)"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/371282.371285","volume":"2","author":"A. Blass","year":"2001","unstructured":"Blass, A., Gurevich, Y.: Inadequacy of computable loop invariants. ACM Transactions on Computational Logic (TOCL)\u00a02(1), 1\u201311 (2001)","journal-title":"ACM Transactions on Computational Logic (TOCL)"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1007\/11523468_109","volume-title":"Automata, Languages and Programming","author":"A.A. Bradley","year":"2005","unstructured":"Bradley, A.A., Manna, Z., Sipma, H.B.: The polyranking principle. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1349\u20131361. Springer, Heidelberg (2005)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/11513988_48","volume-title":"Computer Aided Verification","author":"A.R. Bradley","year":"2005","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Linear ranking with reachability. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol.\u00a03576, pp. 491\u2013504. Springer, Heidelberg (2005)"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-540-78739-6_13","volume-title":"Programming Languages and Systems","author":"A. Chawdhary","year":"2008","unstructured":"Chawdhary, A., Cook, B., Gulwani, S., Sagiv, M., Yang, H.: Ranking abstractions. In: Drossopoulou, S. (ed.) ESOP 2008. LNCS, vol.\u00a04960, pp. 81\u201392. Springer, Heidelberg (2008)"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1145\/237578.237617","volume-title":"International Conference on Supercomputing (ICS 1996)","author":"P. Clauss","year":"1996","unstructured":"Clauss, P.: Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: Applications to analyze and transform scientific programs. In: International Conference on Supercomputing (ICS 1996), pp. 278\u2013285. ACM, New York (1996)"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BFb0002746","volume-title":"Euro-Par \u201997 Parallel Processing","author":"P. Clauss","year":"1997","unstructured":"Clauss, P.: Handling memory cache policy with integer points counting. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds.) Euro-Par 1997. LNCS, vol.\u00a01300, pp. 285\u2013293. Springer, Heidelberg (1997)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-45319-9_6","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M. Col\u00f3n","year":"2001","unstructured":"Col\u00f3n, M., Sipma, H.: Synthesis of linear ranking functions. In: Margaria, T., Yi, W. (eds.) TACAS 2001. LNCS, vol.\u00a02031, pp. 67\u201381. Springer, Heidelberg (2001)"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/3-540-45657-0_36","volume-title":"Computer Aided Verification","author":"M.A. Col\u00f3n","year":"2002","unstructured":"Col\u00f3n, M.A., Sipma, H.B.: Practical methods for proving program termination. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol.\u00a02404, pp. 442\u2013454. Springer, Heidelberg (2002)"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: 5th ACM Symposium on Principles of Programming Languages (POPL 1978), pp. 84\u201396. Tucson (January 1978)","DOI":"10.1145\/512760.512770"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/b105073","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"P. Cousot","year":"2005","unstructured":"Cousot, P.: Proving program invariance and termination by parametric abstraction, Lagrangian relaxation, and semidefinite programming. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol.\u00a03385, pp. 1\u201324. Springer, Heidelberg (2005)"},{"issue":"2","key":"8_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1142\/S0129626491000021","volume":"1","author":"A. Darte","year":"1991","unstructured":"Darte, A., Khachiyan, L., Robert, Y.: Linear scheduling is nearly optimal. Parallel Processing Letters\u00a01(2), 73\u201381 (1991)","journal-title":"Parallel Processing Letters"},{"key":"8_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1362-8","volume-title":"Scheduling and Automatic Parallelization","author":"A. Darte","year":"2000","unstructured":"Darte, A., Robert, Y., Vivien, F.: Scheduling and Automatic Parallelization. Birkhauser, Basel (2000) ISBN 0-8176-4149-1"},{"issue":"6","key":"8_CR18","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1023\/A:1025168022993","volume":"25","author":"A. Darte","year":"1997","unstructured":"Darte, A., Vivien, F.: Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs. International Journal of Parallel Programming\u00a025(6), 447\u2013496 (1997)","journal-title":"International Journal of Parallel Programming"},{"issue":"6","key":"8_CR19","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01379404","volume":"21","author":"P. Feautrier","year":"1992","unstructured":"Feautrier, P.: Some efficient solutions to the affine scheduling problem, part II, multi-dimensional time. International Journal of Parallel Programming\u00a021(6), 389\u2013420 (1992)","journal-title":"International Journal of Parallel Programming"},{"key":"8_CR20","first-page":"19","volume-title":"Symposium on Applied Mathematics","author":"R.W. Floyd","year":"1967","unstructured":"Floyd, R.W.: Assigning meaning to programs. In: Schwartz, J.T. (ed.) Symposium on Applied Mathematics, vol.\u00a019, pp. 19\u201332. A.M.S, Providence (1967)"},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11823230_10","volume-title":"Static Analysis","author":"L. Gonnord","year":"2006","unstructured":"Gonnord, L., Halbwachs, N.: Combining widening and acceleration in linear relation analysis. In: Yi, K. (ed.) SAS 2006. LNCS, vol.\u00a04134, pp. 144\u2013160. Springer, Heidelberg (2006)"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/3-540-53982-4_10","volume-title":"TAPSOFT \u201991. Proceedings of the International Joint Conference on Theory and Practice of Software Development, Brighton, UK, April 8-12, 1991","author":"P. Granger","year":"1991","unstructured":"Granger, P.: Static analysis of linear congruence equalities among variables of a program. In: Abramsky, S. (ed.) TAPSOFT 1991.LNCS, vol.\u00a0494, pp. 169\u2013192. Springer, Heidelberg (1991)"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1145\/1542476.1542518","volume-title":"ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2009)","author":"S. Gulwani","year":"2009","unstructured":"Gulwani, S., Jain, S., Koskinen, E.: Control-flow refinement and progress invariants for bound analysis. In: ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2009), pp. 375\u2013385. ACM, Dublin (2009)"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.: SPEED: Precise and efficient static estimation of program computational complexity. In: 36th ACM Symposium on Principles of Programming Languages (POPL 2009), pp. 127\u2013139. Savannah (January 2009)","DOI":"10.1145\/1594834.1480898"},{"issue":"3","key":"8_CR25","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"R.M. Karp","year":"1967","unstructured":"Karp, R.M., Miller, R.E., Winograd, S.: The organization of computations for uniform recurrence equations. Journal of the ACM\u00a014(3), 563\u2013590 (1967)","journal-title":"Journal of the ACM"},{"issue":"3","key":"8_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/373243.360210","volume":"36","author":"C.S. Lee","year":"2001","unstructured":"Lee, C.S., Jones, N.D., Ben-Amram, A.M.: The size-change principle for program termination. ACM SIGPLAN Notices\u00a036(3), 81\u201392 (2001)","journal-title":"ACM SIGPLAN Notices"},{"key":"8_CR27","volume-title":"Mathematical Theory of Computing","author":"Z. Manna","year":"1974","unstructured":"Manna, Z.: Mathematical Theory of Computing. McGraw-Hill, New York (1974)"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-24622-0_20","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"A. Podelski","year":"2004","unstructured":"Podelski, A., Rybalchenko, A.: In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol.\u00a02937, pp. 239\u2013251. Springer, Heidelberg (2004)"},{"key":"8_CR29","first-page":"32","volume-title":"IEEE Symposium on Logic in Computer Science (LICS 2004)","author":"A. Podelski","year":"2004","unstructured":"Podelski, A., Rybalchenko, A.: Transition invariants. In: Ganzinger, H. (ed.) IEEE Symposium on Logic in Computer Science (LICS 2004), pp. 32\u201341. IEEE Computer Society, Los Alamitos (July 2004)"},{"key":"8_CR30","volume-title":"Theory of linear and integer programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley, NewYork (1986)"},{"issue":"1","key":"8_CR31","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00453-006-1231-0","volume":"48","author":"S. Verdoolaege","year":"2007","unstructured":"Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M.: Counting integer points in parametric polytopes using Barvinok\u2019s rational functions. Algorithmica\u00a048(1), 37\u201366 (2007)","journal-title":"Algorithmica"},{"issue":"11-12","key":"8_CR32","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1002\/cpe.780","volume":"15","author":"F. Vivien","year":"2003","unstructured":"Vivien, F.: On the optimality of Feautrier\u2019s scheduling algorithm. Concurrency and Computation: Practice and Experience\u00a015(11-12), 1047\u20131068 (2003); Euro-Par\u201902 Special Issue","journal-title":"Concurrency and Computation: Practice and Experience"},{"issue":"3","key":"8_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1347375.1347389","volume":"7","author":"R. Wilhelm","year":"2008","unstructured":"Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., Stenstr\u00f6m, P.: The determination of worst-case execution times\u2014overview of the methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS)\u00a07(3), 1\u201353 (2008)","journal-title":"ACM Transactions on Embedded Computing Systems (TECS)"}],"container-title":["Lecture Notes in Computer Science","Static Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15769-1_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:17:36Z","timestamp":1619785056000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15769-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157684","9783642157691"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15769-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}