{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T22:12:48Z","timestamp":1770243168635,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2212558, CCF-2211968"],"award-info":[{"award-number":["CCF-2212558, CCF-2211968"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,10,8]]},"abstract":"<jats:p>\n                    This paper presents a new data structure, called\n                    <jats:italic toggle=\"yes\">Weighted Context-Free-Language Ordered BDDs<\/jats:italic>\n                    (WCFLOBDDs), which are a hierarchically structured decision diagram, akin to Weighted BDDs (WBDDs) enhanced with a procedure-call mechanism. For some functions, WCFLOBDDs are exponentially more succinct than WBDDs. They are potentially beneficial for representing functions of type\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:msup>\n                          <mml:mi mathvariant=\"double-struck\">B<\/mml:mi>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msup>\n                        <mml:mo>\u2192<\/mml:mo>\n                        <mml:mi>D<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    , when a function\u2019s image\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>V<\/mml:mi>\n                        <mml:mo>\u2286<\/mml:mo>\n                        <mml:mi>D<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    has many different values. We apply WCFLOBDDs in quantum-circuit simulation, and find that they perform better than WBDDs on certain benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\u2212<\/mml:mo>\n                        <mml:mn>64<\/mml:mn>\n                        <mml:mo>\u00d7<\/mml:mo>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    that of WBDDs (and\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\u2212<\/mml:mo>\n                        <mml:mn>128<\/mml:mn>\n                        <mml:mo>\u00d7<\/mml:mo>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    that of CFLOBDDs, which are an unweighted version of WCFLOBDDs). These results support the conclusion that for this application\u2014from the standpoint of problem size, measured as the number of qubits\u2014WCFLOBDDs provide the best of both worlds: performance roughly matches whichever of WBDDs and CFLOBDDs is better. (From the standpoint of running time, the results are more nuanced.)\n                  <\/jats:p>","DOI":"10.1145\/3689760","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"1390-1419","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Weighted Context-Free-Language Ordered Binary Decision Diagrams"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4215-0651","authenticated-orcid":false,"given":"Meghana","family":"Sistla","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6859-1391","authenticated-orcid":false,"given":"Swarat","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5676-9949","authenticated-orcid":false,"given":"Thomas","family":"Reps","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Rajeev Alur. 2024. Nested Words - aka Visibly Pushdown Languages. https:\/\/www.cis.upenn.edu\/~alur\/nw.html Last accessed on 04-03-2024."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_89"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_3_1_7_2","unstructured":"Anonymous. 2022. CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams. Public github repository redacted to preserve anonymity."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015246"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008699807402"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Stephane Beauregard. 2003. Circuit for Shor\u2019s algorithm using 2n+3 qubits. Quantum Inf. Comput. (2003). https:\/\/doi.org\/10.26421\/QIC3.2-8 10.26421\/QIC3.2-8","DOI":"10.26421\/QIC3.2-8"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604137"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Randal E. Bryant and Yirng-An Chen. 1995. Verification of Arithmetic Circuits with Binary Moment Diagrams. In Proc. of the 30th ACM\/IEEE Design Automation Conf. 535\u2013541. https:\/\/doi.org\/10.1145\/217474.217583 10.1145\/217474.217583","DOI":"10.1145\/217474.217583"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31653-1_21"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Edmund M. Clarke Masahiro Fujita and Xudong Zhao. 1995. Hybrid decision diagrams: Overcoming the limitations of MTBDDs and BMDs. In Proc. of the Int. Conf. on Computer Aided Design. 159\u2013163. https:\/\/doi.org\/10.1109\/ICCAD.1995.480007 10.1109\/ICCAD.1995.480007","DOI":"10.1109\/ICCAD.1995.480007"},{"key":"e_1_3_1_16_2","unstructured":"Adnan Darwiche. 2011. SDD: A New Canonical Representation of Propositional Knowledge Bases. In Twenty-Second International Joint Conference on Artificial Intelligence. https:\/\/doi.org\/10.5591\/978-1-57735-516-8\/IJCAI11-143 10.5591\/978-1-57735-516-8\/IJCAI11-143"},{"key":"e_1_3_1_17_2","doi-asserted-by":"crossref","unstructured":"Evan Driscoll Aditya V. Thakur and Thomas W. Reps. 2012. OpenNWA: A Nested-Word Automaton Library. In Computer Aided Verification - 24th International Conference CAV 2012 Berkeley CA USA July 7-13 2012 Proceedings. 665\u2013671. https:\/\/doi.org\/10.1007\/978-3-642-31424-7_47 10.1007\/978-3-642-31424-7_47","DOI":"10.1007\/978-3-642-31424-7_47"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008647823331"},{"key":"e_1_3_1_19_2","volume-title":"Monocopy and associative algorithms in an extended LISP","author":"Goto Eiichi","year":"1974","unstructured":"Eiichi Goto. 1974. Monocopy and associative algorithms in an extended LISP. Technical Report. Technical Report TR 74-03, University of Tokyo."},{"key":"e_1_3_1_20_2","volume-title":"Inductive Boolean Function Manipulation: A Hardware Verification Methodology for Automatic Induction","author":"Gupta Aarti","year":"1994","unstructured":"Aarti Gupta. 1994. Inductive Boolean Function Manipulation: A Hardware Verification Methodology for Automatic Induction. Ph. D. Dissertation. Carnegie Mellon Univ. Tech. Rep. CMU-CS-94-208."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.1993.580055"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90035-9"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Xin Hong Xiangzhen Zhou Sanjiang Li Yuan Feng and Mingsheng Ying. 2020. A tensor network based decision diagram for representation of quantum circuits. ACM Transactions on Design Automation of Electronic Systems (TODAES) (2020). https:\/\/doi.org\/10.1145\/3514355 10.1145\/3514355","DOI":"10.1145\/3514355"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.644298"},{"key":"e_1_3_1_25_2","unstructured":"Doga Kisa Guy Van den Broeck Arthur Choi and Adnan Darwiche. 2014. Probabilistic sentential decision diagrams. In Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/11817949_14"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_36"},{"issue":"1","key":"e_1_3_1_28_2","article-title":"Weighted Logics for Nested Words and Algebraic Formal Power Series","volume":"6","author":"Mathissen Christian","year":"2010","unstructured":"Christian Mathissen. 2010. Weighted Logics for Nested Words and Algebraic Formal Power Series. Log. Methods Comput. Sci. 6, 1 (2010). http:\/\/arxiv.org\/abs\/1001.2175","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_3_1_29_2","volume-title":"Memo functions: a language feature with\" rote-learning\" properties","author":"Michie Donald","year":"1967","unstructured":"Donald Michie. 1967. Memo functions: a language feature with\" rote-learning\" properties. Edinburgh University, Department of Machine Intelligence and Perception."},{"key":"e_1_3_1_30_2","unstructured":"Kengo Nakamura Shuhei Denzumi and Masaaki Nishino. 2020. Variable Shift SDD: A More Succinct Sentential Decision Diagram. (2020). https:\/\/doi.org\/10.4230\/LIPICS.SEA.2020.22 10.4230\/LIPICS.SEA.2020.22"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2459034"},{"key":"e_1_3_1_32_2","unstructured":"Madhusudan Parthasarathy. 2024. Visibly Pushdown Automata - Automata on Nested Words. https:\/\/madhu.cs.illinois.edu\/vpa\/ Last accessed on 04-03-2024."},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","unstructured":"Frank Reffel. 1999. BDD-Nodes can be More Expressive. In Proc. of the Asian Computing Science Conference. https:\/\/doi.org\/10.1007\/3-540-46674-6_25 10.1007\/3-540-46674-6_25","DOI":"10.1007\/3-540-46674-6_25"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44898-5_11"},{"key":"e_1_3_1_35_2","unstructured":"Meghana Sistla Swarat Chaudhuri and Thomas W. Reps. 2022. CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams. CoRR abs\/2211.06818 (2022). https:\/\/doi.org\/10.48550\/arXiv.2211.06818 10.48550\/arXiv.2211.06818 arXiv:2211.06818"},{"key":"e_1_3_1_36_2","unstructured":"Meghana Sistla Swarat Chaudhuri and Thomas W. Reps. 2023. Symbolic Quantum Simulation with Quasimodo. CoRR abs\/2302.04349 (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.04349 10.48550\/arXiv.2302.04349 arXiv:2302.04349"},{"key":"e_1_3_1_37_2","unstructured":"Meghana Sistla Swarat Chaudhuri and Thomas W. Reps. 2023. Weighted Context-Free-Language Ordered Binary Decision Diagrams. CoRR abs\/2305.13610 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2305.13610 10.48550\/ARXIV.2305.13610 arXiv:2305.13610"},{"key":"e_1_3_1_38_2","unstructured":"Meghana Sistla Swarat Chaudhuri and Thomas W. Reps. 2024. Weighted Context-Free-Language Ordered Binary Decision Diagrams (Artifact). https:\/\/doi.org\/10.5281\/zenodo.12670155 10.5281\/zenodo.12670155 Computer Software."},{"key":"e_1_3_1_39_2","doi-asserted-by":"crossref","unstructured":"Meghana Aparna Sistla Swarat Chaudhuri and Thomas Reps. 2024. CFLOBDDs: Context-free-language ordered binary decision diagrams. ACM Transactions on Programming Languages and Systems (2024). https:\/\/doi.org\/10.1145\/3651157 10.1145\/3651157","DOI":"10.1145\/3651157"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008691605584"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00768-2_1"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:QINP.0000022725.70000.4a"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2004.1269084"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-09-11-1108"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32157-3_1"},{"key":"e_1_3_1_46_2","doi-asserted-by":"crossref","unstructured":"Sarma B.K. Vrudhula Massoud Pedram and Yung-Te Lai. 1996. Edge valued binary decision diagrams. Representations of Discrete Functions (1996) 109\u2013132.","DOI":"10.1007\/978-1-4613-1385-4_5"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789"},{"key":"e_1_3_1_48_2","doi-asserted-by":"crossref","unstructured":"M. Yannakakis. 1990. Graph-Theoretic Methods in Database Theory. In Symp. on Princ. of Database Syst. 230\u2013242. https:\/\/doi.org\/10.1145\/298514.298576 10.1145\/298514.298576","DOI":"10.1145\/298514.298576"},{"key":"e_1_3_1_49_2","doi-asserted-by":"crossref","unstructured":"Alwin Zulehner Stefan Hillmich and Robert Wille. 2019. How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing. International Conference on Computer Aided Design (ICCAD) (2019). https:\/\/doi.org\/10.1109\/ICCAD45719.2019.8942057 10.1109\/ICCAD45719.2019.8942057","DOI":"10.1109\/ICCAD45719.2019.8942057"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-41753-6"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:02:49Z","timestamp":1770195769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":49,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689760"],"URL":"https:\/\/doi.org\/10.1145\/3689760","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}