{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T02:46:34Z","timestamp":1777949194339,"version":"3.51.4"},"publisher-location":"Singapore","reference-count":40,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819578252","type":"print"},{"value":"9789819578269","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-7826-9_15","type":"book-chapter","created":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T22:11:57Z","timestamp":1777846317000},"page":"277-295","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms for\u00a0Partial Constraint Satisfaction Problems over\u00a0Control-Flow Graphs"],"prefix":"10.1007","author":[{"given":"Xuran","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir Kafshdar","family":"Goharshady","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"15_CR1","unstructured":"Ahmadi, A., Chatterjee, K., Goharshady, A.K., Meggendorfer, T., Safavi, R., Zikelic, \u0110.: Algorithms and hardness results for computing cores of markov chains. In: FSTTCS, pp. 29:1\u201329:20 (2022)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadi, A., Daliri, M., Goharshady, A.K., Pavlogiannis, A.: Efficient approximations for cache-conscious data placement. In: PLDI, pp. 857\u2013871 (2022)","DOI":"10.1145\/3519939.3523436"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-030-59152-6_14","volume-title":"Automated Technology for Verification and Analysis","author":"A Asadi","year":"2020","unstructured":"Asadi, A., Chatterjee, K., Goharshady, A.K., Mohammadi, K., Pavlogiannis, A.: Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. In: Hung, D.V., Sokolsky, O. (eds.) ATVA 2020. LNCS, vol. 12302, pp. 253\u2013270. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59152-6_14"},{"key":"15_CR4","unstructured":"Bodlaender, H.L., Gustedt, J., Telle, J.A.: Linear-time register allocation for a fixed number of registers. In: SODA, pp. 574\u2013583 (1998)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Burgstaller, B., Blieberger, J., Scholz, B.: On the tree width of ada programs. In: Ada-Europe, pp. 78\u201390 (2004)","DOI":"10.1007\/978-3-540-24841-5_6"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Cai, X., Goharshady, A.: Faster lifetime-optimal speculative partial redundancy elimination for goto-free programs. In: SETTA, pp. 382\u2013398. Springer (2024)","DOI":"10.1007\/978-981-96-0602-3_21"},{"key":"15_CR7","doi-asserted-by":"publisher","unstructured":"Cai, X., Goharshady, A.K., Hitarth, S., Lam, C.K.: Faster chaitin-like register allocation via grammatical decompositions of control-flow graphs. In: ASPLOS, pp. 463\u2013477. ACM (2025). https:\/\/doi.org\/10.1145\/3669940.3707286","DOI":"10.1145\/3669940.3707286"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Goharshady, E.K.: The treewidth of smart contracts. In: SAC, pp. 400\u2013408. ACM (2019)","DOI":"10.1145\/3297280.3297322"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Goyal, P., Ibsen-Jensen, R., Pavlogiannis, A.: Faster algorithms for dynamic algebraic queries in basic rsms with constant treewidth. ACM Trans. Program. Lang. Syst. 41(4), 23:1\u201323:46 (2019)","DOI":"10.1145\/3363525"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Ibsen-Jensen, R., Pavlogiannis, A.: Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In: POPL, pp. 733\u2013747 (2016)","DOI":"10.1145\/2837614.2837624"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Ibsen-Jensen, R., Pavlogiannis, A.: Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: ESOP, pp. 112\u2013140 (2020)","DOI":"10.1007\/978-3-030-44914-8_5"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Okati, N., Pavlogiannis, A.: Efficient parameterized algorithms for data packing. Proc. ACM Program. Lang. 3(POPL), 53:1\u201353:28 (2019)","DOI":"10.1145\/3290366"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-319-68167-2_4","volume-title":"Automated Technology for Verification and Analysis","author":"K Chatterjee","year":"2017","unstructured":"Chatterjee, K., Goharshady, A.K., Pavlogiannis, A.: JTDec: a tool for tree decompositions in soot. In: D\u2019Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 59\u201366. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68167-2_4"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A.K., Pavlogiannis, A.: Algorithms for algebraic path properties in concurrent systems of constant treewidth components. ACM Trans. Program. Lang. Syst. 40(3), 9:1\u20139:43 (2018)","DOI":"10.1145\/3210257"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Lacki, J.: Faster algorithms for markov decision processes with low treewidth. In: CAV, pp. 543\u2013558 (2013)","DOI":"10.1007\/978-3-642-39799-8_36"},{"issue":"OOPSLA2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1145\/3622868","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado, G.K., Goharshady, A.K., Kochekov, K., Tsai, Y.C., Zaher, A.K.: Exploiting the sparseness of control-flow and call graphs for efficient and on-demand algebraic program analysis. Proc. ACM Program. Lang. 7(OOPSLA2), 1993\u20132022 (2023)","journal-title":"Proc. ACM Program. Lang."},{"issue":"OOPSLA2","key":"15_CR17","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1145\/3622807","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado, G.K., Goharshady, A.K., Lam, C.K.: The bounded pathwidth of control-flow graphs. Proc. ACM Program. Lang. 7(OOPSLA2), 292\u2013317 (2023)","journal-title":"Proc. ACM Program. Lang."},{"issue":"1","key":"15_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R Dechter","year":"1987","unstructured":"Dechter, R., Pearl, J.: Network-based heuristics for constraint-satisfaction problems. Artif. Intell. 34(1), 1\u201338 (1987). https:\/\/doi.org\/10.1016\/0004-3702(87)90002-6","journal-title":"Artif. Intell."},{"key":"15_CR19","unstructured":"Dechter, R., Pearl, J.: Tree-clustering schemes for constraint-processing. In: AAAI, pp. 150\u2013154 (1988)"},{"key":"15_CR20","unstructured":"Dutta, S.: Anatomy of a compiler: a retargetable ansi-c compiler. Circuit Cellar 121(5) (2000)"},{"key":"15_CR21","unstructured":"Dutta, S., Drotos, D., Vigor, K., et al.: Small device c compiler (2003), http:\/\/sdcc.sourceforge.net\/"},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/11591191_34","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"A Ferrara","year":"2005","unstructured":"Ferrara, A., Pan, G., Vardi, M.Y.: Treewidth in verification: local vs. global. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol. 3835, pp. 489\u2013503. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11591191_34"},{"key":"15_CR23","unstructured":"for Formal Models, I., Verification: Kissat-public (2025), https:\/\/fmv.jku.at\/kissat\/"},{"key":"15_CR24","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: AAAI, pp. 4\u20139 (1990)"},{"key":"15_CR25","doi-asserted-by":"publisher","unstructured":"Freuder, E.C., Wallacex, R.J.: Partial constraint satisfaction 58, 21\u201370 (1992). https:\/\/doi.org\/10.1016\/0004-3702(92)90004-H","DOI":"10.1016\/0004-3702(92)90004-H"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Goharshady, A.K., Lam, C.K., Parreaux, L.: Fast and optimal extraction for sparse equality graphs. In: OOPSLA (2024)","DOI":"10.1145\/3689801"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Goharshady, A.K., Zaher, A.K.: Efficient interprocedural data-flow analysis using treedepth and treewidth. In: VMCAI, vol. 13881, pp. 177\u2013202 (2023)","DOI":"10.1007\/978-3-031-24950-1_9"},{"key":"15_CR28","unstructured":"Gurobi Optimization, L.: Gurobi (2008), https:\/\/www.gurobi.com\/"},{"key":"15_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/3-540-45643-0_7","volume-title":"Algorithm Engineering and Experiments","author":"J Gustedt","year":"2002","unstructured":"Gustedt, J., M\u00e6hle, O.A., Telle, J.A.: The treewidth of java programs. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 86\u201397. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45643-0_7"},{"key":"15_CR30","doi-asserted-by":"publisher","unstructured":"Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree-decomposition 40, 170\u2013180 (2002). https:\/\/doi.org\/10.1002\/net.10046","DOI":"10.1002\/net.10046"},{"issue":"3","key":"15_CR31","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0167-6377(98)00043-1","volume":"23","author":"AM Koster","year":"1998","unstructured":"Koster, A.M., Hoesel, S.P., Kolen, A.W.: The partial constraint satisfaction problem: facets and lifting theorems. Oper. Res. Lett. 23(3), 89\u201397 (1998). https:\/\/doi.org\/10.1016\/S0167-6377(98)00043-1","journal-title":"Oper. Res. Lett."},{"key":"15_CR32","doi-asserted-by":"publisher","unstructured":"Krause, P.K.: Optimal placement of bank selection instructions in polynomial time (2013). https:\/\/doi.org\/10.1145\/2463596.2463598","DOI":"10.1145\/2463596.2463598"},{"key":"15_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-37051-9_1","volume-title":"Compiler Construction","author":"PK Krause","year":"2013","unstructured":"Krause, P.K.: Optimal register allocation in polynomial time. In: Jhala, R., De Bosschere, K. (eds.) CC 2013. LNCS, vol. 7791, pp. 1\u201320. Springer, Heidelberg (2013b). https:\/\/doi.org\/10.1007\/978-3-642-37051-9_1"},{"key":"15_CR34","doi-asserted-by":"publisher","unstructured":"Liu, T., Xue, C.J., Li, M.: Joint variable partitioning and bank selection instruction optimization for partitioned memory architectures. ACM Trans. Embed. Comput. Syst. 12 (2013). https:\/\/doi.org\/10.1145\/2442116.2442126","DOI":"10.1145\/2442116.2442126"},{"key":"15_CR35","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"AK Mackworth","year":"1985","unstructured":"Mackworth, A.K., Freuder, E.C.: The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artif. Intell. 25, 65\u201374 (1985). https:\/\/doi.org\/10.1016\/0004-3702(85)90041-4","journal-title":"Artif. Intell."},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"Obdrz\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: CAV, pp. 80\u201392 (2003)","DOI":"10.1007\/978-3-540-45069-6_7"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S.: Reachability analysis using message passing over tree decompositions. In: CAV, pp. 604\u2013628 (2020)","DOI":"10.1007\/978-3-030-53288-8_30"},{"key":"15_CR38","doi-asserted-by":"publisher","unstructured":"Scholz, B., Burgstaller, B., Xue, J.: Minimizing bank selection instructions for partitioned memory architecture. In: CASES, pp. 201\u2013211. ACM (2006). https:\/\/doi.org\/10.1145\/1176760.1176786","DOI":"10.1145\/1176760.1176786"},{"key":"15_CR39","doi-asserted-by":"publisher","unstructured":"Scholz, B., Burgstaller, B., Xue, J.: Minimal placement of bank selection instructions for partitioned memory architectures. ACM Trans. Embed. Comput. Syst. 7 (2008). https:\/\/doi.org\/10.1145\/1331331.1331336","DOI":"10.1145\/1331331.1331336"},{"key":"15_CR40","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree width and good register allocation. Inf. Comput. 142, 159\u2013181 (1998). https:\/\/doi.org\/10.1006\/inco.1997.2697","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Dependable Software Engineering. Theories, Tools, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7826-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T22:11:59Z","timestamp":1777846319000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7826-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819578252","9789819578269"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7826-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SETTA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Dependable Software Engineering: Theories, Tools, and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Oxford","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"setta2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.setta2025.uk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}