{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:12:12Z","timestamp":1770279132083,"version":"3.49.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,1,4]]},"abstract":"<jats:p>\n            Pointer analysis is one of the fundamental problems in static program analysis. Given a set of pointers, the task is to produce a useful over-approximation of the memory locations that each pointer may point-to at runtime. The most common formulation is Andersen\u2019s Pointer Analysis (APA), defined as an inclusion-based set of\n            <jats:italic>m<\/jats:italic>\n            pointer constraints over a set of\n            <jats:italic>n<\/jats:italic>\n            pointers. Scalability is extremely important, as points-to information is a prerequisite to many other components in the static-analysis pipeline. Existing algorithms solve APA in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u00b7\n            <jats:italic>m<\/jats:italic>\n            ) time, while it has been conjectured that the problem has no truly sub-cubic algorithm, with a proof so far having remained elusive. It is also well-known that APA can be solved in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time under certain sparsity conditions that hold naturally in some settings. Besides these simple bounds, the complexity of the problem has remained poorly understood.\n          <\/jats:p>\n          <jats:p>\n            In this work we draw a rich fine-grained and parallel complexity landscape of APA, and present upper and lower bounds. First, we establish an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) upper-bound for general APA, improving over\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u00b7\n            <jats:italic>m<\/jats:italic>\n            ) as\n            <jats:italic>n<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ). Second, we show that even on-demand APA (\u201cmay a specific pointer\n            <jats:italic>a<\/jats:italic>\n            point to a specific location\n            <jats:italic>b<\/jats:italic>\n            ?\u201d) has an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) (combinatorial) lower bound under standard complexity-theoretic hypotheses. This formally establishes the long-conjectured \u201ccubic bottleneck\u201d of APA, and shows that our\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            )-time algorithm is optimal. Third, we show that under mild restrictions, APA is solvable in \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c9<\/jats:sup>\n            ) time, where \u03c9&lt;2.373 is the matrix-multiplication exponent. It is believed that \u03c9=2+\n            <jats:italic>o<\/jats:italic>\n            (1), in which case this bound becomes quadratic. Fourth, we show that even under such restrictions, even the on-demand problem has an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) lower bound under standard complexity-theoretic hypotheses, and hence our algorithm is optimal when \u03c9=2+\n            <jats:italic>o<\/jats:italic>\n            (1). Fifth, we study the parallelizability of APA and establish lower and upper bounds: (i) in general, the problem is P-complete and hence unlikely parallelizable, whereas (ii) under mild restrictions, the problem is parallelizable. Our theoretical treatment formalizes several insights that can lead to practical improvements in the future.\n          <\/jats:p>","DOI":"10.1145\/3434315","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T17:34:24Z","timestamp":1609781664000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["The fine-grained and parallel complexity of andersen\u2019s pointer analysis"],"prefix":"10.1145","volume":"5","author":[{"given":"Anders Alnor","family":"Mathiasen","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-0722","authenticated-orcid":false,"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2003. T. J. Watson Libraries for Analysis (WALA). https:\/\/github.com. ( 2003 ).  2003. T. J. Watson Libraries for Analysis (WALA). https:\/\/github.com. ( 2003 )."},{"key":"e_1_2_1_2_1","first-page":"434","article-title":"Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud and Virginia Vassilevska Williams . 2014 . Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems . In FOCS. 434 - 443 . Amir Abboud and Virginia Vassilevska Williams. 2014. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS. 434-443.","journal-title":"FOCS."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1388"},{"key":"e_1_2_1_6_1","volume-title":"Regularity Lemmas and Combinatorial Algorithms. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 745-754","author":"Bansal N.","unstructured":"N. Bansal and R. Williams . 2009 . Regularity Lemmas and Combinatorial Algorithms. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 745-754 . N. Bansal and R. Williams. 2009. Regularity Lemmas and Combinatorial Algorithms. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 745-754."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780822.781144"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23702-7_9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302516.3307352"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Ninth National Conference on Artificial Intelligence-Volume 2 ( AAAI ' 91 ). AAAI Press, 738-743","author":"Boddy Mark","year":"1991","unstructured":"Mark Boddy . 1991 . Anytime Problem Solving Using Dynamic Programming . In Proceedings of the Ninth National Conference on Artificial Intelligence-Volume 2 ( AAAI ' 91 ). AAAI Press, 738-743 . Mark Boddy. 1991. Anytime Problem Solving Using Dynamic Programming. In Proceedings of the Ninth National Conference on Artificial Intelligence-Volume 2 ( AAAI ' 91 ). AAAI Press, 738-743."},{"key":"e_1_2_1_11_1","volume-title":"Eficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability. ( 2018 ). arXiv:cs.DS\/","author":"Bradford Phillip G.","year":"1802","unstructured":"Phillip G. Bradford . 2018. Eficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability. ( 2018 ). arXiv:cs.DS\/ 1802 .05239 Phillip G. Bradford. 2018. Eficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability. ( 2018 ). arXiv:cs.DS\/ 1802.05239"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604142"},{"key":"e_1_2_1_13_1","volume-title":"Proc. ACM Program. Lang. 2, POPL, Article Article 30 (Dec. 2018 ), 30 pages.","author":"Chatterjee Krishnendu","year":"2018","unstructured":"Krishnendu Chatterjee , Bhavya Choudhary , and Andreas Pavlogiannis . 2018 . Optimal Dyck Reachability for DataDependence and Alias Analysis . Proc. ACM Program. Lang. 2, POPL, Article Article 30 (Dec. 2018 ), 30 pages. Krishnendu Chatterjee, Bhavya Choudhary, and Andreas Pavlogiannis. 2018. Optimal Dyck Reachability for DataDependence and Alias Analysis. Proc. ACM Program. Lang. 2, POPL, Article Article 30 (Dec. 2018 ), 30 pages."},{"key":"e_1_2_1_14_1","volume-title":"41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Chatterjee Krishnendu","unstructured":"Krishnendu Chatterjee , Wolfgang Dvor\u00e1k , Monika Henzinger , and Veronika Loitzenbauer . 2016. Conditionally Optimal Algorithms for Generalized B\u00fcchi Games . In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ) (Leibniz International Proceedings in Informatics (LIPIcs)) , Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), Vol. 58 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 25 : 1-25 : 15. Krishnendu Chatterjee, Wolfgang Dvor\u00e1k, Monika Henzinger, and Veronika Loitzenbauer. 2016. Conditionally Optimal Algorithms for Generalized B\u00fcchi Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ) (Leibniz International Proceedings in Informatics (LIPIcs)), Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), Vol. 58. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 25 : 1-25 : 15."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2676968"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349309"},{"key":"e_1_2_1_17_1","volume-title":"Estimating the Impact of Scalable Pointer Analysis on Optimization","author":"Das Manuvir","unstructured":"Manuvir Das , Ben Liblit , Manuel F\u00e4hndrich , and Jakob Rehof . 2001. Estimating the Impact of Scalable Pointer Analysis on Optimization . In Static Analysis, Patrick Cousot (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg , 260-278. Manuvir Das, Ben Liblit, Manuel F\u00e4hndrich, and Jakob Rehof. 2001. Estimating the Impact of Scalable Pointer Analysis on Optimization. In Static Analysis, Patrick Cousot (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 260-278."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2007.371239"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90158-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814307"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/277652.277667"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/381694.378806"},{"key":"e_1_2_1_23_1","volume-title":"Ruzzo","author":"Greenlaw Raymond","year":"1995","unstructured":"Raymond Greenlaw , H. James Hoover , and Walter L . Ruzzo . 1995 . Limits to Parallel Computation : P-Completeness Theory. Oxford University Press , Inc., USA. Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. 1995. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Inc., USA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250767"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190025.2190075"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/788019.788876"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378802"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378855"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_2_1_31_1","first-page":"96","volume-title":"Pointer Analysis in the Presence of Dynamic Class Loading. In ECOOP 2004-Object-Oriented Programming, Martin Odersky (Ed.). Springer Berlin Heidelberg","author":"Hirzel Martin","year":"2004","unstructured":"Martin Hirzel , Amer Diwan , and Michael Hind . 2004 . Pointer Analysis in the Presence of Dynamic Class Loading. In ECOOP 2004-Object-Oriented Programming, Martin Odersky (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg , 96 - 122 . Martin Hirzel, Amer Diwan, and Michael Hind. 2004. Pointer Analysis in the Presence of Dynamic Class Loading. In ECOOP 2004-Object-Oriented Programming, Martin Odersky (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 96-122."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239913"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '16)","author":"Huang Jianyu","unstructured":"Jianyu Huang , Tyler M. Smith , Greg M. Henry , and Robert A . van de Geijn. 2016. Strassen's Algorithm Reloaded . In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '16) . IEEE Press, Article Article 59, 12 pages. Jianyu Huang, Tyler M. Smith, Greg M. Henry, and Robert A. van de Geijn. 2016. Strassen's Algorithm Reloaded. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '16). IEEE Press, Article Article 59, 12 pages."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/369028.369096"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529282.1529711"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Igor Kaporin. 1999. A practical algorithm for faster matrix multiplication. Numerical Linear Algebra with Applications 6 8 ( 1999 ) 687-700.  Igor Kaporin. 1999. A practical algorithm for faster matrix multiplication. Numerical Linear Algebra with Applications 6 8 ( 1999 ) 687-700.","DOI":"10.1002\/(SICI)1099-1506(199912)6:8<687::AID-NLA177>3.0.CO;2-I"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996867"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90393-O"},{"key":"e_1_2_1_39_1","volume-title":"Ryder","author":"Landi William","year":"1991","unstructured":"William Landi and Barbara G . Ryder . 1991 . Pointer-induced Aliasing : A Problem Classification. In POPL. ACM. William Landi and Barbara G. Ryder. 1991. Pointer-induced Aliasing: A Problem Classification. In POPL. ACM."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765948"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293606"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_4"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2936313.2816712"},{"key":"e_1_2_1_45_1","volume-title":"The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis. ( 2020 ). arXiv:cs.PL\/","author":"Mathiasen Anders Alnor","year":"2006","unstructured":"Anders Alnor Mathiasen and Andreas Pavlogiannis . 2020. The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis. ( 2020 ). arXiv:cs.PL\/ 2006 .01491 Anders Alnor Mathiasen and Andreas Pavlogiannis. 2020. The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis. ( 2020 ). arXiv:cs.PL\/ 2006.01491"},{"key":"e_1_2_1_46_1","volume-title":"On the Complexity Analysis of Static Analyses","author":"McAllester David","unstructured":"David McAllester . 1999. On the Complexity Analysis of Static Analyses . In Static Analysis, Agostino Cortesi and Gilberto Fil\u00e9 (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 312-329. David McAllester. 1999. On the Complexity Analysis of Static Analyses. In Static Analysis, Agostino Cortesi and Gilberto Fil\u00e9 (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 312-329."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00049-9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145831"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869495"},{"key":"e_1_2_1_50_1","volume-title":"Schwartzbach","author":"M\u00f8ller Anders","year":"2018","unstructured":"Anders M\u00f8ller and Michael I . Schwartzbach . 2018 . Static Program Analysis. Technical Report. Department of Computer Science, Aarhus University . http:\/\/cs.au.dk\/~amoeller\/spa\/ Anders M\u00f8ller and Michael I. Schwartzbach. 2018. Static Program Analysis. Technical Report. Department of Computer Science, Aarhus University. http:\/\/cs.au.dk\/~amoeller\/spa\/"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90006-8"},{"key":"e_1_2_1_52_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou . 1993. Computational Complexity . Addison-Wesley . Christos H. Papadimitriou. 1993. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SQJO.0000039791.93071.a2"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2614628.2614632"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03036473"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349310"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263703"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_1_60_1","first-page":"205","volume-title":"Proceedings of the 16th International Symposium on Static Analysis (SAS '09)","author":"Sridharan Manu","unstructured":"Manu Sridharan and Stephen J. Fink . 2009. The Complexity of Andersen's Analysis in Practice . In Proceedings of the 16th International Symposium on Static Analysis (SAS '09) . Springer-Verlag, Berlin, Heidelberg , 205 - 221 . Manu Sridharan and Stephen J. Fink. 2009. The Complexity of Andersen's Analysis in Practice. In Proceedings of the 16th International Symposium on Static Analysis (SAS '09). Springer-Verlag, Berlin, Heidelberg, 205-221."},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Manu Sridharan Denis Gopan Lexin Shan and Rastislav Bod\u00edk. 2005. Demand-driven Points-to Analysis for Java. In OOPSLA.  Manu Sridharan Denis Gopan Lexin Shan and Rastislav Bod\u00edk. 2005. Demand-driven Points-to Analysis for Java. In OOPSLA.","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"Volker Strassen. 1969. Gaussian Elimination is Not Optimal. Numer. Math. 13 4 ( 1969 ) 354-356.  Volker Strassen. 1969. Gaussian Elimination is Not Optimal. Numer. Math. 13 4 ( 1969 ) 354-356.","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2014.54"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325706"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950296"},{"key":"e_1_2_1_67_1","volume-title":"CASCON '99","author":"Vall\u00e9e-Rai Raja","year":"1999","unstructured":"Raja Vall\u00e9e-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , and Vijay Sundaresan . 1999 . Soot-a Java bytecode optimization framework . In CASCON '99 . IBM Press. Raja Vall\u00e9e-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. 1999. Soot-a Java bytecode optimization framework. In CASCON '99. IBM Press."},{"key":"e_1_2_1_68_1","volume-title":"Batch Alias Analysis. In 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 936-948","author":"Vedurada J.","unstructured":"J. Vedurada and V. K. Nandivada . 2019 . Batch Alias Analysis. In 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 936-948 . J. Vedurada and V. K. Nandivada. 2019. Batch Alias Analysis. In 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 936-948."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037744"},{"key":"e_1_2_1_70_1","volume-title":"Lam","author":"Whaley John","year":"2002","unstructured":"John Whaley and Monica S . Lam . 2002 . An Eficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages. In Static Analysis, Manuel V. Hermenegildo and Germ\u00e1n Puebla (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg, 180-195. John Whaley and Monica S. Lam. 2002. An Eficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages. In Static Analysis, Manuel V. Hermenegildo and Germ\u00e1n Puebla (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 180-195."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_2_1_75_1","volume-title":"Conditional Lower Bound for Inclusion-Based Points-to Analysis. arXiv preprint arXiv","author":"Zhang Qirun","year":"2007","unstructured":"Qirun Zhang . 2020. Conditional Lower Bound for Inclusion-Based Points-to Analysis. arXiv preprint arXiv : 2007 . 05569 ( 2020 ). Qirun Zhang. 2020. Conditional Lower Bound for Inclusion-Based Points-to Analysis. arXiv preprint arXiv: 2007. 05569 ( 2020 )."},{"key":"e_1_2_1_76_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast Algorithms for Dyck-CFL-reachability with Applications to Alias Analysis (PLDI). ACM.  Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast Algorithms for Dyck-CFL-reachability with Applications to Alias Analysis (PLDI). ACM.","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328464"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:35Z","timestamp":1750195475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":73,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434315"],"URL":"https:\/\/doi.org\/10.1145\/3434315","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}