{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T13:18:54Z","timestamp":1770297534379,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540297352","type":"print"},{"value":"9783540322474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11575467_8","type":"book-chapter","created":{"date-parts":[[2005,11,11]],"date-time":"2005-11-11T08:58:51Z","timestamp":1131699531000},"page":"97-118","source":"Crossref","is-referenced-by-count":125,"title":["Using Datalog with Binary Decision Diagrams for Program Analysis"],"prefix":"10.1007","author":[{"given":"John","family":"Whaley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dzintars","family":"Avots","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monica S.","family":"Lam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","volume-title":"ICSE 2005: Proceedings of the 27th International Conference on Software Engineering","author":"D. Avots","year":"2005","unstructured":"Avots, D., Dalton, M., Livshits, V.B., Lam, M.S.: Improving software security with a C pointer analysis. In: ICSE 2005: Proceedings of the 27th International Conference on Software Engineering. ACM Press, New York (2005)"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/10722468_7","volume-title":"Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification","author":"T. Ball","year":"2000","unstructured":"Ball, T., Rajamani, S.K.: Bebop: A symbolic model checker for boolean programs. In: Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, pp. 113\u2013130. Springer, Heidelberg (2000)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-45139-0_7","volume-title":"Model Checking Software","author":"T. Ball","year":"2001","unstructured":"Ball, T., Rajamani, S.K.: Automatically validating temporal safety properties of interfaces. In: Dwyer, M.B. (ed.) SPIN 2001. LNCS, vol.\u00a02057, pp. 103\u2013122. Springer, Heidelberg (2001)"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/6012.15399","volume-title":"PODS 1986: Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems","author":"F. Bancilhon","year":"1986","unstructured":"Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs (extended abstract). In: PODS 1986: Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 1\u201315. ACM Press, New York (1986)"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/781131.781144","volume-title":"PLDI 2003: Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation","author":"M. Berndl","year":"2003","unstructured":"Berndl, M., Lhot\u00e1k, O., Qian, F., Hendren, L., Umanee, N.: Points-to analysis using BDDs. In: PLDI 2003: Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pp. 103\u2013114. ACM Press, New York (2003)"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-44898-5_2","volume-title":"Static Analysis","author":"F. Besson","year":"2003","unstructured":"Besson, F., Jensen, T.: Modular class analysis with datalog. In: Cousot, R. (ed.) SAS 2003. LNCS, vol.\u00a02694, pp. 19\u201336. Springer, Heidelberg (2003), \n                      \n                        http:\/\/www.irisa.fr\/lande\/fbesson\/fbesson.html"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Beyer, D., Noack, A., Lewerentz, C.: Simple and efficient relational querying of software structures. In: Proceedings of the 10th IEEE Working Conference on Reverse Engineering (November 2003)","DOI":"10.1109\/WCRE.2003.1287252"},{"issue":"8","key":"8_CR8","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R.E. Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers\u00a035(8), 677\u2013691 (1986)","journal-title":"IEEE Transactions on Computers"},{"key":"8_CR9","unstructured":"Carbin, M., Whaley, J., Lam, M.S.: Finding effective variable orderings for BDD-based program analysis (2005) (To be submitted for publication)"},{"key":"8_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83952-8","volume-title":"Logic programming and databases","author":"S. Ceri","year":"1990","unstructured":"Ceri, S., Gottlob, G., Tanca, L.: Logic programming and databases. Springer, New York (1990)"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0743-1066(85)90002-0","volume":"2","author":"A. Chandra","year":"1985","unstructured":"Chandra, A., Harel, D.: Horn clauses and generalizations. Journal of Logic Programming\u00a02(1), 1\u201315 (1985)","journal-title":"Journal of Logic Programming"},{"issue":"1","key":"8_CR12","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/227595.227597","volume":"43","author":"W. Chen","year":"1996","unstructured":"Chen, W., Warren, D.S.: Tabled evaluation with delaying for general logic programs. J. ACM\u00a043(1), 20\u201374 (1996)","journal-title":"J. ACM"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/3-540-57186-8_72","volume-title":"Programming Language Implementation and Logic Programming","author":"M.-M. Corsini","year":"1993","unstructured":"Corsini, M.-M., Musumbu, K., Rauzy, A., Charlier, B.L.: Efficient bottom-up abstract interpretation of prolog by means of constraint solving over symbolic finite domains. In: Penjam, J., Bruynooghe, M. (eds.) PLILP 1993. LNCS, vol.\u00a0714, pp. 75\u201391. Springer, Heidelberg (1993)"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/231379.231399","volume-title":"PLDI 1996: Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation","author":"S. Dawson","year":"1996","unstructured":"Dawson, S., Ramakrishnan, C.R., Warren, D.S.: Practical program analysis using general purpose logic programming systemsa case study. In: PLDI 1996: Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, pp. 117\u2013126. ACM Press, New York (1996)"},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/116825.116838","volume":"38","author":"A.V. Gelder","year":"1991","unstructured":"Gelder, A.V., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. J. ACM\u00a038(3), 619\u2013649 (1991)","journal-title":"J. ACM"},{"issue":"5","key":"8_CR16","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/502102.502104","volume":"48","author":"A.Y. Halevy","year":"2001","unstructured":"Halevy, A.Y., Mumick, I.S., Sagiv, Y., Shmueli, O.: Static analysis in datalog extensions. J. ACM\u00a048(5), 971\u20131012 (2001)","journal-title":"J. ACM"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1109\/ICDE.1995.380367","volume-title":"ICDE 1995: Proceedings of the Eleventh International Conference on Data Engineering","author":"M. Iwaihara","year":"1995","unstructured":"Iwaihara, M., Inoue, Y.: Bottom-up evaluation of logic programs using binary decision diagrams. In: ICDE 1995: Proceedings of the Eleventh International Conference on Data Engineering, pp. 467\u2013474. IEEE Computer Society, Los Alamitos (1995)"},{"key":"8_CR18","volume-title":"Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"M.S. Lam","year":"2005","unstructured":"Lam, M.S., Whaley, J., Livshits, V.B., Martin, M.C., Avots, D., Carbin, M., Unkel, C.: Context-sensitive program analysis as database queries. In: Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2005. ACM, New York (2005)"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1145\/996841.996861","volume-title":"PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation","author":"O. Lhot\u00e1k","year":"2004","unstructured":"Lhot\u00e1k, O., Hendren, L.: Jedd: a BDD-based relational extension of Java. In: PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 158\u2013169. ACM Press, New York (2004)"},{"key":"8_CR20","unstructured":"Lind-Nielsen, J.: BuDDy, a binary decision diagram package, \n                      \n                        http:\/\/buddy.sourceforge.net"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/888251.888268","volume-title":"PPDP 2003: Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming","author":"Y.A. Liu","year":"2003","unstructured":"Liu, Y.A., Stoller, S.D.: From datalog rules to efficient programs with time and space guarantees. In: PPDP 2003: Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pp. 172\u2013183. ACM Press, New York (2003)"},{"key":"8_CR22","unstructured":"Livshits, V.B., Lam, M.S.: Finding security vulnerabilities in java applications with static analysis. In: 14th USENIX Security Symposium, August 2005. USENIX (2005)"},{"key":"8_CR23","unstructured":"Martin, M.C., Livshits, V.B., Lam, M.S.: Finding application errors using PQL: a program query language. In: Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) (October 2005)"},{"key":"8_CR24","unstructured":"Naughton, J.F., Ramakrishnan, R.: Bottom-up evaluation of logic programs. In: Computational Logic - Essays in Honor of Alan Robinson, pp. 640\u2013700 (1991)"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1145\/67544.66948","volume-title":"SIGMOD 1989: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data","author":"J.F. Naughton","year":"1989","unstructured":"Naughton, J.F., Ramakrishnan, R., Sagiv, Y., Ullman, J.D.: Efficient evaluation of right-, left-, and multi-linear rules. In: SIGMOD 1989: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pp. 235\u2013242. ACM Press, New York (1989)"},{"key":"8_CR26","first-page":"359","volume-title":"Proceedings of the 16th International Conference on Very Large Data Bases","author":"R. Ramakrishnan","year":"1990","unstructured":"Ramakrishnan, R., Srivastava, D., Sudarshan, S.: Rule ordering in bottom-up fixpoint evaluation of logic programs. In: Proceedings of the 16th International Conference on Very Large Data Bases, pp. 359\u2013371. Morgan Kaufmann Publishers Inc., San Francisco (1990)"},{"issue":"2","key":"8_CR27","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0743-1066(94)00039-9","volume":"23","author":"R. Ramakrishnan","year":"1993","unstructured":"Ramakrishnan, R., Ullman, J.D.: A survey of research on deductive database systems. J. Logic Programming\u00a023(2), 125\u2013149 (1993)","journal-title":"J. Logic Programming"},{"issue":"2","key":"8_CR28","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1145\/316686.316687","volume":"21","author":"G. Ramalingam","year":"1999","unstructured":"Ramalingam, G.: Identifying loops in almost linear time. ACM Transactions on Programming Languages and Systems\u00a021(2), 175\u2013188 (1999)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"8_CR29","first-page":"163","volume-title":"Demand Interprocedural Program Analysis Using Logic Databases","author":"T.W. Reps","year":"1994","unstructured":"Reps, T.W.: Demand Interprocedural Program Analysis Using Logic Databases, pp. 163\u2013196. Kluwer, Dordrecht (1994)"},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1145\/28659.28696","volume-title":"PODS 1987: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"Y. Sagiv","year":"1987","unstructured":"Sagiv, Y.: Optimizing datalog programs. In: PODS 1987: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 349\u2013362. ACM Press, New York (1987)"},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1145\/191839.191927","volume-title":"SIGMOD 1994: Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data","author":"K. Sagonas","year":"1994","unstructured":"Sagonas, K., Swift, T., Warren, D.S.: Xsb as an efficient deductive database engine. In: SIGMOD 1994: Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, pp. 442\u2013453. ACM Press, New York (1994)"},{"key":"8_CR32","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/964001.964004","volume-title":"POPL 2004: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"G. Sittampalam","year":"2004","unstructured":"Sittampalam, G., de Moor, O., Larsen, K.F.: Incremental execution of transformation specifications. In: POPL 2004: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 26\u201338. ACM Press, New York (2004)"},{"key":"8_CR33","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/3-540-16492-8_66","volume-title":"Proceedings on Third International Conference on Logic Programming","author":"H. Tamaki","year":"1986","unstructured":"Tamaki, H., Sato, T.: Old resolution with tabulation. In: Proceedings on Third International Conference on Logic Programming, pp. 84\u201398. Springer, New York (1986)"},{"issue":"3","key":"8_CR34","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0022-0000(74)80049-8","volume":"9","author":"R.E. Tarjan","year":"1974","unstructured":"Tarjan, R.E.: Testing flow graph reducibility. Journal of Computer and System Sciences\u00a09(3), 355\u2013365 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR35","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1145\/73721.73736","volume-title":"PODS 1989: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"J.D. Ullman","year":"1989","unstructured":"Ullman, J.D.: Bottom-up beats top-down for datalog. In: PODS 1989: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 140\u2013149. ACM Press, New York (1989)"},{"key":"8_CR36","volume-title":"Principles of Database and Knowledge-Base Systems","author":"J.D. Ullman","year":"1989","unstructured":"Ullman, J.D.: Principles of Database and Knowledge-Base Systems, 2nd edn. Computer Science Press, Rockville (1989)","edition":"2"},{"key":"8_CR37","unstructured":"Whaley, J.: JavaBDD library, \n                      \n                        http:\/\/javabdd.sourceforge.net"},{"key":"8_CR38","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1145\/996841.996859","volume-title":"PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation","author":"J. Whaley","year":"2004","unstructured":"Whaley, J., Lam, M.S.: Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In: PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 131\u2013144. ACM Press, New York (2004)"},{"key":"8_CR39","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1145\/888251.888277","volume-title":"PPDP 2003: Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming","author":"N.-F. Zhou","year":"2003","unstructured":"Zhou, N.-F., Sato, T.: Efficient fixpoint computation in linear tabling. In: PPDP 2003: Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pp. 275\u2013283. ACM Press, New York (2003)"},{"key":"8_CR40","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1145\/774572.774594","volume-title":"ICCAD 2002: Proceedings of the 2002 IEEE\/ACM International Conference on Computer-Aided Design","author":"J. Zhu","year":"2002","unstructured":"Zhu, J.: Symbolic pointer analysis. In: ICCAD 2002: Proceedings of the 2002 IEEE\/ACM International Conference on Computer-Aided Design, pp. 150\u2013157. ACM Press, New York (2002)"},{"key":"8_CR41","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/996841.996860","volume-title":"PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation","author":"J. Zhu","year":"2004","unstructured":"Zhu, J., Calman, S.: Symbolic pointer analysis revisited. In: PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 145\u2013157. ACM Press, New York (2004)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11575467_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:42:28Z","timestamp":1619491348000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11575467_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540297352","9783540322474"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/11575467_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}