{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T07:48:35Z","timestamp":1744271315263},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T00:00:00Z","timestamp":1476403200000},"content-version":"unspecified","delay-in-days":43,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Pointer analysis is a fundamental static program analysis for computing the set of objects that an expression can refer to. Decades of research has gone into developing methods of varying precision and efficiency for pointer analysis for programs that use different language features, but determining precisely how efficient a particular method is has been a challenge in itself.<\/jats:p><jats:p>For programs that use different language features, we consider methods for pointer analysis using Datalog and extensions to Datalog. When the rules are in Datalog, we present the calculation of precise time complexities from the rules using a new algorithm for decomposing rules for obtaining the best complexities. When extensions such as function symbols and universal quantification are used, we describe algorithms for efficiently implementing the extensions and the complexities of the algorithms.<\/jats:p>","DOI":"10.1017\/s1471068416000405","type":"journal-article","created":{"date-parts":[[2016,10,15]],"date-time":"2016-10-15T21:28:20Z","timestamp":1476566900000},"page":"916-932","source":"Crossref","is-referenced-by-count":2,"title":["Precise complexity guarantees for pointer analysis via Datalog with extensions"],"prefix":"10.1017","volume":"16","author":[{"given":"K. TUNCAY","family":"TEKLE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YANHONG A.","family":"LIU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"S1471068416000405_ref33","doi-asserted-by":"crossref","unstructured":"Tekle K. T. and Liu Y. A. 2011. More efficient Datalog queries: Subsumptive tabling beats magic sets. In Proc. of the 2011 ACM SIGMOD Intl. Conf. on Management of Data, 661\u2013672.","DOI":"10.1145\/1989323.1989393"},{"key":"S1471068416000405_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/271510.271517"},{"key":"S1471068416000405_ref5","doi-asserted-by":"crossref","unstructured":"Ghiya R. and Hendren L. J. 1998. Putting pointer analysis to work. In Proc. of the 25th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, 121\u2013133.","DOI":"10.1145\/268946.268957"},{"key":"S1471068416000405_ref16","doi-asserted-by":"crossref","unstructured":"Liu Y. A. , Stoller S. D. , Lin B. and Gorbovitski M. 2012. From clarity to efficiency for distributed algorithms. In Proc. of the 27th ACM SIGPLAN Conf. on Object-Oriented Programming, Systems, Languages and Applications, 395\u2013410.","DOI":"10.1145\/2384616.2384645"},{"key":"S1471068416000405_ref36","doi-asserted-by":"crossref","unstructured":"Zheng X. and Rugina R. 2008. Demand-driven alias analysis for C. In Proc. of the 35th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, 197\u2013208.","DOI":"10.1145\/1328438.1328464"},{"key":"S1471068416000405_ref26","unstructured":"Shivers O. G. 1991. Control-flow analysis of higher-order languages of taming lambda. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, USA."},{"key":"S1471068416000405_ref34","doi-asserted-by":"crossref","unstructured":"Tekle K. T. and Liu Y. A. 2016. Precise Complexity Guarantees for Pointer Analysis via Datalog with Extensions. ArXiv e-prints.","DOI":"10.1017\/S1471068416000405"},{"key":"S1471068416000405_ref29","doi-asserted-by":"crossref","unstructured":"Sridharan M. and Fink S. J. 2009. The complexity of Andersen's analysis in practice. In Proc. of the 16th Intl. Symp. on Static Analysis, 205\u2013221.","DOI":"10.1007\/978-3-642-03237-0_15"},{"key":"S1471068416000405_ref27","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"S1471068416000405_ref1","unstructured":"Andersen L. O. 1994. Program analysis and specialization for the c programming language. Ph.D. thesis, DIKU, University of Copenhagen, Copenhagen, Denmark."},{"key":"S1471068416000405_ref6","doi-asserted-by":"crossref","unstructured":"Ghiya R. , Lavery D. M. and Sehr D. C. 2001. On the importance of points-to analysis and other memory disambiguation methods for C programs. In Proc. of the 2001 ACM SIGPLAN Conf. on Programming Language Design and Implementation, 47\u201358.","DOI":"10.1145\/378795.378806"},{"key":"S1471068416000405_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050040"},{"key":"S1471068416000405_ref28","doi-asserted-by":"crossref","unstructured":"Smaragdakis Y. , Bravenboer M. and Lhot\u00e1k O. 2011. Pick your contexts well: Understanding object-sensitivity. In Proc. of the 38th Symp. on Principles of Programming Languages, 17\u201330.","DOI":"10.1145\/1926385.1926390"},{"key":"S1471068416000405_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"S1471068416000405_ref7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1869631.1869635","volume-title":"Proceedings of the 6th Symposium on Dynamic Languages","author":"Gorbovitski","year":"2010"},{"key":"S1471068416000405_ref35","doi-asserted-by":"crossref","unstructured":"Wilson R. P. and Lam M. S. 1995. Efficient context-sensitive pointer analysis for C programs. In Proc. of the ACM SIGPLAN'95 Conf. on Programming Language Design and Implementation, 1\u201312.","DOI":"10.1145\/207110.207111"},{"key":"S1471068416000405_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"S1471068416000405_ref32","doi-asserted-by":"crossref","unstructured":"Tekle K. T. and Liu Y. A. 2010. Precise complexity analysis for efficient Datalog queries. In Proc. of the 12th Intl. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming, 35\u201344.","DOI":"10.1145\/1836089.1836094"},{"key":"S1471068416000405_ref2","unstructured":"Avots D. , Dalton M. , Livshits V. B. and Lam M. S. 2005. Improving software security with a C pointer analysis. In Prof. of the 27th Intl. Conf. on Software Engineering, 332\u2013341."},{"key":"S1471068416000405_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1552309.1552311"},{"key":"S1471068416000405_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83952-8"},{"key":"S1471068416000405_ref11","doi-asserted-by":"crossref","unstructured":"Hind M. 2001. Pointer analysis: Haven't we solved this problem yet? In Proc. of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering, 54\u201361.","DOI":"10.1145\/379605.379665"},{"key":"S1471068416000405_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"S1471068416000405_ref13","doi-asserted-by":"crossref","unstructured":"Hind M. and Pioli A. 2000. Which pointer analysis should I use? In Proc. of the 2000 ACM SIGSOFT Intl. Symp. on Software Testing and Analysis, 113\u2013123.","DOI":"10.1145\/347324.348916"},{"key":"S1471068416000405_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-005-7005-6"},{"key":"S1471068416000405_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"S1471068416000405_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90027-2"},{"key":"S1471068416000405_ref23","doi-asserted-by":"crossref","unstructured":"Selinger P. G. , Astrahan M. M. , Chamberlin D. D. , Lorie R. A. and Price T. G. 1979. Access path selection in a relational database management system. In Proc. of the 1979 ACM SIGMOD Intl. Conf. on Management of Data, 23\u201334.","DOI":"10.1145\/582095.582099"},{"key":"S1471068416000405_ref24","doi-asserted-by":"crossref","unstructured":"Shapiro M. and Horwitz S. 1997. The effects of the precision of pointer analysis. In Proc. of the 4th Intl. Symp. on Static Analysis, 16\u201334.","DOI":"10.1007\/BFb0032731"},{"key":"S1471068416000405_ref25","unstructured":"Sharir M. and Pnueli A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications. Prentice-Hall, Chapter 7, 189\u2013233."},{"key":"S1471068416000405_ref30","doi-asserted-by":"crossref","unstructured":"Steensgaard B. 1996. Points-to analysis in almost linear time. In Conf. Record of the 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, 32\u201341.","DOI":"10.1145\/237721.237727"},{"key":"S1471068416000405_ref4","doi-asserted-by":"crossref","unstructured":"Diwan A. , McKinley K. S. and Moss J. E. B. 1998. Type-based alias analysis. In Proc. of the ACM SIGPLAN Conf. on Programming Language Design and Implementation, 106\u2013117.","DOI":"10.1145\/277650.277670"},{"key":"S1471068416000405_ref21","doi-asserted-by":"crossref","unstructured":"Saha D. and Ramakrishnan C. R. 2005. Incremental and demand-driven points-to analysis using logic programming. In Proc. of the 7th Intl. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming, 117\u2013128.","DOI":"10.1145\/1069774.1069785"},{"key":"S1471068416000405_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/161494.161501"},{"key":"S1471068416000405_ref9","unstructured":"Hardekopf B. and Lin C. 2007. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. In Proc. of the ACM SIGPLAN 2007 Conf. on Programming Language Design and Implementation, 290\u2013299."},{"key":"S1471068416000405_ref10","doi-asserted-by":"crossref","unstructured":"Heintze N. and Tardieu O. 2001. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proc. of the 2001 ACM SIGPLAN Conf. on Programming Language Design and Implementation, 254\u2013263.","DOI":"10.1145\/378795.378855"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068416000405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T17:04:34Z","timestamp":1568480674000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068416000405\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":36,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S1471068416000405"],"URL":"https:\/\/doi.org\/10.1017\/s1471068416000405","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}