{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T08:28:21Z","timestamp":1791102501229,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642237010","type":"print"},{"value":"9783642237027","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23702-7_18","type":"book-chapter","created":{"date-parts":[[2011,9,9]],"date-time":"2011-09-09T17:31:31Z","timestamp":1315589491000},"page":"216-232","source":"Crossref","is-referenced-by-count":18,"title":["Transitive Closures of Affine Integer Tuple Relations and Their Overapproximations"],"prefix":"10.1007","author":[{"given":"Sven","family":"Verdoolaege","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna","family":"Beletska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.entcs.2010.09.002","volume":"267","author":"C. Ancourt","year":"2010","unstructured":"Ancourt, C., Coelho, F., Irigoin, F.: A modular static analysis approach to affine loop invariants detection. Electron. Notes Theor. Comput. Sci.\u00a0267, 3\u201316 (2010)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"5","key":"18_CR2","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10009-008-0064-3","volume":"10","author":"S. Bardin","year":"2008","unstructured":"Bardin, S., Finkel, A., Leroux, J., Petrucci, L.: Fast: acceleration from theory to practice. STTT\u00a010(5), 401\u2013424 (2008)","journal-title":"STTT"},{"issue":"3","key":"18_CR3","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/A:1007500431910","volume":"28","author":"D. Barthou","year":"2000","unstructured":"Barthou, D., Cohen, A., Collard, J.-F.: Maximal static expansion. Int. J. Parallel Programming\u00a028(3), 213\u2013243 (2000)","journal-title":"Int. J. Parallel Programming"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/3-540-45706-2_40","volume-title":"Euro-Par 2002. Parallel Processing","author":"D. Barthou","year":"2002","unstructured":"Barthou, D., Feautrier, P., Redon, X.: On the equivalence of two systems of affine recurrence equations. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol.\u00a02400, pp. 309\u2013313. Springer, Heidelberg (2002)"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1109\/PACT.2004.1342537","volume-title":"PACT 2004: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques","author":"C. Bastoul","year":"2004","unstructured":"Bastoul, C.: Code generation in the polyhedral model is easier than you think. In: PACT 2004: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pp. 7\u201316. IEEE Computer Society, Washington, DC, USA (2004)"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-02026-1_9","volume-title":"Combinatorial Optimization and Applications","author":"A. Beletska","year":"2009","unstructured":"Beletska, A., Barthou, D., Bielecki, W., Cohen, A.: Computing the transitive closure of a union of affine integer tuple relations. In: Du, D.-Z., Hu, X., Pardalos, P.M. (eds.) COCOA 2009. LNCS, vol.\u00a05573, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Beletska, A., Bielecki, W., Cohen, A., Palkowski, M., Siedlecki, K.: Coarse-grained loop parallelization: Iteration space slicing vs affine transformations. In: International Symposium on Parallel and Distributed Computing, 73\u201380 (2009)","DOI":"10.1109\/ISPDC.2009.15"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.endm.2009.03.002","volume":"33","author":"W. Bielecki","year":"2009","unstructured":"Bielecki, W., Klimek, T., Trifunovic, K.: Calculating exact transitive closure for a normalized affine integer tuple relation. Electronic Notes in Discrete Mathematics\u00a033, 7\u201314 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-17458-2_10","volume-title":"Combinatorial Optimization and Applications","author":"W. Bielecki","year":"2010","unstructured":"Bielecki, W., Klimek, T., Palkowski, M., Beletska, A.: An iterative algorithm of computing the transitive closure of a union of parameterized affine integer tuple relations. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part I. LNCS, vol.\u00a06508, pp. 104\u2013113. Springer, Heidelberg (2010)"},{"key":"18_CR10","unstructured":"Boigelot, B.: Symbolic Methods for Exploring Infinite State Spaces. Ph.D. thesis, Universit\u00e9 de Li\u00e8ge (1998)"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Boigelot, B., Wolper, P.: Symbolic verification with periodic sets. In: Proceedings of the 6th International Conference on Computer-Aided Verification. Lecture Notes in Computer Science, vol.\u00a0818, pp. 55\u201367. Springer, Heidelberg (1994)","DOI":"10.1007\/3-540-58179-0_43"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/11817963_40","volume-title":"Computer Aided Verification","author":"B. Boigelot","year":"2006","unstructured":"Boigelot, B., Herbreteau, F.: The power of hybrid acceleration. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol.\u00a04144, pp. 438\u2013451. Springer, Heidelberg (2006)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-00768-2_29","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M. Bozga","year":"2009","unstructured":"Bozga, M., G\u00eerlea, C., Iosif, R.: Iterating octagons. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol.\u00a05505, pp. 337\u2013351. Springer, Heidelberg (2009)"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-642-14295-6_23","volume-title":"Computer Aided Verification","author":"M. Bozga","year":"2010","unstructured":"Bozga, M., Iosif, R., Kone\u010dn\u00fd, F.: Fast acceleration of ultimately periodic relations. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol.\u00a06174, pp. 227\u2013242. Springer, Heidelberg (2010)"},{"issue":"4","key":"18_CR15","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/325478.325480","volume":"21","author":"T. Bultan","year":"1999","unstructured":"Bultan, T., Gerber, R., Pugh, W.: Model-checking concurrent systems with unbounded integer variables: symbolic representations, approximations, and experimental results. ACM Trans. Program. Lang. Syst.\u00a021(4), 747\u2013789 (1999)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"18_CR16","unstructured":"Chen, C.: Omega+ library (2009), http:\/\/www.chunchen.info\/omega\/"},{"issue":"2-3","key":"18_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1023\/A:1012996816178","volume":"14","author":"W.-N. Chin","year":"2001","unstructured":"Chin, W.N., Khoo, S.C.: Calculating sized types. Higher Order Symbol. Comput.\u00a014(2-3), 261\u2013300 (2001)","journal-title":"Higher Order Symbol. Comput."},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/BFb0028751","volume-title":"Computer Aided Verification","author":"H. Comon","year":"1998","unstructured":"Comon, H., Jurski, Y.: Multiple counters automata, safety analysis and presburger arithmetic. In: Vardi, M.Y. (ed.) CAV 1998. LNCS, vol.\u00a01427, pp. 268\u2013279. Springer, Heidelberg (1998)"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Darte, A., Robert, Y., Vivien, F.: Scheduling and Automatic Parallelization. Birkhauser, Boston (2000)","DOI":"10.1007\/978-1-4612-1362-8"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/11901914_36","volume-title":"Automated Technology for Verification and Analysis","author":"S. Demri","year":"2006","unstructured":"Demri, S., Finkel, A., Goranko, V., van Drimmelen, G.: Towards a model-checker for counter systems. In: Graf, S., Zhang, W. (eds.) ATVA 2006. LNCS, vol.\u00a04218, pp. 493\u2013507. Springer, Heidelberg (2006)"},{"issue":"3","key":"18_CR21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1051\/ro\/1988220302431","volume":"22","author":"P. Feautrier","year":"1988","unstructured":"Feautrier, P.: Parametric integer programming. Operationnelle\/Operations Research\u00a022(3), 243\u2013268 (1988)","journal-title":"Operationnelle\/Operations Research"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Feautrier, P.: Automatic Parallelization in the Polytope Model. In: Perrin, G.-R., Darte, A. (eds.) The Data Parallel Programming Model. LNCS, vol.\u00a01132, pp. 79\u2013100. Springer, Heidelberg (1996)","DOI":"10.1007\/3-540-61736-1_44"},{"key":"18_CR23","unstructured":"Feautrier, P., Griebl, M., Lengauer, C.: On index set splitting. In: Parallel Architectures and Compilation Techniques, PACT 1999, Newport Beach, CA (October 1999)"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.entcs.2010.09.014","volume":"267","author":"P. Feautrier","year":"2010","unstructured":"Feautrier, P., Gonnord, L.: Accelerated invariant generation for c programs with aspic and c2fsm. Electron. Notes Theor. Comput. Sci.\u00a0267, 3\u201313 (2010)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"18_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/BFb0014196","volume-title":"Languages and Compilers for Parallel Computing","author":"W. Kelly","year":"1996","unstructured":"Kelly, W., Pugh, W., Rosser, E., Shpeisman, T.: Transitive closure of infinite graphs and its applications. In: Huang, C.H., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D.A. (eds.) LCPC 1995. LNCS, vol.\u00a01033, pp. 126\u2013140. Springer, Heidelberg (1996)"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Lombardy, S., R\u00e9gis-Gianas, Y., Sakarovitch, J.: Introducing VAUCANSON. Theor. Comput. Sci.\u00a0328(1-2), 77\u201396 (2004)","DOI":"10.1016\/j.tcs.2004.07.007"},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/3-540-57659-2_31","volume-title":"Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing","author":"W. Pugh","year":"1994","unstructured":"Pugh, W., Wonnacott, D.: An exact method for analysis of value-based array data dependences. In: Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, pp. 546\u2013566. Springer, Heidelberg (1994)"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-27864-1_7","volume-title":"Static Analysis","author":"S. Sankaranarayanan","year":"2004","unstructured":"Sankaranarayanan, S., Sipma, H.B., Manna, Z.: Constraint-based linear-relations analysis. In: Giacobazzi, R. (ed.) SAS 2004. LNCS, vol.\u00a03148, pp. 53\u201368. Springer, Heidelberg (2004)"},{"key":"18_CR29","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, Chichester (1986)"},{"issue":"2","key":"18_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM Journal on Computing\u00a01(2), 146\u2013160 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/11817963_43","volume-title":"Computer Aided Verification","author":"A. Vardhan","year":"2006","unstructured":"Vardhan, A., Viswanathan, M.: LEVER: A tool for learning based verification. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol.\u00a04144, pp. 471\u2013474. Springer, Heidelberg (2006)"},{"key":"18_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-15582-6_49","volume-title":"Mathematical Software \u2013 ICMS 2010","author":"S. Verdoolaege","year":"2010","unstructured":"Verdoolaege, S.: isl: An integer set library for the polyhedral model. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol.\u00a06327, pp. 299\u2013302. Springer, Heidelberg (2010)"},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Verdoolaege, S., Cohen, A., Beletska, A.: Transitive closures of affine integer tuple relations and their overapproximations. Tech. Rep. RR-7560, INRIA (March 2011)","DOI":"10.1007\/978-3-642-23702-7_18"},{"key":"18_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/978-3-642-02658-4_44","volume-title":"Computer Aided Verification","author":"S. Verdoolaege","year":"2009","unstructured":"Verdoolaege, S., Janssens, G., Bruynooghe, M.: Equivalence checking of static affine programs using widening to handle recurrences. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol.\u00a05643, pp. 599\u2013613. Springer, Heidelberg (2009)"},{"key":"18_CR35","unstructured":"NAS benchmarks suite, http:\/\/www.nas.nasa.gov"}],"container-title":["Lecture Notes in Computer Science","Static Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23702-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,15]],"date-time":"2019-06-15T03:03:17Z","timestamp":1560567797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23702-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237010","9783642237027"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23702-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}