{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:09Z","timestamp":1750307829942,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>In this article we present Jedd, a language extension to Java that supports a convenient way of programming with Binary Decision Diagrams (BDDs). The Jedd language abstracts BDDs as database-style relations and operations on relations, and provides static type rules to ensure that relational operations are used correctly.<\/jats:p>\n          <jats:p>The article provides a description of the Jedd language and reports on the design and implementation of the Jedd translator and associated runtime system. Of particular interest is the approach to assigning attributes from the high-level relations to physical domains in the underlying BDDs, which is done by expressing the constraints as a SAT problem and using a modern SAT solver to compute the solution. Further, a runtime system is defined that handles memory management issues and supports a browsable profiling tool for tuning the key BDD operations.<\/jats:p>\n          <jats:p>The motivation for designing Jedd was to support the development of interrelated whole program analyses based on BDDs. We have successfully used Jedd to build Paddle, a framework of context-sensitive program analyses, including points-to analysis and call graph construction, as well as several client analyses.<\/jats:p>","DOI":"10.1145\/1377492.1377494","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Relations as an abstraction for BDD-based program analysis"],"prefix":"10.1145","volume":"30","author":[{"given":"Ond\u0159ej","family":"Lhot\u00e1k","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurie","family":"Hendren","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"volume-title":"Proceedings of the 4th USENIX Tcl\/Tk Workshop. 129--139","year":"1996","author":"Beazley D. M.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"Behrmann G. 2006. The interactive BDD environment. http:\/\/iben.sourceforge.net\/.  Behrmann G. 2006. The interactive BDD environment. http:\/\/iben.sourceforge.net\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646681.702465"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781144"},{"volume-title":"Proceedings of the 10th Working Conference on Reverse Engineering (WCRE'03)","author":"Beyer D.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.537122"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/514183.514184"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/945885.945890"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Clocksin W. F. and Mellish C. S. 1987. Programming in Prolog. Springer-Verlag Berlin Germany.   Clocksin W. F. and Mellish C. S. 1987. Programming in Prolog. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-642-97005-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349309"},{"volume-title":"Proceedings of the 16th IEEE International Conference on Automated Software Engineering (ASE'01)","author":"Fahmy H.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"volume-title":"Database Systems: The Complete Book","year":"2001","author":"Garcia-Molina H.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","unstructured":"Gosling J. Joy B. and Steele G. L. 1996. The Java Language Specification. The Java Series. Addison-Wesley Reading MA.   Gosling J. Joy B. and Steele G. L. 1996. The Java Language Specification. The Java Series. Addison-Wesley Reading MA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378855"},{"key":"e_1_2_1_18_1","unstructured":"Hipp D. R. 2006. SQLite: an embeddable database engine. http:\/\/www.sqlite.org\/.  Hipp D. R. 2006. SQLite: an embeddable database engine. http:\/\/www.sqlite.org\/."},{"key":"e_1_2_1_19_1","unstructured":"Lhot\u00e1k O. 2002. Spark: A flexible points-to analysis framework for Java. M.S. thesis McGill University.  Lhot\u00e1k O. 2002. Spark: A flexible points-to analysis framework for Java. M.S. thesis McGill University."},{"key":"e_1_2_1_20_1","unstructured":"Lhot\u00e1k O. 2006. Program analysis using binary decision diagrams. Ph.D. thesis McGill University.  Lhot\u00e1k O. 2006. Program analysis using binary decision diagrams. Ph.D. thesis McGill University."},{"volume":"2622","volume-title":"Proceedings of the 12th International Conference on Compiler Construction. G. Hedin, Ed. Lecture Notes in Computer Science","author":"Lhot\u00e1k O.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996861"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379676"},{"key":"e_1_2_1_24_1","unstructured":"Lind-Nielsen J. 2006. BuDDy A Binary Decision Diagram Package. http:\/\/buddy.sourceforge.net\/.  Lind-Nielsen J. 2006. BuDDy A Binary Decision Diagram Package. http:\/\/buddy.sourceforge.net\/."},{"volume-title":"Workshop on Declarative Programming in the Context of Object-Oriented Languages. 145--166","author":"Meijer E.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008643722423"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379017"},{"key":"e_1_2_1_28_1","unstructured":"Nilsson M. 2006. GBDD -- A package for representing relations with BDDs. http:\/\/www.regularmodelchecking.com\/software\/docs\/stable\/gbdd\/index.html.  Nilsson M. 2006. GBDD -- A package for representing relations with BDDs. http:\/\/www.regularmodelchecking.com\/software\/docs\/stable\/gbdd\/index.html."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765947"},{"key":"e_1_2_1_30_1","unstructured":"Poskanzer J. 2006. thttpd: tiny\/turbo\/throttling HTTP server. http:\/\/www.acme.com\/software\/thttpd\/.  Poskanzer J. 2006. thttpd: tiny\/turbo\/throttling HTTP server. http:\/\/www.acme.com\/software\/thttpd\/."},{"key":"e_1_2_1_31_1","unstructured":"Qian F. 2006. SableJBDD A Java binary decision diagram package. http:\/\/www.sable.mcgill.ca\/~fqian\/SableJBDD\/.  Qian F. 2006. SableJBDD A Java binary decision diagram package. http:\/\/www.sable.mcgill.ca\/~fqian\/SableJBDD\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504286"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320568"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Schwartz J. T. Dewar R. B. K. Dubinsky E. and Schonberg E. 1986. Programming with Sets\u2014An Introduction to Setl. Springer Berlin Germany.   Schwartz J. T. Dewar R. B. K. Dubinsky E. and Schonberg E. 1986. Programming with Sets\u2014An Introduction to Setl. Springer Berlin Germany.","DOI":"10.1007\/978-1-4613-9575-1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263703"},{"volume-title":"CUDD: CU Decision Diagram Package","year":"2006","author":"Somenzi F.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the 4th International Symposium on Algorithms and Computation (ISAAC'93)","author":"Tani S.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","first-page":"146","article-title":"Depth first search and linear graph algorithms","volume":"1","author":"Tarjan R. E.","year":"1972","journal-title":"J. Comput."},{"key":"e_1_2_1_39_1","unstructured":"Ullman J. D. 1988. Principles of Database and Knowledge-Base Systems Vol. I. Computer Science Press.   Ullman J. D. 1988. Principles of Database and Knowledge-Base Systems Vol. I. Computer Science Press."},{"key":"e_1_2_1_40_1","unstructured":"Ullman J. D. 1989. Principles of Database and Knowledge-Base Systems Vol. II. Computer Science Press.   Ullman J. D. 1989. Principles of Database and Knowledge-Base Systems Vol. II. Computer Science Press."},{"key":"e_1_2_1_41_1","unstructured":"Vahidi A. 2006. JBDD a Java interface to CUDD and BuDDY. http:\/\/javaddlib.sourceforge.net\/jbdd\/index.html.  Vahidi A. 2006. JBDD a Java interface to CUDD and BuDDY. http:\/\/javaddlib.sourceforge.net\/jbdd\/index.html."},{"key":"e_1_2_1_42_1","unstructured":"Whaley J. 2006a. bddbddb. http:\/\/bddbddb.sourceforge.net.  Whaley J. 2006a. bddbddb. http:\/\/bddbddb.sourceforge.net."},{"key":"e_1_2_1_43_1","unstructured":"Whaley J. 2006b. JavaBDD. http:\/\/javabdd.sourceforge.net.  Whaley J. 2006b. JavaBDD. http:\/\/javabdd.sourceforge.net."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/647171.718318"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"volume-title":"Proceedings of Design, Automation and Test in Europe (DATE'03)","author":"Zhang L.","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774594"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996860"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377492.1377494","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1377492.1377494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:55Z","timestamp":1750255075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377492.1377494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1377492.1377494"],"URL":"https:\/\/doi.org\/10.1145\/1377492.1377494","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}