{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:15:33Z","timestamp":1775873733191,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031442445","type":"print"},{"value":"9783031442452","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-44245-2_12","type":"book-chapter","created":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T15:02:30Z","timestamp":1698073350000},"page":"231-258","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Mutual Refinements of\u00a0Context-Free Language Reachability"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0843-0729","authenticated-orcid":false,"given":"Shuo","family":"Ding","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5367-9377","authenticated-orcid":false,"given":"Qirun","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,24]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Choudhary, B., Pavlogiannis, A.: Optimal dyck reachability for data-dependence and alias analysis. Proc. ACM Program. Lang. 2(POPL), 30:1\u201330:30 (2018)","DOI":"10.1145\/3158118"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: Subcubic algorithms for recursive state machines. In: Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, 7\u201312 January 2008, pp. 159\u2013169. ACM (2008)","DOI":"10.1145\/1328438.1328460"},{"key":"12_CR3","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2022)"},{"key":"12_CR4","unstructured":"Cousot, P.: Asychronous iterative methods for solving a fixed point system of monotone equations in a complete lattice (1977)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"F\u00e4hndrich, M., Foster, J.S., Su, Z., Aiken, A.: Partial online cycle elimination in inclusion constraint graphs. In: Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI), Montreal, Canada, 17\u201319 June 1998, pp. 85\u201396. ACM (1998)","DOI":"10.1145\/277650.277667"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Fink, S.J., Yahav, E., Dor, N., Ramalingam, G., Geay, E.: Effective typestate verification in the presence of aliasing. ACM Trans. Softw. Eng. Methodol. 17(2), 9:1\u20139:34 (2008)","DOI":"10.1145\/1348250.1348255"},{"issue":"3","key":"12_CR7","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/5666.5673","volume":"29","author":"PJ Fleming","year":"1986","unstructured":"Fleming, P.J., Wallace, J.J.: How not to lie with statistics: the correct way to summarize benchmark results. Commun. ACM 29(3), 218\u2013221 (1986)","journal-title":"Commun. ACM"},{"key":"12_CR8","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley Longman Publishing Co., Inc. (1978)"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/568438.568455","volume":"32","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60\u201365 (2001)","journal-title":"ACM SIGACT News"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Huang, W., Dong, Y., Milanova, A., Dolby, J.: Scalable and precise taint analysis for android. In: Proceedings of the 2015 International Symposium on Software Testing and Analysis, ISSTA 2015, pp. 106\u2013117. ACM (2015)","DOI":"10.1145\/2771783.2771803"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Kahlon, V.: Boundedness vs. unboundedness of lock chains: characterizing decidability of pairwise CFL-reachability for threads communicating via locks. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11\u201314 August 2009, Los Angeles, CA, USA, pp. 27\u201336. IEEE Computer Society (2009)","DOI":"10.1109\/LICS.2009.45"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Kildall, G.A.: A unified approach to global program optimization. In: Conference Record of the ACM Symposium on Principles of Programming Languages, Boston, Massachusetts, USA, October 1973, pp. 194\u2013206. ACM Press (1973)","DOI":"10.1145\/512927.512945"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Kjelstr\u00f8m, A.H., Pavlogiannis, A.: The decidability and complexity of interleaved bidirected dyck reachability. Proc. ACM Program. Lang. 6(POPL), 1\u201326 (2022)","DOI":"10.1145\/3498673"},{"key":"12_CR14","unstructured":"Kleene, S.C.: Introduction to metamathematics (1952)"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Kodumal, J., Aiken, A.: The set constraint\/CFL reachability connection in practice. In: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation 2004, Washington, DC, USA, 9\u201311 June 2004, pp. 207\u2013218. ACM (2004)","DOI":"10.1145\/996841.996867"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Lattner, C., Adve, V.S.: LLVM: a compilation framework for lifelong program analysis & transformation. In: 2nd IEEE\/ACM International Symposium on Code Generation and Optimization (CGO 2004), 20\u201324 March 2004, San Jose, CA, USA, pp. 75\u201388. IEEE Computer Society (2004)","DOI":"10.1109\/CGO.2004.1281665"},{"issue":"OOPSLA2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1556","DOI":"10.1145\/3563343","volume":"6","author":"Y Lei","year":"2022","unstructured":"Lei, Y., Sui, Y., Ding, S., Zhang, Q.: Taming transitive redundancy for context-free language reachability. Proc. ACM Program. Lang. 6(OOPSLA2), 1556\u20131582 (2022)","journal-title":"Proc. ACM Program. Lang."},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Li, Y., Zhang, Q., Reps, T.W.: Fast graph simplification for interleaved dyck-reachability. In: Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, pp. 780\u2013793. ACM (2020)","DOI":"10.1145\/3385412.3386021"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-37051-9_4","volume-title":"Compiler Construction","author":"Y Lu","year":"2013","unstructured":"Lu, Y., Shang, L., Xie, X., Xue, J.: An incremental points-to analysis with CFL-reachability. In: Jhala, R., De Bosschere, K. (eds.) CC 2013. LNCS, vol. 7791, pp. 61\u201381. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-37051-9_4"},{"issue":"1\u20132","key":"12_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0304-3975(00)00049-9","volume":"248","author":"D Melski","year":"2000","unstructured":"Melski, D., Reps, T.W.: Interconvertibility of a class of set constraints and context-free-language reachability. Theor. Comput. Sci. 248(1\u20132), 29\u201398 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Milanova, A.: Flowcfl: generalized type-based reachability analysis: graph reduction and equivalence of CFL-based and type-based reachability. Proc. ACM Program. Lang. 4(OOPSLA), 178:1\u2013178:29 (2020)","DOI":"10.1145\/3428246"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/11823230_7","volume-title":"Static Analysis","author":"P Pratikakis","year":"2006","unstructured":"Pratikakis, P., Foster, J.S., Hicks, M.: Existential label flow inference via CFL reachability. In: Yi, K. (ed.) SAS 2006. LNCS, vol. 4134, pp. 88\u2013106. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11823230_7"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Rehof, J., F\u00e4hndrich, M.: Type-base flow analysis: from polymorphic subtyping to CFL-reachability. In: Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, London, UK, 17\u201319 January 2001, pp. 54\u201366. ACM (2001)","DOI":"10.1145\/360204.360208"},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1145\/345099.345137","volume":"22","author":"T Reps","year":"2000","unstructured":"Reps, T.: Undecidability of context-sensitive data-dependence analysis. ACM Trans. Program. Lang. Syst. (TOPLAS) 22(1), 162\u2013186 (2000)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"issue":"11\u201312","key":"12_CR25","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"TW Reps","year":"1998","unstructured":"Reps, T.W.: Program analysis via graph reachability. Inf. Softw. Technol. 40(11\u201312), 701\u2013726 (1998)","journal-title":"Inf. Softw. Technol."},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Reps, T.W., Horwitz, S., Sagiv, S.: Precise interprocedural dataflow analysis via graph reachability. In: Conference Record of POPL 1995: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, USA, 23\u201325 January 1995, pp. 49\u201361. ACM Press (1995)","DOI":"10.1145\/199448.199462"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Sp\u00e4th, J., Ali, K., Bodden, E.: Context-, flow-, and field-sensitive data-flow analysis using synchronized pushdown systems. Proc. ACM Program. Lang. 3(POPL), 48:1\u201348:29 (2019)","DOI":"10.1145\/3290361"},{"key":"12_CR28","unstructured":"SPEC: SPEC CPU 2017 (2017). https:\/\/www.spec.org\/cpu2017\/. Accessed 6 Nov 2022"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Sridharan, M., Bod\u00edk, R.: Refinement-based context-sensitive points-to analysis for java. In: Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, Ottawa, Ontario, Canada, 11\u201314 June 2006, pp. 387\u2013400. ACM (2006)","DOI":"10.1145\/1133255.1134027"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Su, Y., Ye, D., Xue, J.: Parallel pointer analysis with CFL-reachability. In: 43rd International Conference on Parallel Processing, ICPP 2014, Minneapolis, MN, USA, 9\u201312 September 2014, pp. 451\u2013460. IEEE Computer Society (2014)","DOI":"10.1109\/ICPP.2014.54"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Sui, Y., Xue, J.: SVF: interprocedural static value-flow analysis in LLVM. In: Proceedings of the 25th International Conference on Compiler Construction, pp. 265\u2013266. ACM (2016)","DOI":"10.1145\/2892208.2892235"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Tan, T., Li, Y., Ma, X., Xu, C., Smaragdakis, Y.: Making pointer analysis more precise by unleashing the power of selective context sensitivity. Proc. ACM Program. Lang. 5(OOPSLA), 1\u201327 (2021)","DOI":"10.1145\/3485524"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Xiao, X., Zhang, Q., Zhou, J., Zhang, C.: Persistent pointer information. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2014, Edinburgh, United Kingdom - 09\u201311 June 2014, pp. 463\u2013474. ACM (2014)","DOI":"10.1145\/2666356.2594314"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Yan, D., Xu, G., Rountev, A.: Demand-driven context-sensitive alias analysis for java. In: Proceedings of the 20th International Symposium on Software Testing and Analysis, ISSTA 2011, Toronto, ON, Canada, 17\u201321 July 2011, pp. 155\u2013165. ACM (2011)","DOI":"10.1145\/2001420.2001440"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1990, pp. 230\u2013242. ACM Press (1990)","DOI":"10.1145\/298514.298576"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Lyu, M.R., Yuan, H., Su, Z.: Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013, Seattle, WA, USA, 16\u201319 June 2013, pp. 435\u2013446. ACM (2013)","DOI":"10.1145\/2499370.2462159"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Su, Z.: Context-sensitive data-dependence analysis via linear conjunctive language reachability. In: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pp. 344\u2013358. ACM (2017)","DOI":"10.1145\/3009837.3009848"}],"container-title":["Lecture Notes in Computer Science","Static Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-44245-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T17:20:01Z","timestamp":1730395201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-44245-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031442445","9783031442452"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-44245-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"24 October 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Static Analysis Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sas2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/sas-2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}